44 Chapter 5

Question 35. What is the most efficient method of breaking the chocolate bar into squares,

using the fewest total number of breaks?

Let us be honest in our counting of what a break means; we are not allowed to break

two pieces off at once or break off an empty piece. To break a piece of chocolate means

to take a single connected piece of chocolate and separate it into two nonempty pieces by

cutting along one of the lines between the squares, following the line all the way across.

How would you break the chocolate bar? Does it matter how you do it? In fact, it does not.

Theorem 36. Breaking a chocolate bar into individual squares always takes exactly the

same number of steps, regardless of the breaking protocol that is followed.

Proof. Notice that each time we break a rectangle along an edge, we make two rectangles,

each a bit smaller than the original. Each break increases the number of rectangles by

exactly one. If the original piece of chocolate has n small squares, therefore, then after

n − 1 breaks, regardless of how the breaks are performed (as long as each break creates

exactly one new piece), there will be n pieces. And in this case, each piece must be a single

small square. So all methods of breaking the chocolate bar use the same number of breaks,

which is one less than the number of squares in the bar.

5.3 Tiling problems

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

Theorem 37. Every 2

n

×2

n

grid of unit squares, with one square removed, can be tiled by

L-shaped tiles consisting of three unit squares.