L-Tiling Problem

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 2ⁿ × 2ⁿ 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 2ⁿ × 2ⁿ 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 2¹ × 2¹ 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 2ⁿ × 2ⁿ grid with any one square removed (Figure 3) can be tiled with L-shaped tiles. Given this assumption, we must show that a 2ⁿ⁺¹ × 2ⁿ⁺¹ grid with one square removed can be tiled with L-shaped tiles.


By the definition of exponentiation, 2ⁿ⁺¹ × 2ⁿ⁺¹ = 2ⁿ × 2ⁿ × 2 × 2 = 2ⁿ × 2ⁿ × 4. In other words, a 2ⁿ⁺¹ × 2ⁿ⁺¹ grid is composed of four 2ⁿ × 2ⁿ grids (quadrants) as seen in Figure 4.

By our assumption, the 2ⁿ × 2ⁿ quadrant that includes the missing square can be tiled by L-shaped tiles. We can now imagine the 2ⁿ × 2ⁿ 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 2ⁿ × 2ⁿ 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 2ⁿ × 2ⁿ grid with any one square removed can be tiled with L-shaped tiles, fulfills.

Thus, a 2ⁿ⁺¹ × 2ⁿ⁺¹ grid with one square removed can be tiled by L-shaped tiles.
By induction, any 2ⁿ × 2ⁿ grid with one square removed can be tiled by L-shaped tiles.