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)³ unit cubes. Prove that if one unit cube is removed from T, then the remaining solid can be decomposed into pieces.

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.

Let us first visualize a tiling with the corner square uncovered.

Base case: 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.

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.