# L-Tiling Problem

Nov 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 2^{n} × 2^{n} 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**

^{n}× 2^{n}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

^{1}× 2

^{1}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

^{n}× 2

^{n}grid with any one square removed (Figure 3) can be tiled with L-shaped tiles. Given this assumption, we must show that a 2

^{n+1}× 2

^{n+1}grid with one square removed can be tiled with L-shaped tiles.

By the definition of exponentiation, 2

^{n+1}× 2

^{n+1}= 2

^{n}× 2

^{n}× 2 × 2 = 2

^{n}× 2

^{n}× 4. In other words, a 2

^{n+1}× 2

^{n+1}grid is composed of four 2

^{n}× 2

^{n}grids (quadrants) as seen in Figure 4.

By our assumption, the 2

^{n}× 2

^{n}quadrant that includes the missing square can be tiled by L-shaped tiles. We can now imagine the 2

^{n}× 2

^{n}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

^{n}× 2

^{n}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

^{n}× 2

^{n}grid with any one square removed can be tiled with L-shaped tiles, fulfills.

Thus, a 2

^{n+1}× 2

^{n+1}grid with one square removed can be tiled by L-shaped tiles.

By induction, any 2

^{n}× 2

^{n}grid with one square removed can be tiled by L-shaped tiles.