When reading this Quanta article about the Fields Medal recipient Yu Deng, I came across this paragraph:
On some of those hikes, his father gave him math problems to solve. He still remembers one: You have a square grid divided into a certain number of cells. Prove that if you remove any one cell from the grid — it doesn’t matter which — you can always perfectly divide the rest of the grid into L-shaped pieces made from three cells each. The solution, which Deng figured out, required a concept known as induction, usually taught in high school. Deng was 7 years old.
I asked Gemini about its solution and this was its response:
This classic tiling puzzle is formally known as Golomb’s Tromino Theorem. For this division to be guaranteed regardless of which cell you remove, the grid must specifically be a square of dimensions \(2^n \times 2^n\), where \(n\) is any positive integer (\(2 \times 2\), \(4 \times 4\), \(8 \times 8\), and so on).
Before diving into the mechanics, notice the foundational arithmetic that makes this possible: a \(2^n \times 2^n\) grid contains \((2^n)^2 = 4^n\) total cells. When you remove any one cell, you are left with \(4^n - 1\) cells. Because \(4^n \equiv 1 \pmod 3\) for all positive integers \(n\), the quantity \(4^n - 1\) is always perfectly divisible by \(3\). This guarantees that the remaining area at least has the potential to be covered by \(3\)-cell L-shaped tiles (trominoes) without any left-over space.
The Mathematical Induction Proof
The beauty of the induction approach lies in a clever divide-and-conquer strategy that reduces any large grid down to simple \(4\)-cell squares.
Step 1: The Base Case (\(n = 1\))
Consider the smallest possible power-of-two grid: a \(2^1 \times 2^1 = 2 \times 2\) square containing \(4\) cells. If you remove any one cell from a \(2 \times 2\) grid, the remaining \(3\) cells naturally form an L-shape. A single L-tromino covers this remaining area perfectly. The base case holds.
Step 2: The Inductive Hypothesis
Assume that for some arbitrary positive integer \(k\), any \(2^k \times 2^k\) grid with a single cell removed can be tiled completely by L-trominoes without overlapping or hanging off the edges.
Step 3: The Inductive Step (\(n = k + 1\))
Now consider a larger grid of size \(2^{k+1} \times 2^{k+1}\). We must prove it can also be tiled if any single cell is removed.
- Divide into Quadrants: Slice the \(2^{k+1} \times 2^{k+1}\) grid horizontally and vertically through its center. This divides the board into four equal quadrants, each of size \(2^k \times 2^k\).
- Locate the Missing Cell: The single removed cell must lie inside exactly one of these four quadrants. We will call this the deficient quadrant. Because this deficient quadrant is a \(2^k \times 2^k\) grid missing exactly one cell, our inductive hypothesis guarantees that we can tile it completely with L-trominoes!
- The Center Trick: We are now left with three intact \(2^k \times 2^k\) quadrants that have no missing cells. To apply our hypothesis to them, take one single L-tromino and place it squarely at the exact center intersection of the overall board. Orient this tile so that it covers exactly one corner cell of each of the three non-deficient quadrants—specifically, the three innermost corners that meet at the center of the board.
- Recurse: By placing that one central tromino, we have effectively "removed" one cell from each of the three remaining quadrants. Now, all four quadrants are independent \(2^k \times 2^k\) grids that are each missing exactly one cell!
- By our inductive hypothesis, all four quadrants can now be tiled perfectly by L-trominoes. Therefore, the entire \(2^{k+1} \times 2^{k+1}\) grid minus one cell is successfully tiled.
 |
Figure 1 |
