Golomb's inductive proof of a tromino theorem

Polyominos were invented by Solomon Golomb, then a 22 year-old student at Harvard, in 1954. A polyomino is a "rook"-connected set of equal squares. (In computer science the kind of connectedness where neighboring squares are required to share an edge is also known as the 4-connectedness. If two squares that share a vertex are also considered neighbors, we get the 8-connectedness.)

Trominos are polyominos that consist of three squares. There are two kinds of trominos: a 3×1 rectangle and an L-shaped piece. A property of the latter is the subject of the following theorem:

Theorem

A unit square has been removed from a 2ⁿ×2ⁿ board. Prove that the rest of the board can be tiled with L-shaped trominos.

The applet below may help you grasp a proof that is quintessential mathematical induction. You may click inside the applet to "remove" a square or on the "One step" button, to see how, in applet's view, the proof may evolve. Exponent n could be changed by clicking a little off the central line of the number at the bottom of the applet.

Proof

Copyright © 1996-2008 Alexander Bogomolny

The proof is so simple, its first step was made into a proof without words.

Remark 1

You can test your understanding of Golomb's theorem by trying to tile the board manually.

Remark 2

We may base the last step of the proof on the fact that a tromino can be covered with 4 twice as small copies of itself which makes it a rep-4 tile (a rep-tile variety):

Thus a 2^k×2^k board could be looked at as combining one big piece (green) of tromino and a smaller, 2^k-1×2^k-1 board with a 1×1 square removed.

References

1. B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, #40
2. S. Golomb, Two Right Tromino Theorems, in The Changing Shape of Geometry, edited by C. Pritchard, Cambridge University Press, 2003
3. R. Nelsen, Proofs Without Words II, MAA, 2000, p. 123

Copyright © 1996-2008 Alexander Bogomolny