US-TST 2009 Problem 1

Let $m$ and $n$ be positive integers. Mr. Fat has a set $S$ containing every rectangular tile with integer side lengths and area of a power of $2$ . Mr. Fat also has a rectangle $R$ with dimensions $2^m \times 2^n$ and a $1 \times 1$ square removed from one of the corners. Mr. Fat wants to choose $m + n$ rectangles from $S$ , with respective areas $2^0, 2^1, \ldots, 2^{m + n - 1}$ , and then tile $R$ with the chosen rectangles. Prove that this can be done in at most $(m + n)!$ ways.

Palmer Mebane.