Exercise 1760Logic, sets and proofs › Proof techniques › InductionOlympiadAdded 3 Nov 2026

Tiling by induction

#induction#tiling#L-tromino

Statement

Show that any $2^n\times2^n$ board with one square removed can be tiled by L-trominoes (3-square L-shapes).

Hint

Divide the board into four $2^{n-1}\times2^{n-1}$ quadrants; place one L-tromino at the center to create "removed" squares in each quadrant.

Show solutionHide solution

Solution

Base case. $n=1$ : $2\times2$ board with one square removed is itself an L-tromino.

Inductive step. Divide the $2^n\times2^n$ board into four $2^{n-1}\times2^{n-1}$ quadrants. One contains the removed square. Place one L-tromino covering one corner square of each of the other three quadrants (at the center of the board). Now each quadrant is a $2^{n-1}\times2^{n-1}$ board with one square removed, tiled by induction.

Conclusion. The board can be tiled.

Tiling by induction

Statement

Solution

More problems in Induction