Lesson 6

Finally, consider the following problem.

Prove that for any integer \(n \ge 1\), a square of size \(2^{n} \times 2^{n}\), from which one of the four central cells is removed, can be divided into L-shaped triminoes (L-shaped pieces of three cells).

Problem. Is this a correct proof?

The base case \(n=1\) is clear. For the induction step \(n-1 \to n\), consider a \(2^{n} \times 2^{n}\) grid with one central cell missing. Cut the grid into four subgrids of size \(2^{n-1}\times 2^{n-1}\) and place a trimino in the center so that it covers one cell of each subgrid not containing a missing cell. Then, every subgrid has one missing cell and hence can be tiled by the induction hypothesis.