rec.puzzles Archive

What is a winning strategy for the game "Chomp"?

competition/games/chomp New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

What is a winning strategy for the game "Chomp"?

You begin with a rectangular slab of chocolate that has m chocolate
squares per row and n chocolate squares per column.  Then, player A
chooses a square.  Suppose he chooses the square p columns from the
left and q rows from the bottom (having coordinates (p,q)).  Then
player A eats all squares with coordinates (s,t) where s>=p and t>=q.
Then player B picks a square from those remaining and similarly eats
all squares up and right of the one he chooses.  A and B take turns
respectively until all the squares have been taken.  The object of the
game is not to eat the lower left square of the slab, which is
poisoned.

Player A will always have a winning strategy unless m=n=1.  It's
relatively easy to find the winning strategies for those cases where
m=n, or either m or n equals 1 or 2.  Can you find a winning strategy
for when n=3, or better yet, a general winning strategy?

Of course, the initial slab of chocolate need not have only 2
dimensions.  It can have 3 dimensions, or more.

-- Lucky
Show solution
There is a discussion about winning strategies in (inevitably) Winning
Ways (Berlekamp, Conway and Guy) pages 598--600 which give a variety of
strategies for the two-dimensional problem and the arithmetic parallel
for more than two dimensions.

It may save your stomach from eating too much chocolate!

-- David K Smith <D.K.Smith@exeter.ac.uk>