we-solve (beta)

Math-595 · mathematics · Combinatorics

Octal Games Periodicity

Status Open · unsolvedmath.comLLM status Open unverified

Statement

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.

An octal take-and-break rule specifies, for each allowed number of removed counters, whether the remainder may consist of zero, one or two heaps; the three permissions are encoded by the bits of an octal digit. A finite code has only finitely many nonzero digits. Play is normal play on finite heaps. Its nim-sequence is $g(n)=\operatorname{mex}\{\bigoplus_i g(n_i):\text{legal move from a heap of size }n\}$, where $\oplus$ is binary xor. Eventual periodicity means $g(n+p)=g(n)$ for all $n\geq N_0$, for some $p,N_0$. [S1] [S2]

Statement recorded in the supplied source.
Are the nim-sequences of all finite octal games eventually periodic? [S1]

Short English statement

Does the sequence of nim-values for every finitely specified octal heap game eventually repeat with a fixed period?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-595-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-595

Eventual Periodicity in Finite Octal Games

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.

An octal take-and-break rule specifies, for each allowed number of removed counters, whether the remainder may consist of zero, one or two heaps; the three permissions are encoded by the bits of an octal digit. A finite code has only finitely many nonzero digits. Play is normal play on finite heaps. Its nim-sequence is $g(n)=\operatorname{mex}\{\bigoplus_i g(n_i):\text{legal move from a heap of size }n\}$, where $\oplus$ is binary xor. Eventual periodicity means $g(n+p)=g(n)$ for all $n\geq N_0$, for some $p,N_0$. [S1] [S2]

Statement recorded in the supplied source.
Are the nim-sequences of all finite octal games eventually periodic? [S1]

Short English statement

Does the sequence of nim-values for every finitely specified octal heap game eventually repeat with a fixed period?

Research attempt: a finite periodicity certificate and the nonsplitting subcase

Status. We give a sufficient finite certificate for any proposed eventual period and prove eventual periodicity for every finite rule without splitting. We do not prove that a certificate exists for every finite octal code. The inspected primary data source [S2] uses bits for zero, one and two nonempty successor heaps and distinguishes empirical prefixes from proven periods.

1. A safe finite certificate

Let $K$ be the largest number of counters removed in a permitted move. A zero-removal move may split into two positive heaps, but may not leave the original heap unchanged. Take $N\geq1$, $p\geq1$, and put $T=2N+p+K$. We claim: \[g(n+p)=g(n)\text{ for }N\leq n\leq T \quad\Longrightarrow\quad g(n+p)=g(n)\text{ for every }n\geq N.\tag{1}\] The bound is sufficient, not asserted optimal. Assume by induction that the equality is known below some $n>T$, and compare the option-value sets of heaps $n$ and $n+p$. A move removing the entire heap is unavailable because both sizes exceed $K$. A one-heap move removes $k\geq1$ counters, and its values agree by induction at base index $n-k\geq N$.

For a two-heap move from $n$, write $a+b=n-k$ with $a,b\geq1$. The sum exceeds $2N+p$, so one part, say $b$, is at least $N$. Replace it by $b+p$ to obtain a legal split of $n+p-k$ with the same xor value by induction. The comparison has base index $b<n$, even when $k=0$.

Conversely, in a split $a+b=n+p-k$ from $n+p$, the sum exceeds $2N+2p$, so one part is at least $N+p$. Reduce that part by $p$. It stays positive, the resulting split is legal from $n$, and the xor value is unchanged. Its comparison base index is at least $N$ and less than $n$. Octal rules permit equal parts whenever the two-heap bit is present, so equality between the reduced parts is not an extra prohibition. Both option sets are therefore equal, and applying mex proves the next equality in $1$.

2. An actual finite-state proof without splitting

Suppose no two-heap bit occurs. With maximum removal $K\geq1$, there are at most $K$ one-heap options and at most one empty option. Thus every mex value is at most $K+1$. Once $n>K$, empty moves are impossible, and $g(n)$ is a fixed function of the previous $K$ values, determined by which removal digits permit one nonempty heap. The state vector of these $K$ values has at most $(K+2)^K$ possibilities. Iterating a deterministic map on this finite set eventually repeats a state and thereafter repeats forever. This proves eventual periodicity in the nonsplitting subcase. The zero rule $K=0$ is the constant-zero sequence.

This argument fails with splitting because a move can reference $g(a)$ for arbitrarily distant $a$, rather than just a bounded window behind $n$. Boundedness of values alone does not repair that missing finite-memory property.

3. Certificate search and its logical limitation

Given $N,p$, recurrence evaluation through $T+p=2N+2p+K$ checks the hypothesis of $1$ by finite integer computations. Enumerating all pairs $N,p$ therefore semidecides eventual periodicity: if a period exists, one pair eventually passes and $1$ certifies it. Failure of all pairs checked so far does not prove nonperiodicity. This is the same distinction as termination of a successful search versus termination on every input.

4. Adversarial verification and remaining gap

The diagnostic computes every two-digit code $0.d_1d_2$ through heap size 300, tests candidate certificates with $1\leq N\leq12$ and $1\leq p\leq12$, and checks all certificates found against the remaining computed tail. It also checks the nonsplitting codes against their finite-state cycles. These checks test indexing and the option correspondence, not the universal existence assertion. The proof explicitly treats zero-removal splitting, positive remainders and the disappearance of empty moves; an illegal one-heap zero-removal move would invalidate the well-founded recurrence and is excluded. What remains is a theorem forcing some $(N,p)$ to satisfy $1$ for every finite splitting code, or a proof that a particular code never does.

Sources

Go to contribution →