Math Detours · Grade 8 · Around the corner · 22

Strategy stealing

In Chomp the first player can always win, and we can prove it without knowing how. The strangest kind of proof.

Name ____________________Date ____________

Tonight's idea

Chomp is played on a bar of chocolate whose bottom-left square is poisoned. On your turn you pick a square and eat it, together with every square above it or to its right. Whoever is left with only the poison must eat it, and loses.

S poison eat S and everything above or right of it these squares stay
One move on a \(5 \times 3\) bar: eating \(S\) removes it and the five dashed squares, six at once.

Claim: on any bar bigger than \(1 \times 1\), the first player can force a win. We will prove it without saying what the winning move is.

Chomp cannot draw and must end, so every position is a win or a loss for the player about to move; a winning move leaves the opponent a losing one. Consider eating only the top-right square. If that is a winning move, we are done. If not, the second player has a winning reply: eat some square \(S\). But eating \(S\) from the full bar removes the top-right square anyway, so it leaves exactly the position that "top-right, then \(S\)" leaves, with the second player facing it. The first player steals the reply.

Either the top-right nibble wins, or the second player's answer to it would have. Either way the first player has a winning first move.

The proof never says which move wins. For big bars nobody knows.

Watch one: a \(2 \times 4\) bar, and a strategy you can state

Call the first player A and the second B. A eats the top-right square: bottom row 4, top row 3. From now on A keeps the bottom row exactly one square longer than the top.

Say B eats the second square of the top row, so the top row is 1. A eats the third square of the bottom row: bottom 2, top 1. If B eats the last top square, A eats the second bottom square and leaves the poison alone. If B eats the second bottom square instead, only the poison and the top square remain, and A eats the top square. Every road ends with B holding the poison.

Play against a computer that searches every line: mathdetours.com/demos/chomp.html.

Your turn

  1. The bar is a single row of \(n \ge 2\) squares. Who wins, and with what move?
  2. A \(2 \times 5\) bar. A eats the top-right square, leaving bottom 5, top 4. B then eats the third square of the top row, so the top row is 2 squares long. What should A eat? State the rule A follows for the rest of the game, and explain why B, not A, ends up with the poison.
  3. A \(4 \times 4\) bar. Find A's winning first move and describe the strategy that follows it. Hint: look for a position with a symmetry A can copy.
  4. A \(3 \times 3\) bar. Suppose A opens badly by eating only the top-right square. Find B's winning reply, and check that it leaves exactly the position A could have made in one move from the full bar. Which step of tonight's proof is this?

Stretch: noughts and crosses on any board

Play noughts and crosses on a board of any size, with any winning-line length. Show that the second player cannot have a winning strategy. Hint: if they did, the first player could put one mark anywhere, then follow the second player's strategy as if that mark were not there. Why can a spare mark never hurt?

Answers

  1. The first player wins by eating the square next to the poison, which takes the whole row except the poison. The second player must eat it.
  2. A eats the fourth square of the bottom row, leaving bottom 3, top 2. The rule: after each of A's moves the bottom row is exactly one longer than the top row. Any move by B breaks this (shortening one row, or both), and A can always restore it, because the position after A's move is "bottom longer by one" and B cannot create that shape in one bite. The rows only shrink, so eventually A leaves bottom 1, top 0: just the poison, with B to move.
  3. A eats the square diagonally next to the poison (second row, second column). That removes the \(3 \times 3\) block, leaving an L: the bottom row of 4 and the left column of 4, sharing the poison. The two arms each have 3 squares beyond the poison. Whatever B bites from one arm, A bites the same amount from the other. The arms stay equal after A's moves, so B is the one who eventually faces the lone poison.
  4. After the top-right nibble, B eats the square diagonally next to the poison. That leaves the L with arms of 2, and B wins by copying, as in question 3. A could have eaten that same square at the start, and it would have removed the top-right square too, leaving the same L with B to move. This is the "stealing" step: B's winning reply was a winning first move for A all along.

Stretch. Suppose the second player had a winning strategy. The first player makes any mark, then pretends to be the second player and follows that strategy. If the strategy ever calls for the square already marked, mark any free square instead. At every stage the first player has every mark the strategy requires, plus one spare. A spare mark of your own can never block your own line or help the opponent, so the first player wins, which contradicts the assumption that the second player's strategy wins. So the game is a first-player win or a draw. (On the \(3 \times 3\) board it is a draw.)

← PreviousNext: The Josephus problem →