L-Tiling ProblemNov 20, 2012
One of my favorite problems I encountered in my mathematical proofs class was the L-tiling problem. Along with teaching mathematical induction, it often leads to more difficult questions. What happens if we use a different tile shape? How many unique tiling patterns are there for any 2n × 2n grid? What if we were able to use more than 1 tile shape and had to minimize the number of shapes used?
The L-tiling problem asks the following question: Given a positive integer, n, can any 2n × 2n grid with one square removed be tiled with L-shaped tiles (Figure 1)?
First, we look at the base case where n = 1 to see if a 21 × 21 grid with one square removed can be tiled with L-shaped tiles (Figure 2). Since the base case can be tiled with L-shaped tiles, the base case holds true.
Let us assume that a 2n × 2n grid with any one square removed (Figure 3) can be tiled with L-shaped tiles. Given this assumption, we must show that a 2n+1 × 2n+1 grid with one square removed can be tiled with L-shaped tiles.
By the definition of exponentiation, 2n+1 × 2n+1 = 2n × 2n × 2 × 2 = 2n × 2n × 4. In other words, a 2n+1 × 2n+1 grid is composed of four 2n × 2n grids (quadrants) as seen in Figure 4.
By our assumption, the 2n × 2n quadrant that includes the missing square can be tiled by L-shaped tiles. We can now imagine the 2n × 2n part with the missing square to be filled. Our next move would be to place an L-shaped tile in the center of our grid as shown in Figure 5. This allows us to examine each of the remaining unfilled 2n × 2n quadrants.
When looking at the remaining quadrants, we notice that exactly 1 square is filled in each quadrant as a result of our centrally placed L-shaped tile. We can imagine these squares to be "missing" in order to transform each quadrant into a situation which our assumption, a 2n × 2n grid with any one square removed can be tiled with L-shaped tiles, fulfills.
Thus, a 2n+1 × 2n+1 grid with one square removed can be tiled by L-shaped tiles.
By induction, any 2n × 2n grid with one square removed can be tiled by L-shaped tiles.