Can all but one square of an n by n chessboard be covered by L-shaped trominoes?
In general, it may not be possible, but if n is a power of 2, it can! See the Figure for an 8×8 example.
Is there a method for finding such a tiling? Yes, and we can find it by induction!
Presentation Suggestions:
This is a terrific application of induction. Ask students to try to tile an 8×8 or a 16×16 board with L-shaped tiles before showing them this proof.
The Math Behind the Fact:
A simple proof by induction shows this property. The simplest case is a 2×2 chessboard. Clearly if one square is removed, the remainder can be tiled by one L-shaped tromino. This is the base case.
Now, given a large chessboard of size 2nx2n, with one square removed, it can be divided into four 2(n-1)x2(n-1) smaller chessboards (the corners of the original board). One of those corners contains the removed tile, so by the inductive step, it can be tiled by L-shaped trominoes. Now notice that the remaining three 2(n-1)x2(n-1) boards all meet at a common corner at the center of the original board.
The 3 corner tiles there form an L-shaped set that can be covered by one tromino! And by removing them, those 3 chessboards each have a tile removed, and by the inductive step they can be tiled by trominoes as well! Thus we have covered the entire chessboard (apart from the removed square) by trominos!
This proof actually leads to a method for constructing such a tiling, by successive applications of induction. As an example, consider Figure 1 above without any tiling and with one square removed (here, the black square). We divide the board into four 4×4 boards, one in each quadrant. The bottom left board can be tiled by the inductive step, because it has a square removed. And in the three other boards, we can cover the corner squares where they meet by a single L-shaped tromino (here, orange). These three 4×4 boards will then have a single tile removed, hence by the inductive step they can be tiled too.
But how can each of these 4×4 boards with a square removed be tiled? We apply our inductive method again, cutting each into four 2×2 boards: one of which has a square removed, and the other three of which don’t have a square removed. Cover their 3 center tiles by a (green) tromino. What remains uncovered are 2×2 boards with a square removed… these can easily be covered by (red and green) trominoes!
How to Cite this Page:
Su, Francis E., et al. “Inductive Tiling.” Math Fun Facts. <https://www.math.hmc.edu/funfacts>.
Fun Fact suggested by:
Arthur Benjamin