Grundy's Game Periodicity

Eventual Periodicity in Grundy’s Splitting Game

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A move splits one heap into two nonempty heaps of unequal sizes; the player with no legal move loses. Let $g(0)=g(1)=g(2)=0$ and, for $n\geq3$, \[g(n)=\operatorname{mex}\{g(a)\oplus g(b):a+b=n,\ 1\leq a<b\}.\] Here mex is the least nonnegative integer missing from a finite set and $\oplus$ is binary xor. Ask whether $g(n)$ is eventually periodic. [S1] [S2]

Statement recorded in the supplied source.

Is the nim-sequence of Grundy's game eventually periodic? [S1]

Short English statement

Do the nim-values of the game that splits heaps into unequal parts eventually settle into a repeating pattern?

Research attempt: a certificate respecting unequal parts and period obstructions

Status. We prove a finite sufficient periodicity test specifically for Grundy's unequal-split rule, and derive necessary restrictions on any eventual period. No eventual period or proof of nonperiodicity is obtained. The inspected primary data source [S2] supplies context; its computed prefix is not treated as an infinite theorem.

1. Repairing the equality-of-parts trap

Fix $N\geq1$, $p\geq1$ and put $T=2N+3p$. A sufficient certificate is \[g(n+p)=g(n)\quad\text{for every }N\leq n\leq T.\tag{1}\] Assume $1$, and induct on $n>T$. For a legal split $a<b$ of $n$, increase the larger part to $b+p$. The resulting split remains unequal and has sum $n+p$. Since $b\geq N$ and $b<n$, induction shows its xor value equals the original value.

For a split $a<b$ of $n+p$, the larger part is greater than $N+p$, so reducing $b$ by $p$ gives a positive part on which the induction hypothesis applies. If $b-p\ne a$, this is a legal unequal split of $n$. If $b-p=a$, the direct reduction is illegal. In that exceptional case $b=a+p$ and $n=2a$. Since $n>2N+3p$, we have $a>N+p$. Reduce the smaller part instead, replacing $a$ by $a-p$. The resulting parts are positive and unequal, sum to $n$, and their xor value is unchanged by induction. All comparison base indices lie between $N$ and $n-1$.

Thus the option-value sets for $n$ and $n+p$ coincide in both directions, and mex gives $g(n)=g(n+p)$. Induction proves eventual periodicity from the finite certificate $1$. The computation needs values only through $T+p=2N+4p$. The special collision repair is essential; the ordinary octal argument allowing equal heaps cannot simply be copied here.

2. No period can start at zero

Suppose $g$ were periodic with period $p$ for all $n\geq0$. Because $g(0)=0$, the values at $p,2p,3p$ would all be zero. But the legal unequal split $3p=p+2p$ has xor value $0\oplus0=0$, forcing $g(3p)\ne0$, a contradiction. Any eventual periodicity must therefore have a genuine initial exception.

More generally, if $a\geq1$ has $g(a)=0$, an eventual period $p$ cannot divide $a$. Choose $n$ so large that $n-a$ and $n$ lie in the periodic tail and $n>2a$. Periodicity would give $g(n-a)=g(n)$, while the legal split $a+(n-a)$ would have option value $0\oplus g(n-a)=g(n)$, impossible for a mex. In particular $p=1$ is impossible because $g(1)=0$.

3. A restriction on the periodic residue pattern

If an eventual period existed, denote its residue values by $h(r)$ for $r\in\mathbb Z/p\mathbb Z$. For each residue $r$, choose two distinct sufficiently large heap sizes $a,b$ in that residue. Their xor is $h(r)\oplus h(r)=0$, and their sum lies in residue $2r$. Hence \[h(2r)\ne0\quad\text{for every }r.\tag{2}\] For odd $p$, doubling permutes the residue classes, so $2$ would imply that there are no zero nim-values sufficiently far out. For even $p$, it excludes zero values in all even residues. Neither statement by itself is a contradiction: infinitude of zero nim-values has not been proved in this attempt.

4. Verification and exact remaining problem

The diagnostic evaluates the defining recurrence through $n=400$, checks every certificate with $1\leq N,p\leq50$ whose required range is present, and records their outcomes. It also verifies the small zero-value obstructions directly from the recurrence. These bounded searches cannot rule out a much longer period or preperiod. The symbolic proof checks both directions of the option correspondence and explicitly handles the only reduction that can turn unequal parts into equal ones. The remaining question is whether any certificate $1$ exists, or whether one can prove that every proposed tail fails. The necessary conditions $2$ and the zero-heap divisibility test restrict candidates without settling either possibility.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1366 (GAME-009), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 A. Flammenkamp, Grundy's Game data (). https://wwwhomes.uni-bielefeld.de/achim/grundy.html. Bibliographic information from the supplied record.

• S3 MIT OCW, Grundy's Game -- Periodic? $2010$. https://ocw.mit.edu/courses/es-268-the-mathematics-in-toys-and-games-spring-2010/403b38e26e810396764745e0ebdc0b29_MITES_268S10_ses1_handout.pdf. Bibliographic information from the supplied record.