# Tiling a rectangle with L-tromino [duplicate]

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.

## marked as duplicate by MJD, user147263, Harish Chandra Rajpoot, user99914, WintherSep 30 '15 at 0:35

• Try induction. Place the first L around the missing square so that you have a 2x2 block removed. Look at the 4 blocks that are left. Each looks like a square with a corner removed... – TravisJ Sep 28 '15 at 14:23
• TravisJ's comment and your response sound like you were thinking about L-tromino, not L-tetromino? – J. J. Sep 28 '15 at 14:34
• A tetromino contains 4 squares and 4 is an even number. So what sort of L-tetromino we are allowed to use??? – achille hui Sep 28 '15 at 15:02
• @J.J., I thought the L-tetromino was made of 3 squares... not like a tetris L with 4 squares. That is an important clarification that should be made. The hint I provided should work for 3-square L, I don't know if it will work (and expect it will not work) for a 4-square L. – TravisJ Sep 28 '15 at 15:36
• I meant the 3 square one. – guest Sep 28 '15 at 18:43

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.