hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Medium level:

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 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 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!

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.07
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!