last byte
DOI: 10.1145/1646353.1646380
Peter Winkler
Puzzled
Breaking chocolate Bars
Welcome to three new puzzles. Solutions to the first two will be published
next month; the third is (as yet) unsolved. In each, the issue is how your intuition
matches up with the mathematics.
1.Charlie needs to break up chocolate bars in the process of baking s’mores for his children and their friends. Each
bar is a rectangle scored into a five-by-nine array of squares. To
break a bar into small squares, Charlie repeatedly picks up a
single piece of chocolate and cracks it along a line (see Figure 1).
Charlie breaks up the first bar by first cracking it along its
longest lines, resulting in five strips of nine squares each. He
then dismantles each strip, square by square, for a total of
4 + 5 × 8 = 44 breaks. He breaks up the second bar the opposite
way, first into eight strips of length five, then breaking up these
strips for a total of 8 + 9 × 4 = 44 breaks, again. Darn. Can Charlie
do better? What’s the smallest number of breaks Charlie needs
to reduce a chocolate bar to its constituent squares?
figure 1. charlie’s first bar at the beginning,
after four breaks, and after 12 breaks.
2.Charlie’s children, Alice and Bobby, steal one of the bars and agree to play the following game: They place the bar
on the table with its rows of nine squares aligned east-west
(see Figure 2). Alice chooses any square and eats it, along with
all the squares to the northeast (including straight north or
east) of the chosen square. Bobby then chooses some remaining
square and eats it, again along with all remaining squares to
the northeast. The two then continue to alternate until the bar
is completely gone.
Alice could have started with the square at the southwest
corner of the bar and thus consumed the whole bar in her first
turn. But that square happens to be rotten. The object of the
game is to force your opponent to eat the last square.
Prove that Alice indeed has a winning strategy.
figure 2. A possible opening move for
Alice, and reply by Bobby.
a
b
3.What strategies enable Alice to win the game on any rectangular chocolate bar with more than a single
square of chocolate?
c
Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.
Peter Winkler ( puzzled@cacm.acm.org) is Professor of Mathematics and of computer Science and albert
bradley third century Professor in the Sciences at Dartmouth college, hanover, Nh.