Chomp 4

After beating your friend at his game 3 times already, you wonder if there’s always a way to win for an $n$ by $m$ chocolate bar. As a reminder, here are the rules of the game:

You’re given a chocolate bar made of $n$ by $m$ squares.
You and another person will take turns picking a square of chocolate to eat, then eating all the squares to the top, the right, and top-right of the chosen square.
You must eat at least one square on your turn, and you cannot skip your turn.
Whoever eats the mouldy square loses.

Should you go first or second? Does this decision depend on the dimensions of the chocolate bar?

Hint

Solving the general form of the game is very difficult. We don’t know how to find a general solution beyond brute force.

Solution

You’ll always want to go first.

Let’s call the players A and B, with player A going first. We want to show that player A will always win with the “Strategy-stealing” argument.

Let’s assume the opposite: that player B can always win, no matter what moves player A performs. For the first move, player A takes the top-right square. By definition, player B will have an optimal response that puts player A in a losing position.

However, any move that player B makes at this point is also something that player A could’ve taken on his first move, leaving the board in the exact same losing state to player B.

This contradicts our earlier assumption that player B can always win, and proves that the first player always wins.

Previous puzzle in this series

Chomp 3

Try These Next

Planting Trees 2

Coin Weighing 2

Proving Rules on Cards