Chomp

Problem:

Alice and Bob take turns in playing the following game on a rectangular chocolate board, with Alice playing first.

The player on move chooses a square on the board and takes it, along with all other squares in the north-east quadrant from it. The player who is forced to take the bottom left square loses the game.

Who has a winning strategy?

Solution

We prove that Alice has a winning strategy. Suppose not. Then in particular, if Alice takes the top right square, Bob would be in a winning position. Therefore, he has a move with which he can in turn place Alice in a losing position.

However, Alice could have played that move as her first move already, thus placing Bob in a losing position right after her first move. This is a contradiction, as we assumed that the initial position was a losing position.

Schematically, if a “+” represents a winning position and a “-” represents a losing position, then under the assumption that Bob has a winning strategy, we have the following diagram, leading to a contradiction:

This problem was discussed in the ETH Math Youth Academy.