The Missing-Square Tromino Tiling, math that surprises you lesson

Remove any one square from a 4 by 4 board. Can the $15$ squares that are left be covered by L-shaped pieces of three squares each, with no overlaps and no gaps? The area fits, since $15 = 5 \cdot 3$ , but area alone did not settle the mutilated chessboard, so a real answer has to place the pieces. This page builds a tiling for every position of the missing square, on every board whose side is a power of $2$ , from one solved small case and one step that is repeated.

Key terms

Missing-square tromino tiling

Definition A tromino tiling of a region of grid squares, as the term is used here, is a collection of L-trominoes, each lying on three squares of the region, such that every square of the region is covered by exactly one of them. The missing-square tromino tiling theorem says that for every whole number $n \ge 1$ , if any one square is removed from a board of $2^n$ by $2^n$ squares, then the remaining $4^n - 1$ squares have a tromino tiling, and the tiling uses

\frac{4^n - 1}{3}

trominoes. The proof builds the tiling. A 2 by 2 board with one square missing is itself covered by one L-tromino. A larger board is cut into four quadrants of side $2^{n-1}$ , the missing square lies in exactly one of them, and one tromino is placed on the three squares at the center of the board that belong to the other three quadrants. Each quadrant then has exactly one square that is either missing or already covered, so it is a smaller board of the same kind and is tiled in the same way.

In plain words The missing square spoils one quadrant. One tromino at the center spoils each of the other three quadrants in the same way, so the big puzzle becomes four copies of the same puzzle at half the size.

Example Number the rows of a 4 by 4 board from $1$ at the top and the columns from $1$ at the left, and remove the square $(1, 2)$ in row $1$ and column $2$ . It lies in the upper left quadrant. The four squares touching the center of the board are $(2, 2)$ , $(2, 3)$ , $(3, 2)$ and $(3, 3)$ , one in each quadrant, so the central tromino covers $(2, 3)$ , $(3, 2)$ and $(3, 3)$ and leaves $(2, 2)$ to the upper left quadrant. In each quadrant three squares are then left, and they form an L-tromino.

Tromino	Squares it covers
Central	$(2, 3)$ , $(3, 2)$ , $(3, 3)$
Upper left	$(1, 1)$ , $(2, 1)$ , $(2, 2)$
Upper right	$(1, 3)$ , $(1, 4)$ , $(2, 4)$
Lower left	$(3, 1)$ , $(4, 1)$ , $(4, 2)$
Lower right	$(3, 4)$ , $(4, 3)$ , $(4, 4)$

The five trominoes cover $15$ different squares, all but $(1, 2)$ , in agreement with $(16 - 1)/3 = 5$ .

L-tromino

Definition An L-tromino is the shape made of three unit squares that form a 2 by 2 square with one of its four squares removed. Placed on a grid, it covers three of the four squares of some 2 by 2 block. Turning it by quarter turns gives four orientations, one for each square of the block that it leaves out. Flipping it over gives one of the same four, because the shape is symmetric about the diagonal of the block through its corner square, the square that touches both others. The only other shape made of three unit squares joined edge to edge is the straight tromino, a 1 by 3 bar.

In plain words Take a 2 by 2 square and leave out one of its squares. Every L-tromino on the grid looks like that, only turned.

Example A 2 by 2 board with one square missing is covered by exactly one L-tromino, whichever square is missing, because the three squares left form the orientation that leaves out that square. Two L-trominoes tile a 2 by 3 rectangle. With rows $1$ and $2$ and columns $1$ to $3$ , one covers $(1, 1)$ , $(1, 2)$ and $(2, 1)$ , and the other covers $(1, 3)$ , $(2, 2)$ and $(2, 3)$ .

Mathematical induction

Definition Mathematical induction proves that a statement $P(n)$ holds for every whole number $n \ge n_0$ . It has two parts. The base case shows that $P(n_0)$ is true. The inductive step shows that for every whole number $n \ge n_0$ , if $P(n)$ is true, then $P(n + 1)$ is true. The assumption that $P(n)$ holds, made inside the step, is called the induction hypothesis. Together the two parts give $P(n_0)$ , then $P(n_0 + 1)$ , then $P(n_0 + 2)$ , and so on for every whole number $n \ge n_0$ .

In plain words Prove the first case, then prove that each case brings the next one with it. Reaching the first rung of a ladder, and being able to climb from any rung to the next, gets you to every rung.

Example The tile count needs $4^n - 1$ to be a multiple of $3$ for every $n \ge 1$ . The base case holds because $4 - 1 = 3$ . For the step, suppose that $4^n - 1 = 3k$ for a whole number $k$ . Then

\begin{aligned} 4^{n+1} - 1 &= 4(4^n - 1) + 3 \\[0.4em] &= 3(4k + 1), \end{aligned}

which is again a multiple of $3$ . In the tromino theorem, $P(n)$ says that every board of side $2^n$ with one square missing has a tromino tiling. The base case $n = 1$ is the 2 by 2 board, and the step is the quadrant construction, which applies the induction hypothesis to each of the four quadrants of a board of side $2^{n+1}$ .

Divide and conquer

Definition Divide and conquer is a method that solves a problem by splitting it into smaller problems of the same kind, solving each of those by the same method, and combining their solutions. Problems that are small enough are solved directly instead of being split. A method that applies itself to smaller cases in this way is called recursive. It is sure to finish when every split produces strictly smaller problems, measured by a whole number such as the side of a board, and every problem of the smallest size is solved directly.

In plain words Cut the job into smaller copies of itself, keep cutting until the pieces are easy, and then put the answers together.

Example On an 8 by 8 board with the square $(2, 3)$ missing, the first split gives four 4 by 4 quadrants. The missing square is in the upper left quadrant, so the central tromino covers $(4, 5)$ , $(5, 4)$ and $(5, 5)$ , the central squares of the other three. Each 4 by 4 quadrant is then split into four 2 by 2 blocks with a central tromino of its own, and each 2 by 2 block, now with one square missing or covered, takes one tromino. That is $1$ tromino at the first level, $4$ at the second and $16$ in the blocks, so

1 + 4 + 16 = 21 = \frac{64 - 1}{3}.

The count for any size follows the same pattern. If $T(n)$ is the number of trominoes on a board of side $2^n$ , then $T(1) = 1$ and $T(n) = 4\,T(n - 1) + 1$ for $n \ge 2$ , because a board is four quadrants plus one central tromino.

Base case

Definition The base case of an induction is the first case $P(n_0)$ , which is proved directly rather than from an earlier case. In a recursive method the base cases are the smallest problems, which are solved without splitting further. An inductive step alone proves no case of the statement, and a recursion whose splits never reach a base case never finishes.

In plain words The base case is the small puzzle solved by hand that every larger solution is built from.

Example For the tromino theorem the base case is the 2 by 2 board, solved by one tromino for each of the four positions of the missing square. Halving a side of $2^n$ a total of $n - 1$ times gives exactly $2$ , so every chain of splits ends at this base case. The claim that $4^n + 1$ is a multiple of $3$ shows why the base case cannot be skipped. Its step works, since

4^{n+1} + 1 = 4(4^n + 1) - 3,

but its base case fails, because $4 + 1 = 5$ . In fact $4^n + 1$ leaves the remainder $2$ on division by $3$ for every whole number $n$ , because $4^n$ leaves the remainder $1$ .

Check yourself

On a 4 by 4 board, numbered as in the example, remove the square $(4, 2)$ instead. Which squares does the central tromino cover, and which squares do the other four trominoes cover?

Show the answer

The square $(4, 2)$ lies in the lower left quadrant, rows $3$ and $4$ and columns $1$ and $2$ . Its central square $(3, 2)$ is left alone, and the central tromino covers $(2, 2)$ , $(2, 3)$ and $(3, 3)$ . Each quadrant now has one square missing or covered, and its other three squares form a tromino.

Tromino	Squares it covers
Upper left	$(1, 1)$ , $(1, 2)$ , $(2, 1)$
Upper right	$(1, 3)$ , $(1, 4)$ , $(2, 4)$
Lower left	$(3, 1)$ , $(3, 2)$ , $(4, 1)$
Lower right	$(3, 4)$ , $(4, 3)$ , $(4, 4)$

Together with the central tromino these five pieces cover every square except $(4, 2)$ exactly once.

Extend the pattern to a 16 by 16 board with one square missing. How many trominoes does the tiling use, and how many of them are placed at each level of the construction?

Show the answer

The board has $256 - 1 = 255$ squares to cover, so the tiling uses $255/3 = 85$ trominoes. The first split places $1$ central tromino and gives four 8 by 8 quadrants. Each of those places $1$ central tromino of its own, $4$ in all, and gives four 4 by 4 boards. Each of these sixteen boards places $1$ central tromino, $16$ in all, and gives four 2 by 2 blocks. Each of the sixty-four blocks takes $1$ tromino. The total is

1 + 4 + 16 + 64 = 85,

which also follows from the rule for $T(n)$ , since $T(4) = 4 \cdot 21 + 1 = 85$ .

Change a number. A 5 by 5 board with one square missing has $24$ squares, a multiple of $3$ . Show that if the missing square is $(1, 2)$ , in row $1$ and column $2$ , the board has no tromino tiling. Mark the squares whose row and column are both odd and count them.

Show the answer

The marked squares have rows $1$ , $3$ or $5$ and columns $1$ , $3$ or $5$ , so there are $9$ of them, and $(1, 2)$ is not one of them. Every L-tromino lies inside a 2 by 2 block of two consecutive rows and two consecutive columns. One of those rows is odd and one of those columns is odd, so the block contains exactly one marked square, and a tromino covers at most one marked square.

A tiling of $24$ squares would use $8$ trominoes, which together cover at most $8$ marked squares. All $9$ marked squares are still on the board and need covering, so no tiling exists. The construction of this page does not apply either, since $5$ is not a power of $2$ and cannot be halved into equal quadrants. In fact a 5 by 5 board with one square missing has a tromino tiling exactly when the missing square is one of the nine marked squares.