janmr blog

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

Consider now the following question: Given a $2^n \times 2^n$ square grid ($n \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 \times 1$ grid ($n=0$) with one cell occupied then there is nothing to tile and we are done.

For $n \geq 1$ we can divide the square into four sub-squares each of size $2^{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:

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 \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.