acm-header
Sign In

Communications of the ACM

Last byte

Puzzled: Breaking Chocolate Bars


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
broken chocolate bars

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?

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.

3. What strategies enable Alice to win the game on any rectangular chocolate bar with more than a single square of chocolate?

Back to Top

Author

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.

Back to Top

Footnotes

Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

DOI: http://doi.acm.org/10.1145/1646353.1646380

Back to Top

Figures

F1Figure 1. Charlie's first bar at the beginning, after four breaks, and after 12 breaks.

F2Figure 2. A possible opening move for Alice, and reply by Bobby.

Back to top


©2010 ACM  0001-0782/10/0200  $10.00

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.


Comments


Nikolay Kurtov

The first puzzle is really trivial. A simple program and basic induction ideas allow to solve it quickly.
Puzzles 2 and 3 are more difficult and really interesting :)


Displaying 1 comment

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • Article
  • Author
  • Footnotes
  • Figures