Exercise 1246Combinatorics › Counting principlesOlympiadAdded 4 Nov 2026

Tiling a 2ⁿ × 2ⁿ board with L-trominoes

#induction#tilings#trominoes#divide and conquer

Statement

An L-tromino is the shape made of three unit squares forming an "L". Prove that for every $n\ge1$ , a $2^n\times2^n$ board from which any single square has been removed can be tiled by L-trominoes.

Hint

Divide the board into four quadrants. After placing one L-tromino well, each quadrant becomes an instance of the problem for $n-1$ .

Show solutionHide solution

Solution

Idea. Induction on $n$ , with a first move that recreates four smaller copies of the same problem.

Base case. For $n=1$ , a $2\times2$ board minus one square is exactly one L-tromino.

Induction step. Assume the statement for $n-1$ and take a $2^n\times2^n$ board with one square removed. Divide it into four quadrants of size $2^{n-1}\times2^{n-1}$ . The removed square lies in one of them.

Consider the four squares at the centre of the board: one in each quadrant. Place one L-tromino covering the three central squares that lie in the three quadrants not containing the removed square.

Now each quadrant has exactly one square that is missing. By the induction hypothesis, each quadrant minus that square can be tiled by L-trominoes. Together with the central tromino, this tiles the whole board.

Remark. The count is consistent: $4^n-1$ is divisible by $3$ .

Lesson. Induction with a self-similar structure: choose a first step that reduces the problem to several smaller problems of exactly the same kind.

Tiling a 2ⁿ × 2ⁿ board with L-trominoes

Statement

Solution

More problems in Counting principles