Chomp is played on an m by n grid. A move names a square and removes it together with everything above and to the right of it. The player forced to take the bottom left square loses. Show that the first player wins on every grid other than 1 by 1, without exhibiting a winning move.

Chomp is played on an m by n grid. A move names a square and removes it together with everything above and to the right of it. The player forced to take the bottom left square loses. Show that the first player wins on every grid other than 1 by 1, without exhibiting a winning move.

Approach: Assume the opposite and consider what happens after the opening move that removes only the top right square, then ask whether the opponent's reply could have been played first.

The first player wins on every board other than 1 by 1, by strategy stealing. Chomp is a finite game with no draws, so exactly one player has a winning strategy. Suppose it were the second player. Let the first player open by removing only the top right square. By assumption the second player has a winning reply R from that position. Playing R directly on the full board removes the top right square as well, so it reaches the same position, with the roles of the players swapped. So the first player could have played R as his opening and would then hold the winning position, contradicting the assumption. Hence the first player has a winning first move. The argument names no move, and for general m by n grids no explicit winning strategy is known, while for square boards the opening is the square diagonally next to the corner.

Follow-up: For a 2 by n Chomp board, what is the explicit winning first move and how is it maintained?

Key concepts: strategy stealing, finite game, winning strategy.