Inductive Tiling

Figure 1

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 8x8 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 8x8 or a 16x16 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 2x2 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 2ⁿx2ⁿ, 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 4x4 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 4x4 boards will then have a single tile removed, hence by the inductive step they can be tiled too.

But how can each of these 4x4 boards with a square removed be tiled? We apply our inductive method again, cutting each into four 2x2 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 2x2 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. <http://www.math.hmc.edu/funfacts>.

Keywords:    combinatorics Subjects:    combinatorics Level:    Medium Fun Fact suggested by:   Arthur Benjamin Suggestions? Use this form. 4.01 current rating Click to rate this Fun Fact...     *   Awesome! I totally dig it!     *   Fun enough to tell a friend!     *   Mildly interesting     *   Not really noteworthy and see the most popular Facts! Get the Math Fun Facts iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!