# 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^{n}×2^{n} 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 with a spin control at the bottom of the applet.

What if applet does not run? |

|Activities| |Contact| |Front page| |Contents| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny

### Proof

The proof is by induction. For n = 1, the assertion is obvious. With a square removed from a 2×2 board, the remaining part is exactly an L-shaped tromino piece.

Assume the statement true for n = k-1 and let n = k. Draw the center lines of the 2^{k}×2^{k} board. The cut-off square lies in exactly one of the four thus obtained 2^{k-1}×2^{k-1} boards. We may remove one square from each of the other three boards by placing a tromino at the center of the 2^{k}×2^{k} board. The result is a tromino and four 2^{k-1}×2^{k-1} boards, each with a square removed - just a situation to apply the inductive hypothesis.

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

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

|Activities| |Contact| |Front page| |Contents| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny