8
Part II · Games with turns

A proof that you can win

Chomp is a chocolate bar with one poisoned square. Mathematicians have proved that the first player can always win, on a bar of any size, and for most sizes nobody knows what the winning move is. This chapter is about how you can be certain of something you cannot see. It is the best kind of proof there is.

The rules. A rectangular chocolate bar. The top-left square is poison. On your turn, pick any square and eat it, along with every square to its right and every square below it. Whoever is forced to eat the poison loses.

Play a few games. Hover over a square to see what you would eat. Robo has worked out every one of the 210 shapes this bar can be nibbled into, so it plays perfectly. If you go first and play well, you can still beat it. Ask for a hint when you need one and try to spot what the winning positions have in common.

Chomp

Do not eat the poison.
Rows Columns

Robo knows the winning move for every shape of this bar. That is different from knowing a rule for it.

The proof

Here is something amazing. For any bar bigger than one square, the first player can always win. This has been proved. And yet, for most bar sizes, nobody knows what the first player's winning move is. The proof tells you the move exists without telling you what it is. Read it slowly; every step is honest.

  1. Imagine the first player nibbles just the tiny bottom-right square. Call this the shy move.
  2. Either the shy move is a winning move (in which case we are done: the first player has a winning move), or it is not.
  3. If it is not, then the second player has some winning reply to it. Call that reply the secret move: eating some square, along with everything right of and below it.
  4. But look: the secret move also eats the bottom-right square, because every move does. So the first player could have played the secret move right at the start, and reached exactly the same position, with the second player to move. Now the first player is the one with the winning position.
  5. So either way, the first player has a winning first move. We just proved a winning move exists without finding it.

This is called a strategy-stealing argument: whatever plan the second player had, the first player steals it. Chapter 9 uses the same trick on the game of Hex.

Why does the trick work here? Because in Chomp an extra move can never hurt you: the shy move is "free". In most games that is false. In chess, being forced to move can be a disaster, so strategy stealing proves nothing about chess.

The one size we do understand

For a square bar there is a rule, and it is beautiful. Eat the square just diagonally below and right of the poison, the one in row 2, column 2. That leaves an L shape with two equal arms. Now, whatever Robo eats from one arm, you eat the same amount from the other arm. The arms stay equal, Robo eventually has to eat the poison, and you never had to think.

Press "Make it square" above, go first, and try it. This is a mirror strategy, and once you have seen one you will start noticing them everywhere.

Counting the shapes

How many different shapes can a 4 by 6 bar be nibbled into? Every possible shape is a staircase: each row is no longer than the row above it. Trace the edge of the staircase from the top-right corner to the bottom-left corner and you get a path of 10 steps, 6 of them going left and 4 going down. Choosing which 4 of the 10 steps go down decides the whole shape. So the number of shapes is "10 choose 4":

C(10, 4) = 10! / (4! × 6!) = 210

How many shapes?

A bar with r rows and c columns has C(r + c, r) shapes.

Each shape is a path: left steps and down steps in some order. The poison square alone is a shape too, and so is the empty bar.

How many shapes can a 3 by 5 bar make?

Math corner

Proof by contradiction. To prove something is true, assume it is false and show that leads to nonsense. The Chomp proof assumes "the second player can win" and turns that into "the first player can win", which cannot both be true. So the assumption was wrong. Mathematicians use this move constantly.

Existence without construction. The proof is non-constructive: it shows a winning move exists but gives no way to find it except trying every one. For a 4 by 6 bar that is 210 shapes, easy. For a 100 by 100 bar, C(200, 100) is a number with 59 digits, and nobody has a shortcut.

Choosing. C(n, k), read "n choose k", counts the ways to pick k things out of n. The formula is n! divided by k! times (n − k)!. C(10, 4) = 3,628,800 / (24 × 720) = 210. These numbers are also the rows of Pascal's triangle.

Big idea

You can prove a winning move exists without knowing it. Assume the second player has a winning plan; show the first player could steal it; conclude the first player wins. The proof is airtight and completely unhelpful for actually playing, and both of those things are fine.

Try it on paper

1. On a 2 by 2 bar, what is the winning first move?

Answer

Eat the bottom-right square, leaving an L of two equal arms (one square each). Whatever Robo eats, you eat the other arm, and Robo eats the poison.

2. On a 1 by n bar (a single row), what is the winning first move?

Answer

Eat everything except the poison. Robo must eat the poison. On a single row the first player wins instantly, whatever n is.

3. How many shapes can a 2 by 3 bar make? List them by their row lengths.

Answer

C(5, 2) = 10. As (top row, bottom row): (3,3), (3,2), (3,1), (3,0), (2,2), (2,1), (2,0), (1,1), (1,0), (0,0). The last one is the empty bar, after the poison has been eaten.

Challenge

Use the board with hints on to find the winning first move for a 3 by 3 bar, a 3 by 4 bar, and a 3 by 5 bar. Then try to guess a rule for 3-row bars. Do not feel bad if you cannot: no simple rule is known, and three-row Chomp has been studied by computer up to very long bars without one appearing.

Answer

3 by 3: eat row 2, column 2 (the square trick). 3 by 4: eat row 2, column 3, leaving rows of 4, 2, 2. 3 by 5: eat row 3, column 2, leaving rows of 5, 5, 1. The winning first moves jump around with no pattern anyone has been able to describe, which is exactly why the existence proof is so satisfying.

True story

Chomp was invented in 1974 by David Gale, a mathematician at Berkeley who also co-invented the Hex-like game of Bridg-It and the famous "stable marriage" algorithm. The strategy-stealing proof was noticed almost immediately. The name Chomp was given by Martin Gardner, who wrote about mathematics in Scientific American for 25 years and introduced more people to games like this than anyone in history. A version of the same game, played with the divisors of a number instead of a chocolate bar, was described by the Dutch mathematician Fred Schuh in 1952, twenty years earlier.

Stars in this chapter

Earn them by doing the clever thing, not by clicking around.