Chomp

Chomp is a two-player impartial game played on a finite board in the form of a rectangle, usually pictured as a chocolate bar with one poisoned corner cell. Number the rows from top to bottom and the columns from left to right, starting at 1, with the poisoned cell at . Players alternate moves. A player chooses a remaining cell and removes it together with every remaining cell satisfying and . The player who removes the poisoned cell loses. The rectangular version was analyzed by Gale (1974). Positions are called winning or losing for the player to move, assuming optimal play.

Every initial board with more than one cell admits a winning opening. To see this, consider the move removing only the cell from an board. If this move is winning, the assertion follows. Otherwise, the second player has a winning reply. Making that reply directly on the original board produces the same position, since any move also removes . The first player can therefore make a winning opening. This argument establishes existence without identifying a winning opening (Gale 1974).

For a one-row board of width , the unique winning opening is , leaving only the poisoned cell. For a two-row board, the positions from which the player to move loses have row lengths with . Consequently, the unique winning opening on a board is . On an square board with , the unique winning opening is . The first player then answers each move by (Brouwer et al. 2005, p. 4).

Gale (1974) reported that all boards with had exactly one winning opening and asked whether winning openings were unique in general. The general assertion is false, with an board providing a counterexample (Brouwer et al. 2005, p. 4). Sheiner (2026) proved that every board, for positive integer , has exactly one winning opening, settling the three-row case of Gale's question. This result concerns initial boards and does not assert uniqueness for arbitrary partially eaten positions.

In the three-row case, write a nonempty position as , where the remaining row lengths are integers with and . No winning opening on is made in the first row. An opening in the second row produces , while one in the third row produces , with and , respectively. The widths admitting second-row openings begin 1, 3, 4, 6, 8, 10, 11, 13, 15, 16, 18, 20, ... (OEIS A029900), and those admitting third-row openings begin 2, 5, 7, 9, 12, 14, 17, 19, 22, 23, 26, 29, ... (OEIS A029901). Sheiner (2026) proved that these two sets are disjoint and together contain every positive integer. The first sequence is indexed by in the losing positions and is not necessarily increasing (Brouwer et al. 2005, pp. 7-8).