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

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

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