Problem 2320

Solution 1. We call each of the rectangles in $S$ a tile, and the tile with area $2^0 = 1$ the unit tile. We may assume without loss of generality that the missing $1 \times 1$ square in $R$ is the top-left corner. Suppose Mr. Fat walks on the path of squares starting from the top right corner square and going left along the top row of squares until the missing square is stepped on, then turning and going down along the left column of squares to the bottom left square. For a given tiling, let $a_1, a_2, \dots$ be the sequence of areas of the tiles he steps on by walking along this path from start to finish. We will show that
(a) every tile is stepped on, that is, $a_1, a_2, \dots, a_{m+n}$ is a rearrangement of $2^0, 2^1, \dots, 2^{m+n}$; and
(b) any valid sequence $a_1, \dots, a_n$ uniquely determines the tiling.
Since there are at most $(m+n)!$ ways to order the $m+n$ possible areas, this would finish the problem.

To establish (a), we induct on $m+n$. It is trivial for $m+n=1$. Suppose it is true for $m+n-1$. We show it holds for $m+n$. Consider the tile with area $2^{m+n-1}$, and call it $T$. If $T$ has dimensions $2^a \times 2^b$, then we have $a+b=m+n-1$ and since $T$ is contained in $R$, $a \le m$ and $b \le n$. Thus the only two possibilities for the dimensions of $T$ are $2^m \times 2^{n-1}$ or $2^{m-1} \times 2^n$. In other words, $T$ must stretch over either the entire length or entire width of $R$. It follows that $T$ must be hit on our walk.

Now, consider the rectangle formed by removing $T$ completely from $R$ and, if this breaks $R$ into two pieces, sliding them together so that the two newly formed edges coincide. This forms a tiling of a smaller rectangle $R'$ with dimensions $2^x \times 2^y$ for $x+y=m+n-1$, and the areas hit along the walk corresponding to $R'$ are precisely those areas encountered along the walk on $R$ other than $T$. By the inductive hypothesis, all of the areas are stepped on, and so (a) holds for all rectangles $R$.

To establish (b), we again induct on $m+n$. It is trivial for $m+n=1$. Suppose it is true for $m+n-1$. Let $a_1, a_2, \dots, a_{m+n}$ be a valid ordering of the areas $\{2^0, 2^1, \dots, 2^{m+n-1}\}$, that is, an ordering generated by walking along a tiling.

Suppose $2^{m+n-1}$ appears before $2^0$ in $a_1, \dots, a_{m+n}$. Consider any tiling that generates this ordering and call the largest tile $T$. We must hit $T$ before the unit tile. Hence, the part of the rectangle below or to the left of $T$ has odd area, since all other tiles in the tiling have even area. In particular, this part must contain the missing corner. The corner is in the top-left, so this part can't be below the largest rectangle. Therefore, it is to the left of $T$. Hence $T$ has the same height as $R$. Likewise, if we hit the unit tile before $T$, we may use the same reasoning to show that $T$ would have the same width as $R$.

Therefore, depending on whether $2^{m+n-1}$ appears before or after $2^0$ in the ordering, we may uniquely determine whether $T$ spans an entire column or an entire row in any tiling achieving the given ordering. This uniquely determines the dimension of the rectangle that is obtained by removing $T$ and sliding the two resulting parts together (if there are even two parts at all). Suppose that the dimensions of this rectangle are uniquely fixed to be $2^a \times 2^b$, where we must have $a+b=m+n-1$.

Now, remove $2^{m+n-1}$ to obtain an ordering of $\{2^0, 2^1, \dots, 2^{m+n-2}\}$. By the inductive hypothesis, there is a unique tiling of a $2^a \times 2^b$ rectangle by these tiles. The position of $2^{m+n-1}$ in the given ordering then provides a unique way to insert a tile of area $2^{m+n-1}$ to reconstruct a tiling of the original $2^m \times 2^n$ rectangle; that is, we know whether this tile spanned a column or a row and the ordering tells us the position along the top and left boundaries of the rectangle where it must be inserted. Finally, any tiling of the original $2^m \times 2^n$ rectangle that generates the given ordering must be obtained by making this insertion. Since the tiling of our $2^a \times 2^b$ rectangle was unique by induction, the entire tiling is unique, as desired.

Solution 2 (By Ricky Liu). We may assume without loss of generality that $R$ is missing its upper left corner. The left column of $R$ has length $2^m - 1$, which cannot be written as a sum of fewer than $m$ powers of $2$. Therefore, at least $m$ tiles intersect this column. Likewise, at least $n$ tiles intersect the top row. Since no tiles can intersect both the left column and the top row, we must have equality in both cases. Hence $m$ rectangles intersect the left column in $2^0, 2^1, \dots, 2^{m-1}$ squares, and $n$ rectangles intersect the top row in $2^0, \dots, 2^{n-1}$ squares.

We count tilings of $R$ with any $m+n$ rectangles $A_1, \dots, A_m, B_1, \dots, B_n$ such that $A_i$ intersects the left column in $2^{i-1}$ squares and $B_j$ intersects the top row in $2^{j-1}$ squares. The lower right corner of $R$ can lie in any of these $m+n$ rectangles, whose placement is then uniquely determined. Then the lower right corner of the remaining portion of $R$ can lie in any of the other $m+n-1$ rectangles, and so forth. It follows that there are exactly $(m+n)!$ such tilings. Since all of our desired tilings have this form, this completes the proof.