Mudd Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2007 by Francis Su
You can now subscribe to our RSS feed to get the latest Fun Facts!
Get a random Fun Fact!
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

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

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

Inductive Tiling

Figure 1
Figure 1

Can all but one square of an n by n chessboard be covered by L-shaped trominoes?

In general, it can not necessarily be done, 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:
Ask students to try to tile an 8x8 or a 16x16 board with L-shaped tiles before showing them the 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.

So, given a chessboard of size 2nx2n, with one square removed, it can be divided into four 2(n-1)x2(n-1) smaller chessboards, one of which contains the removed tile.

In the remaining three 2(n-1)x2(n-1) boards, we'll remove a tile from each by taking the adjacent center corners of the three to give an L-shaped hole.

The inductive hypothesis will show how to cover the four smaller boards, since they each have a square removed, and are size 2(n-1)x2(n-1). The L-shaped hole can also be covered by a tromino. This covers the original board except for the original missing square!

In Figure 1 above, applying the inductive step removes the yellow tiles near the center of the 8x8 board. The 8x8 is divided into 4 quadrants, each with a square missing. Then applying the inductive step removes the green tiles near the center of each 4x4 quadrant. This gives several 2x2 boards with a square removed---the base case!

How to Cite this Page:
Su, Francis E., et al. "Inductive Tiling." Mudd Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

Bookmark this page on: | Digg this! | Del.icio.us | Technorati | Reddit | Fark | Squidoo | Furl | Blinklist | Yahoo MyWeb | Google | Stumbleupon |

Keywords:    combinatorics
Subjects:    combinatorics
Level:    Medium
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
4.58
 
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!

Want another Math Fun Fact?

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