Chomp 3

Even after losing the previous 2 games to you, it appears that your friend has not yet learnt his lesson. This time, he has a rectangular chocolate bar made of $2$ by $n$ squares. The same rules apply:

You 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? And how will you ensure that you don’t eat the mouldy square?

Solution

Choose to go first, eating the top-right square.

Based on your friend’s move, respond accordingly:

If he eats a square on the bottom row, this will leave a smaller rectangle. Eat the new top-right square.
If he eats only squares on the top row, eat the same number of squares from the bottom row.

Whichever move your friend makes, you can always bring it back to the following configuration when it is your friend’s turn: $k$ squares on the top row, $k + 1$ squares on the bottom row.

Each pair of moves also reduces the value of $k$ , ensuring that you’re eventually left with $k = 0$ , meaning your friend will be left with the mouldy chocolate.

Extension

After a few games with $2$ by $n$ chocolate bars, your friend protests: “Hey! I’ve realised you win every time you go first. It’s my turn to go first.”

You let him go first the next round. However, his first move isn’t taking the single top-right square. Show that if the first player doesn’t take the single top-right square on their first move, the second player always wins in optimal play.

Solution

Let’s consider 2 cases:

Case 1: Player 1 takes the $k^{th}$ $k^{th}$ square from the right on the bottom row, taking a total of $2 k$ $2 k$ squares.
- The chocolate bar is now a $2$ by $m$ chocolate bar, where $m = n - k$ . We’ve already solved this earlier: player 2 can now take the top-right square to leave player 1 in a losing position.
Case 2: Player 1 takes $k$ $k$ squares from the top row, where $k > 1$ $k > 1$ .
- Player 2 can take $k - 1$ squares from the bottom row, turning it into a $2$ by $m$ chocolate bar with the top-right square eaten, where $m = n - k + 1$ . That’s a losing position for the next player (i.e. player 1).

If Player 1 doesn’t make the optimal move on their first move, player 2 can always win.

Previous puzzle in this series

Chomp 2

Next puzzle in this series

Chomp 4

Try These Next

Equal Shape Cutting 1

Antipodal Temperature and Pressure

9 Dots