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://
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://
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 email@example.com.
Peter Winkler ( firstname.lastname@example.org) is Professor of Mathematics and of Computer science and Albert bradley Third
Century Professor in the sciences at Dartmouth College, hanover, nh.