Communications of the ACM
Last byte
Puzzled: Solutions and Sources
Solution. Charlie was able to break a five-by-nine-square-segment rectangular bar into its constituent squares using 44 breaks along its seams. But could he have done better? If you tried it yourself, you might conclude that he could not have done better, but also that he couldn't have done worse. Indeed, breaking only one piece at a time, Charlie is foreordained to make exactly 44 breaks.
Very smart people have been stumped by this puzzle, only to slap themselves on the forehead when they realized that every break increases the number of pieces of chocolate by one. Since there are 45 squares, there must be 44 breaks, no matter how they did it. In general, of course, given an m by n chocolate bar, the conclusion is that the required number of breaks is always mn −1.
2. Playing Chomp
Solution. Charlie's children, Alice and Bobby, play a game called Chomp in which they alternate eating a square together with every square northeast of the first square, trying to avoid eating the last square.
The game was invented (in a different form) in 1952 by Dutch mathematician Frederik "Fred" Schuh and independently in 1974 by the late mathematician and economist David Gale. The name "Chomp" was coined by an amateur mathematician, the great puzzle maven Martin Gardner. The proof that Alice can force a win is a classic strategy-stealing argument that goes like this: First, since the game is deterministic, full-information, and bounded in length, someone must have a winning strategy. Assume it's Bobby, and let square X be his winning reply to Alice's first move of biting off only the northeast corner square. But Alice could instead have begun by taking X (and everything northeast of X) on her first move, later adopting Bobby's winning strategy.
This contradiction shows it must have been Alice, not Bobby, who had the winning strategy.
3. Alice's Winning Strategy
This proof works for any m by n chocolate bar (as long as it has more than one square) but fails to reveal what Alice's winning strategy actually is. Subsequent work (such as at http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/chomp.html) has solved the three-row game, but still no one knows how Alice is able to win the game in general. Indeed, there may not be a general strategy that can be described in a simple way.
But, hey, you never know. The game Bridg-It, also invented by Gale and publicized by Gardner, had the same curious property: It could be proved that the first player had a winning strategy, though no such strategy is known. It was later produced and sold commercially as a board game by game publisher Hasbro. Mathematician Oliver Gross of the Rand Corporation then came up with an elegant winning strategy. Explore the game and that remarkable strategy at http://home.flash.net/~markthom/html/bridg-it.html.
So maybe Chomp has an elegant winning strategy after all. Meanwhile, if you find one, please tell the rest of us.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1666420.1666447
©2010 ACM 0001-0782/10/0300 $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.
No entries found