Tiling a rectangle with L-tromino

Question

Consider a $2^{1999} \times 2^{1999}$ square, with a single $1 \times 1$ square removed. Show that no matter where the small square is removed it is possible to tile this "giant square minus tiny square" with L-trominos.

Answer 1

Let $\mathcal{D}_{1999}$ consist of the single $2^{1999} \times 2^{1999}$-square. For $1 \le n \le 1999$, define the family $\mathcal{D}_{n-1}$ recursively to contain the squares obtained from the squares of $\mathcal{D}_n$ by splitting them into four equal size squares.

For each $0 \le k \le 1999$ there is a unique dyadic cube $Q_k$ in $\mathcal{D}_k$ that contains the removed unit square. We prove by induction that one can fill $Q_k$ by L-trominos starting from $k=0$.

When $k=0$ there are no squares to fill, so we are done. Let then $k \ge 1$ and assume that the claim holds for $k-1$. The square $Q_k$ contains $Q_{k-1}$, and by filling $Q_{k-1}$ we get one fourth of $Q_k$ filled and are left with three $2^{k-1} \times 2^{k-1}$ subsquares to fill. Place one L-tromino so that it covers the three non-filled center-squares. Each of the three $2^{k-1} \times 2^{k-1}$ subsquares will then have one filled (removed) square, and we can fill them by induction.