Tiling problems

A selection from Proof and the Art of Mathematics

Consider next a tiling problem using small L-shaped tiles on a large board.

Theorem 37. Every 2ⁿ × 2ⁿ grid of unit squares, with one square removed, can be tiled by L-shaped tiles consisting of three unit squares.

Proof: We prove this by induction on n. The claim is clear when n = 0, since in this case we have a 1 × 1 grid, with only one square, and when we remove it, we can tile what remains with no tiles at all. (The case n = 1, or a 2 × 2 grid, is similarly trivial, since when you remove one of the squares, what is left is perfectly covered by a single tile.)

Suppose now by induction that the statement is true for a number n, and consider a 2ⁿ⁺¹ × 2ⁿ⁺¹ grid of unit squares, with one unit square removed. Since 2ⁿ⁺¹ is even, we may divide the large square into four 2ⁿ × 2ⁿ quadrants. The omitted square resides in one of them. Place a single tile near the center, oriented so that it covers one corner square from each of the other three quadrants, as indicated:

If we now think of the smaller quadrants separately, we have four smaller quadrants, each with one square removed. By the induction hypothesis, these can each be tiled with the L-shaped tiles. Together with our initial center tile, we thereby produce a tiling of the whole square. So all such grids with one square omitted can be tiled. □

Consider next the collection of shapes, similar to those in the popular game Tetris, that can be formed from four unit squares. There are five such shapes, pictured above.

Question 38: Can you arrange these shapes to form a rectangle?

For example, can you tile a 4 × 5 rectangle with these shapes, using one tile of each type? Give it a try!

Interlude

This is a brief excerpt from chapter 5 of my book Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing for aspiring mathematicians who want to learn how to write proofs. The book is filled with compelling mathematical statements having interesting elementary proofs.

Proof and the Art of Mathematics has been awarded the 2024 Daniel Solow Author’s Award by the Mathematical Association of America, awarded for outstanding and impactful contributions to mathematics education.

Did you try it? The answer is no, one cannot tile a rectangle with these shapes.

Theorem 39. The collection of tiles, with one of each tile shape type above, cannot tile a rectangle.

Proof: Suppose that we could tile a rectangle using exactly one of each type of those tile shapes. Since we have five shapes, each with area four, the total area is twenty, and so the possible size rectangles are 4 × 5, 2 × 10, or 1 × 20. One can see easily that the latter two rectangles are impossible, but our argument works generally, and so there is no need to argue separately for that case. Imagine that we have such a tiling of the rectangle. Let us place a chessboard pattern on the rectangle, and note that there are equal numbers of dark and light squares (but see also exercise 9).

This chessboard pattern will induce a chessboard pattern on each of the pieces. Namely, if we could arrange the pieces to form the rectangle, then they would each inherit a light-square/dark-square pattern from the global chessboard pattern.

The thing to notice, however, is that each of the individual tiles would have exactly two dark squares and two light squares, with the exception of the final inverted T-shaped piece, which has three dark squares and one light square, or possibly three light squares and one dark square, depending on how it should happen to land on the chessboard pattern. This means that there cannot be a tiling of the rectangle, because on the one hand, the number of light and dark squares on the rectangle is equal, but when you think about the individual tiles, the problematic green tile will prevent the light and dark squares from balancing. So there can be no tiling. □

Selections from the chapter’s end:

Mathematical Habits

Recognize when you have a proof and when you do not. This is an important, difficult step in one's mathematical development. Unfortunately, beginners are sometimes satisfied by an argument that experienced mathematicians will say is nonsense. Perhaps the attempted argument makes unwarranted assumptions, or misuses terms, or does not logically establish the full conclusion, or perhaps it makes any number of other mathematical errors, without the beginner realizing this. Therefore, be honest with yourself in your work; be skeptical about your argument; avoid talking nonsense. If you are not sure whether you have a proof, then you probably do not. Verify that your arguments logically establish their conclusions. Do not offer hand-waving arguments that avoid difficult but essential details. Never offer arguments that you do not understand.

Exercises

6. Is the conclusion of the theorem 37 true for n × n squares in general? Why or why not?

7. Explain how the proof of theorem 37 provides a construction method for producing the desired tiling. (Namely, once a given square is omitted, then perform the division into quadrants, place the one tile, and iterate with the smaller squares.) What tiling do you get this way for the 16 × 16 grid shown in the illustration?

8. Prove that the collection of shapes pictured before theorem 39 is indeed the collection of all shapes in the plane, freely allowing rotations and reflections, that can be formed from four unit squares by joining them at vertices along their edges.

9. Prove or refute the following statement: If you place a chessboard pattern on an n × m rectangular grid, there will be an equal number of dark and light squares. Generalize your answer as much as you can.

10. In the context of theorem 39, suppose that you have three pieces of each shape. Can you now tile a rectangle? Can you tile a 10 × 10 square with five tiles of each type?