janmr blog

Tiling with L-Trominos

An L-tromino is a figure in the plane made of three equal-sized squares connected in an L-shape:

An L-tromino

Consider now the following question: Given a 2n×2n2^n \times 2^n square grid (n0n \geq 0) with exactly one cell occupied, is it possible to tile the remaining area using L-trominos?

The answer is yes and it is quite easy to see why. First, if it is a 1×11 \times 1 grid (n=0n=0) with one cell occupied then there is nothing to tile and we are done.

For n1n \geq 1 we can divide the square into four sub-squares each of size 2n1×2n12^{n-1} \times 2^{n-1}. The occupied cell must appear in exactly one of these sub-squares and we now place an L-tromino appropriately at the center such that one cell gets occupied in each of the other three sub-squares:

L-tromino induction proof

Now each of the sub-squares have exactly one cell occupied and the theorem follows by induction.

As an example, here is a complete tiling for a 32×3232 \times 32 grid:

(Interactive, full-screen example.)

The theorem is mentioned in Proof Without Words II by Roger B. Nelsen and in Mathematical Gems III by Ross Honsberger. The theorem itself is attributed to Solomon W. Golomb.