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>