last byte

DOI: 10.1145/1666420.1666447
Peter Winkler
Puzzled
Solutions and Sources
Last month (February 2010, p. 120) we posted a trio of brainteasers,
including one as yet unsolved, concerning the breaking of a bar of chocolate.

1.making S’mores. 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/ma-marim/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.

 

All readers are encouraged to submit prospective puzzles for future columns to [e-mail].

Peter Winkler ( [e-mail]) is Professor of Mathematics and of Computer science and Albert bradley Third Century Professor in the sciences at Dartmouth College, hanover, nh.