56 Chapter 5

5.4 Prove that if the initial chocolate bar in theorem 36 is a rectangle, then one always has rectan-

gular pieces after every stage of the breaking process.

5.5 Generalize the chocolate bar theorem (theorem 36) to nonrectangular chocolate bars.

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

5.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?

5.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.

5.9 Prove or refute the following statement: If you place a chessboard pattern on an n ×m rectan-

gular grid, there will be an equal number of dark and light squares. Generalize your answer as

much as you can.

5.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?

5.11 Give an alternative proof of theorem 41 by induction. [Hint: Consider how to generate repre-

sentations of n + 1 from representations of n.]

5.12 In the Escape! game, is it possible to fill as much as desired of the plane outside of the original

L-shape? For example, can one make sure for any given n that all squares in the n × n square,

except possibly the original L-shape, have a stone?

5.13 Consider a version of the Escape! game on a finite n × n board, modifying the rules so that

stones that would have been placed outside this region are simply not placed. For which values

of n can you vacate the yellow corner? For which values of n can you vacate the entire board?

5.14 Show that in the n×n version of Escape!, you cannot lose: every sequence of legal moves leads

eventually to a completely vacated board. [Hint: Show first that a nonempty board always has

a legal move; next, show by induction from the lower left that every square can be activated

only finitely many times. So there is no infinite play, and therefore the board must become

empty at a finite stage of play.]

5.15 (Challenge) Show that the number of steps to vacate the n × n board does not depend on the

particular sequence of moves that are made. The game always ends with an empty board in

exactly the same number of steps regardless of how the plays are made.

Credits

Theorem 37 is due to Solomon Golomb (1954), who also investigated similar tilings of

many other shapes. Theorem 41 was observed in 1951 by Arthur B. Brown of Queens Col-

lege and proved by William Moser of the University of Toronto. The pointing-at painting

is David and Charles Colyear by Sir Godfrey Kneller, in the public domain via Wikime-

dia Commons. The Escape! game is due to Maxim Kontesevic and was discussed on the

Numberphile video series at https://www.youtube.com/watch?v=lFQGSGsXbXE&t=11s.