Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Tiling a Chessboard with Trominoes

Puzzle

Show that a chessboard of size 2^n by 2^n can be tiled with L-shaped figures of 3 squares, such that only one square remains uncovered. In fact, the uncovered square may be any square — for every choice, there exists a tiling. In fact, the puzzle may be extended to 3D: Eight unit cubes make a cube with edge length two. We will call such a cube with one unit cube removed a "piece". A cube with edge length 2^n consists of (2^n)3 unit cubes. Prove that if one unit cube is removed from T, then the remaining solid can be decomposed into pieces.

Source

First proved by Solomon W Golomb in Checker Boards and Polyominoes, American Mathematical Monthly, 61 (1954), 675-682. The proof is admired for its ingenious use of induction.

Solution

Let us first visualize a tiling with the corner square uncovered. For a board of size 2 x 2, one L-shape suffices. Induction step: put 3 boards of size 2^n by 2^n next to each other such that their corner squares form an L-shape. Put a fourth board of size 2^n by 2^n so that the corner square of the resulting 2^(n+1) by 2^(n+1) board is in its corner. That proves the induction step. Now, let us visualize how we can move the uncovered square to any square of our choice through a series of "rotations". Given an 2^(n+1) by 2^(n+1) board with a corner square removed, identify which of the four 2^n by 2^n boards that compose the 2^(n+1) by 2^(n+1) board contains the target square. Then rotate the 2^(n+1) by 2^(n+1) board clockwise so that the correct 2^n by 2^n board contains the uncovered square. Now, focus on the 2^n by 2^n board and rotate it appropriately, and so on.

Followup

Tiling Deficient Rectangles with Trominoes (PDF) by J Marshall Ash and S W Golomb, Mathematics Magazine, 77(1), 46-55.

The Tromino Puzzle by Norton Starr contains history of the puzzle and extensive bibliography.

(A) An 8x8 chessboard has had two of its diagonally opposite squares removed, leaving it with sixty-two squares. Can we tile it with 31 non-overlapping 2x1 rectangles (dominoes) such that all squares are covered? (B) Under what circumstances would removal of two squares from an 8x8 chessboard allow such a tiling? For example, if we remove an arbitrary white square and an arbitrary black square, can the remaining board be tiled?

A set of fuel dumps on a circular racetrack have just enough gasoline for one car to make one round trip. Prove that there exists a fuel dump from which one car, starting with an empty gas tank, can complete the round trip.

12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.