🔢 mathematics

Structural Conjectures for 4 x n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry

This paper presents an extensive computational study of 4 x n Chomp, tabulating over 4.3 million P-positions to propose four structural conjectures regarding unique extensions, asymptotic ratios, period-112 modular patterns, and linear cone geometry that reveal a richer deterministic structure in the game than previously suspected.

Original authors: Arnav Garg

Published 2026-04-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arnav Garg

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a game called Chomp played on a rectangular chocolate bar. The bar is made of a grid of squares. Two players take turns. On your turn, you pick one square and "eat" it, along with everything above it and to the right of it. The catch? The top-left square is poisoned. If you are forced to eat that last square, you lose.

Mathematicians have figured out the winning strategy for very small or very specific chocolate bars, but for a bar that is 4 squares wide and n squares long, the pattern was a mystery until now.

This paper is like a massive, high-speed detective story where the author used a super-fast computer to map out every single "losing position" (a spot where the player whose turn it is will lose if the opponent plays perfectly) for chocolate bars up to 500 squares long.

Here is what the author found, explained simply:

1. The "One-and-Done" Rule (Unique Extension)

Think of the chocolate bar as having four rows. The top three rows have certain lengths (let's call them A, B, and C).

The Discovery: The author found that for any specific combination of lengths for the top three rows, there is at most one specific length for the fourth row that creates a "losing position."
The Analogy: Imagine you are building a tower with three blocks of specific sizes. If you want the tower to be "unstable" (a losing position), there is only one specific size of the fourth block that will make it unstable. You can't just pick any fourth block; the math forces a single, unique answer. This suggests the game is much more predictable and "deterministic" than anyone thought.

2. The "Golden Ratio" of Chocolate (Asymptotic Ratios)

As the chocolate bar gets longer and longer (imagine stretching it out to infinity), the author noticed the rows settle into a specific shape.

The Discovery: The lengths of the rows stop changing randomly and start following a fixed pattern. If the top row is length 100, the second row will always be about 76 units long, the third about 50, and the fourth about 22.
The Analogy: It's like a tree growing. No matter how tall the tree gets, the branches always grow at the same relative proportions. The author calculated these "growth rates" but couldn't find a simple math formula (like a fraction) to describe them exactly yet. They are close to some famous numbers, but the exact secret remains hidden.

3. The "Hidden Rhythm" (Period-112)

The author looked for a repeating pattern in the data, like a beat in a song.

The Discovery: The data repeats a specific pattern every 112 steps.
The Analogy: Imagine a clock that doesn't tick every second, but has a complex rhythm that resets every 112 ticks. The author found that this rhythm is likely a mix of two smaller rhythms: one that repeats every 7 steps (inherited from the 3-row version of the game) and another mysterious one that repeats every 8 steps. The number 112 is just the "least common multiple" where these two rhythms sync up perfectly.

4. The "Funnel" Shape (Linear Cone Geometry)

If you plot all the possible "losing positions" on a graph, they don't look like a random cloud of dots.

The Discovery: They form a neat, funnel-like shape (a cone). As the rows get longer, the "width" of the valid losing positions grows in a straight, predictable line.
The Analogy: Imagine pouring sand into a funnel. The sand doesn't pile up randomly; it forms a smooth, widening cone. The author found that the "valid" losing positions in this game fit into a similar smooth, widening shape, with a tiny wobble caused by that 112-step rhythm mentioned earlier.

Why Does This Matter?

Before this paper, the 4-row version of Chomp was a black box. We knew the first player usually wins, but we didn't know why or how the losing spots were arranged.

The author found 4.3 million specific losing positions.
They proved that the game is likely governed by strict rules (the "Unique Extension") rather than chaos.
They found a hidden rhythm (112) that controls the game's structure.

What the paper does NOT say:

It does not claim this helps solve other games (like Chess or Go).
It does not claim this has medical or real-world applications.
It does not prove these rules are 100% true for infinite boards; it only proves they hold true for the 500-step range they tested. The author calls them "conjectures" (strong guesses based on evidence) rather than proven laws.

In short, the author took a messy, complex game, ran a massive computer simulation, and found that underneath the chaos, there is a very orderly, rhythmic, and predictable structure waiting to be fully understood.

1. Problem Statement

The paper investigates the combinatorial game Chomp played on a $4 \times n$ rectangular grid.

Game Rules: Players alternate removing a square and all squares above and to the right of it. The top-left square $(1,1)$ is "poisoned"; the player forced to take it loses.
Objective: Identify P-positions (Previous-player winning positions, or losing positions for the player whose turn it is).
Context: While $1 \times n$ and $2 \times n$ cases are fully solved, and $3 \times n$ has partial algorithmic solutions, the $4 \times n$ case lacked systematic computational analysis. The paper aims to fill this gap by tabulating P-positions and identifying underlying structural patterns.

2. Methodology

The author developed an optimized retrograde solver in C++ to compute P-positions for board widths up to $n = 500$ .

State Representation:
- Positions are represented as non-increasing tuples $(a, b, c, d)$ where $a \ge b \ge c \ge d \ge 0$ , denoting the number of squares in each row.
- Bitpacking: Each tuple is encoded into a single uint64 integer using four 16-bit fields to minimize memory usage and maximize hashing speed.
Algorithm Design:
- Sparse Storage: Only P-positions are stored in a hash set. The solver short-circuits N-positions (winning for the current player) as soon as a move to a known P-position is found.
- Bottom-Up Evaluation: States are processed in increasing order of total cell count, ensuring all successors are resolved before evaluating a state.
Performance:
- Computed 4,316,097 P-positions for $n \le 500$ .
- Execution time: ~70 minutes on an Apple M4 processor.
- Memory usage: Peak usage of 45 MB.
Verification:
- Validated against the known $2 \times n$ formula (where $c=d=0$ implies $b=a-1$ ).
- Cross-checked with an independent Python solver for the $3 \times n$ subcase ( $d=0$ ) up to $n=50$ .
- Corrected an initial column-alignment bug in data output.

3. Key Contributions and Results

The analysis of the computed dataset led to four primary structural conjectures:

A. Conjecture 1: Unique Extension Property

Statement: For any valid triple of row lengths $(a, b, c)$ , there exists at most one integer $d$ such that $(a, b, c, d)$ is a P-position.
Implication: The projection map $\pi: (a, b, c, d) \to (a, b, c)$ is injective on the set of P-positions.
Significance: This suggests the $4 \times n$ game is a "deterministic lift" of the $3 \times n$ game. While not every $(a, b, c)$ extends to a P-position (only ~20% do), if an extension exists, the fourth row length $d$ is uniquely forced. This contrasts with the $3 \times n$ case, where no such simple injective mapping was previously established.

B. Conjecture 2: Asymptotic Ratios

Statement: As the board width $a \to \infty$ $a \to \infty$ , the ratios of row lengths in P-positions converge to fixed constants:
- $b/a \to L_1 \approx 0.762$
- $c/a \to L_2 \approx 0.499$
- $d/a \to L_3 \approx 0.224$
Methodology: Estimated via windowed medians, rolling windows, and power-law curve fitting.
Observation: No exact algebraic identity was found for these constants. However, $L_3 \approx 0.224$ is remarkably close to $\cos(3\pi/7) \approx 0.2225$ , suggesting a potential hidden algebraic relationship.

C. Conjecture 3: Period-112 Modular Structure

Statement: The set of triples $(a, b, c)$ that extend to P-positions exhibits a modular structure with a fundamental period of 112.
Evidence:
- Autocorrelation analysis of the sequence of $d$ -values shows a sharp peak at lag 112.
- A logistic classifier using only $c$ and $(a-b) \pmod{112}$ predicts extendability with 79% accuracy.
- Chi-squared tests confirm modulus 112 provides the strongest statistical separation ( $\chi^2 = 12,433$ ) compared to other moduli.
Interpretation: $112 = \text{lcm}(7, 8) \times 2$ . The factor of 7 likely stems from the $3 \times n$ sub-game periodicity, while the factor of 8 remains unexplained (ruling out bit-packing artifacts).

D. Conjecture 4: Linear Cone Geometry

Statement: The set of extending triples $(a, b, c)$ forms a linear cone in $\mathbb{R}^3$ .
Geometry: For a fixed $c$ , the valid range of $(a, b)$ forms a contiguous band. The width of this band grows linearly with $c$ :
$\text{width}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$
where $f$ is a bounded periodic function. The slope $11/8 = 1.375$ was derived from slice-based measurements.

4. Significance and Future Directions

Structural Insight: The findings suggest that $4 \times n$ Chomp possesses a richer, more deterministic structure than previously suspected, potentially simpler than the $3 \times n$ case due to the "Unique Extension" property.
Generalization: The author hypothesizes that the Unique Extension property may generalize to $k \times n$ Chomp for all $k$ , implying that all Chomp games are recursively determined by the solved $2 \times n$ case.
Open Questions:
1. Proof: Can the Unique Extension property be proven combinatorially?
2. Algebraic Limits: Are the asymptotic ratios roots of a common polynomial?
3. Higher Dimensions: Does this hold for $5 \times n$ ? (Requires $O(n^5)$ state space).
4. Period Origin: What is the source of the period-8 component in the 112-cycle?
5. Closed Form: Can the ~20% of extendable triples be described by a closed-form mask?

The paper also notes the submission of the sequence of $d$ -values to the On-Line Encyclopedia of Integer Sequences as A395126. The code and data are publicly available via the author's GitHub repository.