This is my problem as you can see; I was very happy to see it make it on. Here are two solutions, outlined.

I think this problem is quite hard for a problem 1, even compared to IMO. Is it just me?

MellowMelon wrote: This is my problem as you can see; I was very happy to see it make it on. Here are two solutions, outlined.

Regarding the second solution, are you sure that it is required precisely $ m$ and $ n$ rectangles to tile the line with the missing corner ?I thought this in my attempt to solve the problem, but I thought this wasn´t true. We do indeed have that $ 2^m-1=1+2+...+2^{m-1}$ (is this the justification?), but I don´t think that this proves that this line requires exactly $ m$ rectangles.Sorry that I don´t understand it.Could you explain it to me?

$ 2^m - 1 = 1 + 2 + \cdots + 2^{m - 1}$ is what is actually used. To show $ m$ powers of $ 2$ are needed to construct this number, consider the sum that uses a minimal amount. None can be repeated or we combine them and minimality is contradicted. None can be $ 2^m$ or more or we're too high. Now it's clear that if less than $ m$ powers are used our sum is less than $ 1 + 2 + \cdots + 2^{m - 1}$ (which uses everything available).

MellowMelon wrote: $ 2^m - 1 = 1 + 2 + \cdots + 2^{m - 1}$ is what is actually used. To show $ m$ powers of $ 2$ are needed to construct this number, consider the sum that uses a minimal amount. None can be repeated or we combine them and minimality is contradicted. None can be $ 2^m$ or more or we're too high. Now it's clear that if less than $ m$ powers are used our sum is less than $ 1 + 2 + \cdots + 2^{m - 1}$ (which uses everything available). Thanks a lot.

Here is a problem that I wrote inspired by this TST problem: Consider a $ \underbrace{4\times 4\times \cdots \times 4}\limits_n$ hypertorus (a hypercube where the sides wrap around) missing one unit cell. We want to cover it with $ 2n$ hyperboxes with integer side lengths of sizes $ 2^0, 2^1, \ldots, 2^{2n-1}$. Two of these coverings are equivalent if the corresponding hyperboxes cover the same unit cells. Show that there are exactly $ (2n)!$ such nonequivalent coverings.

jgnr wrote: I think this problem is quite hard for a problem 1, even compared to IMO. Is it just me? Yeah, I agree A dented rectangle is a rectangle of the form $\ell \times 2^k$ minus the upper-right corner. Recursively, we define the order on a tiling of a dented rectangle $D$ as follows: consider the largest tile $t$, which clearly must divide the dented rectangle $D$ into a dented rectangle $D'$ and a rectangle $R$ (possibly empty). Observe that the tiling of $R$ (by binary representation) consists of a bunch of parallel rectangles. If the dented rectangle splits horizontally, we take the order on $D'$, then $|t|$, then the order from left to right of the tile sizes in $R$; otherwise in the other case we take the up-down order on sizes of $R$, then $|t|$, then the order on $D'$. Looking at the tile sizes, this induces a permutation of $\{2^0, \dots, 2^{m+n-1}\}$ for each tiling, of which there are $(m+n)!$. To show no two tilings produce the same order we use strong induction on areas. Indeed just note that by looking at the location of $2^0$ we can distinguish between a horizontal/vertical split and looking at binary representations of the areas ensures that within each case the orders are distinct. So it reduces to the claim for $D'$ and $R$, whence the former follows by induction and the latter being trivial. The bound is not especially tight; that's a motivation to look for a combinatorial solution like this (rather than trying to be very precise). Also, the combinatorial idea of recursion (or "dynamic programming" if you like USACO) is IMO the other key insight.

Does this work? Assume the corner is on the upper left side of the rectangle. We will prove the result using induction on $m+n$. For our base case, where $n = m = 1$, there are two ways: Either the $2$ by $1$ tile is vertical or horizontal. For our inductive step, assume that all $m, n$ such that $m+n\leq r$ work. We will prove that all $m+n = r+1$ work. Consider the rectangle with area $2^{m+n-1}$. Its dimensions must either be $2^{m}$ by $2^{n-1}$ or $2^{m-1}$ by $2^{n}$. Call this rectangle $F$. Then, for the first case, if it was placed a distance $c$ from the left wall, where $c$ was not a power of two, and $k$ was the number of $1$s in the binary representation of $c$, then I claim that there are $k!\cdot m!$ ways to place the rectangles on the left side of the $F$. There are a unique set rectangle areas we can use (express the area on the left side of $F$ in binary). Consider the largest rectangle area, and let it be $2^{m+t}$, where $t$ is a constant. Clearly $2^{m+t} > $ the area on the right of $F$, and it's dimensions must be $2^{m}$ by $2^{t}$, otherwise it will not fit. Then, we can continue, and there are exactly $k$ rectangles with area $2^{m+t'}$, where $t' \geq 0$. There are $k!$ ways to arrange these rectangles, and all that's left it the $1$ by $2^{m} - 1$ rectangle. There are $m!$ ways to arrange the $1$ by $2^{i}$ rectangles, for a total of $k!\cdot m!$ ways. However, there are still $n-1-k$ rectangles left, all of whom have area greater or equal $2^{m}$. We can use the same trick for the rectangles on the left side of $F$, so that the vertical sides of all the rectangles on the right of $F$ are $2^{m}$. There are $(n-1-k)!$ ways to arrange these rectangles. Thus, there are a total of $k!(n-1-k)!m!$. Since there are $\binom{n-1}{k}$ different numbers that have $k$ ones when written in binary, the total number of ways for $2^{m}$ by $2^{n-1}$ rectangles is \[\sum_{k=0}^{n-1}\binom{n-1}{k}m!k!(n-1-k)! = \sum_{k=0}^{n-1}(n-1)!m! = (n)!m!\]However, whenever $c$ is a power of $2$, then we have to reconsider. If we let $c = 2^{k}$, then there are $(m+k)!$ ways to arrange the tiles on the left side of $F$, due to our inductive hypothesis, and $(n-1-k)!$ ways to arrange them on the right side of $F$. Thus, the total number of ways for $F$ having dimensions $2^{m}$ by $2^{n-1}$ is less than or equal to \[n!m! + \sum_{k=1}^{n-1}(m+k)!(n-1-k)!\]We can do the same for the second case, to get the total number of ways is less than or equal to \[2n!m! + \sum_{k=1}^{n-1}(m+k)!(n-1-k)! + \sum_{k=1}^{m-1}(n+k)!(m-1-k)!\]\[\leq 2\cdot (n+m-1)! + (n-1)\cdot (n+m-2)! + (m-1)\cdot (n+m-2)!\]\[= (n+m-2)!(3n+3m-4)\]\[\leq (n+m)!\]Our inductive step is proven, so we conclude the result for all $n, m\geq 1$.

Call an $X\times Y$ rectangle a rectangle with vertical height $X$ and horizontal width $Y$, and a dented rectangle an $X\times Y$ with top right corner missing. Note that for any shape, there is a unique set of blocks of power of 2 area by binary expansion. Claim 1: Say you have the correct sized blocks for a $2^m\times x$ rectangle. Then it must tile as vertical strips $2^m\times 2^{a_1},\ldots,2^m\times 2^{a_k}$ in some order if $x=2^{a_1}+\cdots+2^{a_k}$. Proof: Induct on $x$, $x=1$ trivial. WLOG $a_1<\cdots<a_k$. We claim the $2^{m+a_k}$ area block must tile as $2^m\times 2^{a_k}$; this finishes since now two rectangles on either side and finish by induction on both. Say it splits as $2^b\times 2^{m+a_k-b}$. Then \begin{align*} 2^b&\le 2^m \implies b\le m, \\ 2^{m+a_k-b} &\le x < 2^{a_k+1} \implies m\le b. \end{align*}So $b=m$, as desired. $\blacksquare$ Claim 2: Say you have correct sized blocks for a $2^m\times x$ dented rectangle $R$. There must be a sequence of parallel $2^m\times --$ vertical blocks starting from the leftmost edge. (If $x=2^n$ for some $n$, you can switch $m,n$ too.) Proof: Logic similar to the above claim shows that the largest block must be a $2^m\times --$ block somewhere in the middle of $R$. This splits $R$ into a rectangle on the left and a dented rectangle on the right. The left rectangle must tile with vertical strips by Claim 1, proving the claim. (Note that there could also be more vertical strips to the right of the largest block.) $\blacksquare$ Key Claim: [Full Tiling Classification] There is a sequence of red vertical $2^m\times --$ tiles for some distance, then a sequence of blue horizontal $--\times 2^n$ tiles from the bottom up to some distance, then a sequence of maximally vertical red tiles from the left to some distance, and so on. (Figure below not to scale.)

Say the non-tiled dented rectangle in the top right is $x\times y$. At least one of $x,y$ must be a power of 2. Suppose only one is, say $x$. Then by Claim 2 the next rectangle in the order must be placed as an $x\times --$ rectangle on the left edge. It's location is fixed, and there are $m+n-k$ blocks left, so there are at most $m+n-k$ options. Now suppose $x$ and $y$ are powers of 2. Then area left is $A=xy-1$, which is 1 less than a power of 2. So $A=2^0+\cdots+2^\ell$ for some $\ell$. Then there are $\ell+1$ blocks used, so $\ell=m+n-k-1$, and hence $xy=2^{m+n-k}$. The key is to notice that if the block is horizontal, then the height must be a power of 2, so there are at most $\log_2 x$ options! Similarly, if it's vertical there are $\log_2 y$ options for the block. In total, there are at most \[ \log_2x+\log_2y = \log_2(xy)= m+n-k\]options, as claimed.

If this works, the bound is extremely weak-- it can be easily improved by inducting separately on the case where rectangle $m+n-1$ has dimensions $2^m\times 2^{n-1}$ and the case where it has dimensions $2^{m-1}\times 2^n.$ I found the same rigid characterization as @above, so hopefully its correct? Label the rectangle with area $2^i$ with $i,$ and assume WLOG that the top right square is missing. Call a rectangle $\emph{tall}$ if it has height $2^m.$ Induct on the value of $m+n.$ Assume $m+n-1$ has dimensions $2^m\times 2^{n-1};$ we can deal with the other case similarly. Suppose rectangle $m+n-k$ is the largest rectangle that isn't tall. Then, it must have length at least $2^{n-k+1}.$ But since rectangles $m+n-1,m+n-2,\dots,m+n-(k-1)$ are all tall, the remaining area has length at most $$2^n-(2^{n-1}+2^{n-2}+\dots+2^{n-k+1})=2^{n-k+1}.$$Therefore, equality must occur, so rectangles $m+n-1,m+n-2,\dots,m+n-(k-1)$ must occupy the leftmost region possible. There are $(k-1)!$ ways to arrange these rectangles, and, by the inductive hypothesis, at most $(m+n-k+1)!$ ways to arrange the remaining rectangles. Hence, the number of tilings is at most $$\sum_{k=2}^{m+1}(k-1)!(m+n-k+1)!<\sum_{k=2}^{m+1}(m+n-1)!=m(m+n-1)!.$$We can similarly get the bound of $n(m+n-1)!$ if we assume that rectangle $m+n-1$ has dimensions $2^{m-1}\times 2^n,$ so the final answer is at most $(m+n)!,$ as desired.

Suppose WLOG the upper left corner is missing a square; we proceed by induction on m+n, with m+n=2 evident. Consider the top and left sides that have lengths $2^m-1,2^n-1$. A rectangle with a side on one of these sides won't be on the other side, and mod 2 in $2^m-1$ shows that you need a rectangle with side length 1 on the top side, then $2^m-2$ mod 4 shows you need a rectangle with side length 2, etc. so that you need m rectangles that share a side with the top, and n with the left. It follows that any rectangle must share a side with left or top, and now consider the largest rectangle: It can have lengths $2^0,2^1,...,2^{m-1}$ on the top, for m choices, or similarly n choices on the left side. After placing it, we reduce to an inductive position; in particular, there are m+n options for the largest rectangle, and by inductive hypothesis there are (m+n-1)! ways remaining, hence inductive step is established. We conclude. Edit: Not sure why others thought this was difficult, maybe for a 2009 TST but imo nowadays this should be a JMO 1, maybe even easier.

WLOG interpret a $a \times b$ be rectangle with $a$ being vertical and $b$ horizontal. We claim inductively that the number of ways to fill a rectangle missing a corner with $n$ rectangles with areas that are powers of two is less than $n!$. Consider where the largest rectangle with area $2^{m+n-1}$. When we place it in the grid horizontally or vertically, it splits the rectangle missing a corner into a smaller rectangle missing a corner and potentially a smaller rectangle as well. Note that the smaller rectangle must be divided into rectangles oriented the same way as the largest rectangle. Furthermore, which of the remaning rectangles after largest belong on which side is determined. $0$ to $2^m - 1$ Thus, there are at most \[ \sum_{i=0}^{2^m-1} s_2(i)!(m+n-1 - s_2(i))! + \sum_{i=0}^{2^n-1} s_2(i)!(m+n-1 - s_2(i))! \]ways to fill. This simplifies as \[ \sum_{i=0}^{m} \binom{m}{i} i!(m+n-1 - i)! + \sum_{i=0}^{n} \binom{n}{i} i!(m+n-1 - i)! \le 2(m+n-1)! \le (m+n)! \]

quite hard for a TST 1 imo Define a binary tiling of a region consisting of unit cells as a tiling with rectangles whose areas are powers of 2 such that each area appears at most once. Note that the set of areas only depends on the area of the region due to binary representation. We will prove a more general claim: A region that is either a rectangle with at least one dimension that is a power of 2, or a rectangle with at least one dimension that is a power of 2 minus one corner cell, has at most $d!$ binary tilings, where $d$ is the number of distinct areas (also the sum of the digits in binary of the total area). We will induct. This is clearly true of the rectangle is a 1 by $k$ stick. Now, suppose WLOG that there are $2^a$ rows. Case 1: The number of columns is not a power of 2. Consider the rectangle with the largest area in the binary tiling, which must contain more than half of the whole rectangle. In this case, if the height of the rectangle is anything less than $2^a$, even $2^{a-1}$ times the largest possible width (which is not the entire grid width since the number of columns is not a power of 2) is too small, as there is at most one crossed out cell. Thus, the rectangle must span from the top of the grid to the bottom. It will then split the rectangle into two regions. Note that given the split, by binary representation we already know which areas go in which region. Suppose that after the split we know that $x$ remaining tiles go in one region and $y$ in the other. We know by induction hypothesis that there are at most $x!y!$ ways to finish the tiling from here. Furthermore, there are at most ${x+y\choose x}$ ways to assign areas to regions to achieve a $x$ to $y$ split, since the set of sticks determines the total area which determines the cutoff point. so we can pick $x$ of the $x+y$ sticks to go in one region. Hence, there are at most $$x!y!{x+y\choose x}=(x+y)!$$ways to do it given $x$ and $y$. Since $x+y$ is fixed and there are at most $x+y+1$ possible pairs, there are at most $(x+y+1)!$ total ways summing over all $(x,y)$, done. Case 2: The number of columns is a power of 2. The issue here is that in the case where there is a crossed out cell, we can actually make a horizontal cut that takes off very slightly more than half of the rectangle since the crossed-out cell belongs to the other part. This makes it also possible to cut in the other direction so our bound previously used overestimates by a factor of 2 (the bound on the other side gives the same result). However, we can cleverly refine the argument to save a factor of 2. We said earlier that there were at most ${x+y\choose x}$ ways to pick which areas belonged to which region. However, note that the single monomino must belong to the region with the crossed-out cell due to parity, so this reduces the count to ${x+y-1\choose x}.$ Multiplying this by $x!y!$ gives $$(x+y-1)!y,$$and again noting that $x+y-1$ is fixed and summing $y$ from 0 to $x+y$ gives $$\frac{(x+y-1)!(x+y)(x+y+1)}{2}=\frac{(x+y+1)!}{2}.$$Doing the same for the other direction we are done.

Clearly all rectangles have powers of 2 as side lengths, and note that it takes at least $k$ powers of two to sum to $2^k-1$. If we suppose the top right square is missing, we see that at least $m+n$ rectangles are required to cover the top and right rows, and hence all rectangles touch the top or right side of the board. Further, equality tells us the set of rectangles along the top/right side must have distinct lengths/widths. At each step, we consider the rectangle which covers the bottom left tile, which starts with $m+n$ choices, then goes to down to at most $m+n-1$, and so on. $\blacksquare$

WLOG let the missing corner be the top-right corner. Claim: Every rectangle in the tiling of $R$ must touch either the top or right edge. Proof: Consider the top and right edges: they have lengths $2^m-1$ and $2^n-1$, respectively. Note that \[2^m-1 = 2^{m-1} + 2^{m-2}+\dots+2^1+2^0,\] which implies the we need at least $m$ rectangles to cover the top edge. Similarly, we need at least $n$ rectangles to tile the right edge. Thus, we need at least $m+n$ rectangles to tile the top and right edges, but we only have $m+n$ rectangles to tile $R$, so we are done. $\square$ Consider the rectangle that covers the bottom-left corner. It can only be one of the $m$ rectangles touching the top edge or one of the $n$ rectangles touching the right edge. Hence, there are at most $m+n$ choices for the rectangle covering the bottom-left corner. Then, we are left with another rectangle and a similar argument applies to the new bottom-left corner. Continuing this repeatedly, we see that there are at most \[(m+n) \cdot (m+n-1) \cdot \ldots \cdot 2 \cdot 1 = (m+n)!\] ways to tile $R$, as desired. $\blacksquare$