Chomp, math that surprises you lesson

A chocolate bar is divided into squares, and the square in the bottom left corner is poisoned. Two players take turns biting off a square together with everything above it and to its right, and whoever has to take the poisoned square loses. Can the first player always win, whatever the size of the bar? This page shows that the answer is yes for every rectangle with more than one square, by an argument that proves a winning first move exists without saying which square it is.

Key terms

Chomp

Definition Chomp is a game for two players on a rectangular bar of $m$ rows and $n$ columns of squares, where $m$ and $n$ are positive whole numbers with $mn \ge 2$ , so the bar has more than one square. Number the columns $0, 1, \dots, n - 1$ from left to right and the rows $0, 1, \dots, m - 1$ from bottom to top, and call the square in column $x$ and row $y$ the square $(x, y)$ . The square $(0, 0)$ in the bottom left corner is poisoned. The players take turns, and passing is not allowed. On each turn a player chooses a remaining square $(x, y)$ and removes every remaining square $(u, v)$ with

u \ge x \quad \text{and} \quad v \ge y,

that is, the chosen square, the squares to its right in its row, the squares above it in its column, and every square that is both above it and to its right. The player who chooses the poisoned square loses, so a player who is left with only the poisoned square loses. Both players see the bar, and nothing is decided by chance.

After any number of moves, every remaining row starts at column $0$ and is no longer than the row below it. So a position can be written as its list of row lengths from the bottom up, such as $[3, 2]$ for a bottom row of $3$ squares under a top row of $2$ , with $[1]$ for the poisoned square alone. The result proved on this page is that every rectangle with more than one square is a first-player win. The proof does not say which first move wins, and no simple rule is known that names a winning first move for every rectangle.

In plain words Each bite removes the chosen square and everything above it and to its right. Nobody wants the poisoned square, so each player tries to leave the other with nothing else.

Example On a bar with one row, the first player chooses the square next to the poison, which removes every square except the poisoned one, and the opponent must take the poison. A bar with one column works the same way with the square just above the poison. Now take $2$ rows and $3$ columns, the position $[3, 3]$ . The first player bites only the top right square $(2, 1)$ , leaving $[3, 2]$ . The opponent has four safe choices, and each has an answer that leaves the bottom row exactly one square longer than the top row.

Opponent bites	Leaves	You bite	Leaves
$(0, 1)$	$[3]$	$(1, 0)$	$[1]$
$(1, 1)$	$[3, 1]$	$(2, 0)$	$[2, 1]$
$(1, 0)$	$[1, 1]$	$(0, 1)$	$[1]$
$(2, 0)$	$[2, 2]$	$(1, 1)$	$[2, 1]$

When you leave $[1]$ , the opponent has to take the poison. When you leave $[2, 1]$ , the opponent can bite $(1, 0)$ , leaving $[1, 1]$ , or $(0, 1)$ , leaving $[2]$ , and you answer with $(0, 1)$ or $(1, 0)$ to leave $[1]$ . So biting the top right square wins on the bar with $2$ rows and $3$ columns.

Strategy-stealing argument

Definition A strategy-stealing argument proves that the first player has a winning strategy by showing that a winning answer for the second player could be used by the first player instead. For Chomp it goes as follows. Let $R$ be a bar of $m$ rows and $n$ columns with $mn \ge 2$ , and let $c = (n - 1, m - 1)$ be its top right square, which is not the poisoned square. Each move removes at least one square, so the game ends after at most $mn$ moves. It cannot end in a draw and has no chance or hidden information, so by backward induction every position is either winning or losing for the player to move.

Suppose the first player opens by biting only $c$ . If this leaves a losing position for the opponent, it is a winning first move. Otherwise the position left is winning for the opponent, so the opponent has a winning reply, a square $q$ whose bite leaves a position $Q$ that is losing for the first player. The square $q$ is not the poisoned square, since choosing it would lose at once. Every square $(x, y)$ of $R$ satisfies $x \le n - 1$ and $y \le m - 1$ , so a bite at any square of $R$ removes $c$ as well. Hence biting $q$ straight away from the full bar removes exactly the squares removed by biting $c$ and then $q$ . It leaves the same position $Q$ , but now the opponent is the player to move, and $Q$ is losing for the player to move. So biting $q$ is a winning first move. In both cases the first player has a winning first move. The argument needs a square that every bite removes, and among the shapes that can occur in Chomp only rectangles have one.

In plain words Biting only the far corner is a move that costs almost nothing. If it wins, the first player is done. If the opponent has a winning answer to it, the first player could have made that answer as the opening move, because that bite takes the far corner anyway.

Example On the bar with $3$ rows and $3$ columns, biting only the corner $(2, 2)$ does not win. It leaves $[3, 3, 2]$ , and the opponent answers with $(1, 1)$ , which leaves $[3, 1, 1]$ . This is an L shape with two squares to the right of the poison and two squares above it, and the mirror rule of question 2 in Check yourself shows that an L shape with two equal arms is losing for the player to move. The argument says that the first player should make this answer as the opening move instead. Biting $(1, 1)$ from the full bar leaves the same $[3, 1, 1]$ , now with the opponent to move. Checking every possibility shows that biting $(1, 1)$ is in fact the only winning first move on this bar.

Nonconstructive proof

Definition A nonconstructive proof shows that an object with some property exists without exhibiting the object or giving a method to find it. A constructive proof names the object or gives a procedure that produces it. Nonconstructive proofs often split into cases and show that each case yields an object, without deciding which case is true, or they show that assuming no such object exists leads to a contradiction.

In plain words A nonconstructive proof tells you that the answer exists, but not what it is.

Example A classic proof shows that there are irrational numbers $a$ and $b$ such that $a^b$ is rational. A number is rational when it is a fraction $p/q$ of integers with $q \ne 0$ , and irrational otherwise, and $\sqrt{2}$ is irrational. Let $x = \sqrt{2}^{\sqrt{2}}$ . If $x$ is rational, take $a = b = \sqrt{2}$ . If $x$ is irrational, take $a = x$ and $b = \sqrt{2}$ , since

\begin{aligned} x^{\sqrt{2}} &= \bigl(\sqrt{2}^{\sqrt{2}}\bigr)^{\sqrt{2}} \\[0.4em] &= \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} \\[0.4em] &= \sqrt{2}^{\,2} = 2. \end{aligned}

Either way a suitable pair exists, but the proof does not say which pair it is. A much deeper theorem shows that $x$ is irrational, so the second case is the true one, but the short proof never needed to know that. The strategy-stealing argument for Chomp has the same shape. It shows that either the corner bite or a winning reply to it works as an opening, without deciding which, and without saying where that reply is.

First-player win

Definition A game started from a given position is a first-player win if the player who moves first has a winning strategy, a rule for choosing moves that wins against every possible sequence of replies. It is a second-player win if the second player has such a strategy. In a finite game for two players who alternate, with full information, no chance and no draws, backward induction shows that every starting position is exactly one of the two. In a game that can end in a draw, a starting position can be neither, as in tic-tac-toe, where correct play by both sides always ends in a draw.

In plain words A first-player win means that moving first is enough to win, provided you play correctly from then on. It is a statement about perfect play, so a first player who makes a mistake can still lose.

Example Every Chomp bar with more than one square is a first-player win, while the bar of a single square is a second-player win, because the first player has to take the poison at once. In the take-away game with moves of one, two or three counters, a pile of $21$ is a first-player win and a pile of $20$ is a second-player win. For a Chomp bar with $2$ rows an explicit strategy is known. Bite the top right square, and afterwards always leave the bottom row exactly one square longer than the top row. If the opponent bites the top row at column $x$ , so that the top row keeps $x$ squares, bite the bottom row at column $x + 1$ . If the opponent bites the bottom row at column $x$ , so that both rows keep $x$ squares, bite the top row at column $x - 1$ . Each time the bar shrinks, and the game ends with the opponent facing $[1]$ . Square bars also have a simple strategy, found in question 2 below. For general rectangles, no simple rule for finding a winning first move is known, although for any particular small bar a computer can find one by backward induction.

Check yourself

Take a bar with $2$ rows and $4$ columns. Show that biting the top right square $(3, 1)$ wins, by giving an answer to every reply.

Show the answer

The bite at $(3, 1)$ leaves $[4, 3]$ . The opponent has six safe choices, and each answer below leaves the bottom row exactly one square longer than the top row.

Opponent bites	Leaves	You bite	Leaves
$(0, 1)$	$[4]$	$(1, 0)$	$[1]$
$(1, 1)$	$[4, 1]$	$(2, 0)$	$[2, 1]$
$(2, 1)$	$[4, 2]$	$(3, 0)$	$[3, 2]$
$(1, 0)$	$[1, 1]$	$(0, 1)$	$[1]$
$(2, 0)$	$[2, 2]$	$(1, 1)$	$[2, 1]$
$(3, 0)$	$[3, 3]$	$(2, 1)$	$[3, 2]$

From $[3, 2]$ and from $[2, 1]$ the same rule gives an answer to every reply, as in the example of the Chomp card, and each round removes at least two squares. So the game reaches $[1]$ with the opponent to move, and the opponent has to take the poison.

Take a square bar with $4$ rows and $4$ columns. Show that the first player wins by biting $(1, 1)$ , the square diagonally above and to the right of the poison.

Show the answer

The bite at $(1, 1)$ removes every square with $x \ge 1$ and $y \ge 1$ . What is left is an L shape, the poison with an arm of three squares to its right in the bottom row and an arm of three squares above it in the left column, which is $[4, 1, 1, 1]$ . A bite at $(x, 0)$ with $x \ge 1$ removes only squares of the bottom arm, from column $x$ on, because the squares of the left arm have $x$ coordinate $0$ . In the same way a bite at $(0, y)$ with $y \ge 1$ removes only squares of the left arm, from row $y$ up.

So answer every bite by cutting the other arm to the same length. After each of your moves the two arms are equal. The opponent can never take the last safe square, because a move that empties one arm leaves the other arm still nonempty, and you then empty it. When both arms are empty, the opponent faces the poison alone. The same opening and the same mirror rule win on every square bar with at least $2$ rows.

The L shape $[4, 1, 1, 1]$ from question 2 is losing for the player to move. Why does the strategy-stealing argument not prove that it is a first-player win?

Show the answer

The argument needs a square that every bite removes, so that the first player’s trial move is swallowed by any reply. In the L shape there is no such square. Every square of the bottom arm survives a bite at $(0, 1)$ , every square of the left arm survives a bite at $(1, 0)$ , and the poison survives every safe bite.

Trying the argument anyway shows where it breaks. Suppose the first player bites $(3, 0)$ , leaving arms of two and three squares. The opponent’s winning reply is $(0, 3)$ , which makes both arms two squares long. Biting $(0, 3)$ directly from the original L leaves arms of three and two squares instead, a different position, and a winning one for the opponent. The reply cannot be stolen, and the L shape really is a second-player win.