Unique Winning Opening Move in Three-Row Chomp

Erez Sheiner · 2026

Read Unique Winning Opening Move in Three-Row Chomp by Erez Sheiner (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23837.txt.

Introduction

Erez Sheiner settles a 52 year old question about Chomp, the chocolate bar game where a move eats a rectangle corner. Gale had computed that every three row board up to width 100 has exactly one winning first move and asked if that always holds. Sheiner proves it does for every width, using a two variable recurrence for losing positions. A rightmost hole principle splits the counting numbers into two move types, also naming the winning row, which is never the first.

Catalog record

CREATORErez Sheiner
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE17773
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.23837

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unique Winning Opening Move in Three-Row Chomp Erez Sheiner Abstract Chomp was introduced by Gale in 1974 [ 4 ] . In the same paper, Gale reported that the 3 × n 3\times n games had been completely analyzed for n ≤ 100 n\leq 100 , with a unique winning first move in every case, and asked whether winning first moves are unique in general. Although the general uniqueness statement is false [ 1 , Section 7.1] , we prove that the three-row uniqueness phenomenon suggested by Gale’s computations holds for all n n : every 3 × n 3\times n Chomp rectangle has exactly one winning opening move. This settles the three-row case of Gale’s 52-year-old first-move uniqueness question. The proof is carried out in the two-variable recurrence introduced by Brouwer, Horváth, Molnár-Sáska, and Szabó [ 1 ] for the function f ⁡ ( q , r ) f(q,r) whose values encode the P P -positions. The main local ingredient is a rightmost-hole principle: if a value p p is absent from the set C ⁡ ( q , r ) C(q,r) but belongs to all corresponding sets C ⁡ ( t , r ) C(t,r) for q < t < p q<t<p , then all intermediate values q + 1 , … , p − 1 q+1,\ldots,p-1 are forced to belong to C ⁡ ( q , r ) C(q,r) . This separates the diagonal values from the starts of constant rows, and yields a partition of the positive integers into the two possible types of winning opening moves. 1 Introduction Chomp, introduced by Gale [ 4 ] , is played on a finite n\times m binary matrix A . The game starts with A_{ij}=1 for all i,j , and a move (p,q) is allowed if A_{pq}=1 . The move (p,q) sets A_{ij}=0 for every i\geq p , j\geq q . The player forced to make the move (1,1) loses. In the three-row case we write a position as [p,q,r],\qquad p\geq q\geq r\geq 0, where p,q,r are the row lengths in nonincreasing order. A P -position is a position from which the previous player wins, and an N -position is a position from which the next player wins. A move reducing the second row of [p,q,r] to length a<q gives [p,a,\min(a,r)] ; in particular, if a<r , the resulting position is [p,a,a] . Similarly, reducing the first row to length a<p gives [a,\min(a,q),\min(a,r)] . The three-row case has been studied through recurrences, computation, and renormalization methods. Zeilberger gave an early recurrence-based analysis of three-row Chomp [ 5 ] . Brouwer, Horváth, Molnár-Sáska, and Szabó introduced the two-variable function used below and developed the associated table of P -positions [ 1 ] . Friedman and Landsberg studied the same structure from a nonlinear-dynamics and renormalization viewpoint [ 2 ] . A recent preprint of Garg on 4\times n Chomp also places the three-row case in this context: it records the computational evidence for uniqueness in 3\times n Chomp up to n\leq 100{,}000 and states that a proof had remained out of reach [ 3 ] . The present note provides such a proof directly from the recurrence. Theorem 1.1 (Unique opening move) . For every positive integer n , the initial three-row Chomp rectangle [n,n,n] has exactly one winning opening move. The rest of this note proves the theorem. 2 The recurrence The following elementary lemma explains the meaning of the function used in the recurrence. Lemma 2.1 (Existence and uniqueness of the encoded P -position) . For every q\geq r\geq 0 , there is a unique integer p>r such that one of the following holds: (i) r<p<q and [p,p,r] is a P -position; (ii) p\geq q and [p,q,r] is a P -position. In either case, the corresponding P -position is obtained from any sufficiently long position [k,q,r] by reducing the first row to length p . Proof. First observe uniqueness. Suppose p_{1}<p_{2} are two integers satisfying the lemma. If p_{i}<q , the position corresponding to p_{i} is [p_{i},p_{i},r] ; if p_{i}\geq q , it is [p_{i},q,r] . In all cases, the position corresponding to p_{1} is obtained from the position corresponding to p_{2} by reducing the first row to length p_{1} . This is a legal move from one P -position to another, impossible. It remains to prove existence. We argue by induction on q+r . The case q=r=0 is clear: among the one-row positions [p,0,0] , the unique P -position is [1,0,0] . Now let q\geq r\geq 0 , and assume the assertion has already been proved for all pairs (q^{\prime},r^{\prime}) with q^{\prime}\geq r^{\prime} and q^{\prime}+r^{\prime}<q+r . Consider first the values of p for which [p,q,r] can move to a P -position by reducing the second row. If the second row is reduced to a<q , the resulting position is [p,a,\min(a,r)]. The lower pair (a,\min(a,r)) has smaller sum than (q,r) . Hence, by the induction hypothesis, there is at most one value of p for which this resulting position is a P -position. Similarly, if the third row is reduced to b<r , the resulting position is [p,q,b], and the lower pair (q,b) has smaller sum than (q,r) . Hence, again by the induction hypothesis, there is at most one value of p for which this resulting position is a P -position. Thus only finitely many values of p are blocked by moves reducing the second or third row. Choose an integer p\geq q which is not one of these blocked values. If reducing the first row of [p,q,r] to some length k with r<k<p gives a P -position, then existence is proved, since this k satisfies the lemma. Otherwise, no move reducing the first row to a length greater than r leads to a P -position. A move reducing the first row to a length 1\leq k\leq r gives the rectangle [k,k,k] , which is an N -position by the standard strategy-stealing argument, and the move to length 0 is the losing move that takes the poisoned square. By the choice of p , no move reducing the second or third row of [p,q,r] leads to a P -position. Therefore [p,q,r] has no move to a P -position, and hence it is itself a P -position. Since p\geq q , this is alternative (ii). ∎ We denote the unique integer in Lemma 2.1 by f(q,r) . Thus, if r<f(q,r)<q, then [f(q,r),f(q,r),r] is a P -position, while if f(q,r)\geq q, then [f(q,r),q,r] is a P -position. Conversely, every three-row P -position is encoded in this way. The recurrence introduced by Brouwer et al. [ 1 ] is based on the following blocked values. When computing f(q,r) , a value p is blocked if choosing it would give a position with a move to an already encoded P -position. We separate the blocked values according to whether the move reduces the second row or the third row. If the second row is reduced to some length a<q , then the lower two row lengths become a,\min(a,r). The corresponding encoded P -position is therefore given by f(a,\min(a,r)) . Thus the values blocked by reducing the second row are R(q,r)=\{f(a,\min(a,r)):0\leq a<q\}. Equivalently, R(q,r)=\{f(a,a):0\leq a<r\}\cup\{f(a,r):r\leq a<q\}. If the third row is

Read the complete text