rinum Mohammed Munir Ahmed

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 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)?
Figure 1
L-shaped Tile


Figure 2
21 × 21 Base Case
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.


Figure 3
2n × 2n Case
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.

Figure 4
2n+1 × 2n+1 Case

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.

Figure 5
Inductive Step

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.
© 2014 rinum

Location : Chicago, IL
Email : [email protected]
About : On rinum.com, I post my thoughts and track my work.

I am currently a pharmacy student at the University of Illinois at Chicago. Before that, I received my Bachelor of Science in Mathematics and Computer Science.

In case you were wondering, rinum is my middle name reversed.