The chocolate bar problem

A brief excerpt from Proof and the Art of Mathematics

Consider next the chocolate bar problem. Imagine a rectangular chocolate bar, the kind having a pattern of small squares. We shall break the chocolate along these lines, in such a way that in the end we have only those tiny squares as separate pieces.

There are a variety of ways that we might do this. For example, for the bar pictured above, we could first make the three long breaks, making four 8 × 1 sticks, and then would break off one square at a time from those sticks. This would make 3 + 4⋅7 breaks altogether. Alternatively, we could first make all the short breaks, and then break off individual squares from the resulting 1 × 4 sticks, resulting in 7 + 8⋅3 breaks.

Question: What is the most efficient method of breaking the chocolate bar into squares, using the fewest total number of breaks?

This is a quick fun 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. I have strived to fill the book with interesting 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.

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

Selection from the chapter’s end:

Mathematical Habits

Generalize. After proving a statement, seek to prove a more general statement. Weaken the hypothesis or strengthen the conclusion. Apply the idea of the argument in another similar-enough circumstance. Unify our understanding of diverse situations. Seek the essence of a phenomenon.

Exercises

4. Prove that if the initial chocolate bar is a rectangle, then one always has rectangular pieces after every stage of the breaking process.

5. Generalize the chocolate bar theorem to nonrectangular chocolate bars.