The sharp odd-cut threshold in Ellis–Thanatipanonda Family B

What Lean checks

The actual well-founded mex games have identical values at every positive pile size iff 3x < y, including infinite cut sets. The six-block base formula, preservation under all even cuts, and discrepancy by 4x are proved internally.

Cinna Davis and GPT-6.2 Astra, 18 November 2026

In the partition game CUT, a move with cut size dd splits one pile into d+1d+1 nonempty piles of the same total size. Write GC(n)G_C(n) for the Sprague–Grundy value of a pile of size nn when the allowed cut sizes form CC. A position with several piles has value equal to the bitwise XOR of their values. The value of a pile is the least nonnegative integer absent from its option values.

Theorem. Let C={1}∪X∪YC=\{1\}\cup X\cup Y, where XX is a nonempty set of even integers at least 44, and YY is a nonempty set of odd integers at least 55. Put x=minXx=\min X and y=minYy=\min Y. Then

GC(n)=G{1,x}(n) for every n≥1⇔y>3x.G_C(n)=G_{\{1,x\}}(n)\text{ for every }n\ge1 \quad\Longleftrightarrow\quad y>3x.

If y<3xy<3x, the two sequences differ at some n≤4xn\le4x. The sets may be infinite.

Ellis and Thanatipanonda conjectured in Section 7, Conjecture 2, that y>3xy>3x suffices for equality. Their Theorems 3 and 19 give the two published inputs below. Published paper, open text

The base game

Put g(n)=G{1,x}(n)g(n)=G_{\{1,x\}}(n). Theorem 19 gives the same sequence for {1}∪X\{1\}\cup X. Theorem 3 gives g(6xq+r)=8q+b(r)g(6xq+r)=8q+b(r) for q≥0q\ge0 and 1≤r≤6x1\le r\le6x. The six blocks of bb each have length xx. In the table, a parenthesized pair repeats to fill its block.

Residue interval Values in order
1,…,x1,\ldots,x (0,1)(0,1)
x+1,…,2xx+1,\ldots,2x (2,3)(2,3)
2x+1,…,3x2x+1,\ldots,3x 1,41,4, followed by repetitions of (5,4)(5,4)
3x+1,…,4x3x+1,\ldots,4x (3,2)(3,2)
4x+1,…,5x4x+1,\ldots,5x (4,5)(4,5)
5x+1,…,6x5x+1,\ldots,6x (6,7)(6,7)

Why a large cut preserves the value

We show that whenever p≥3x+2p\ge3x+2 piles of positive sizes h1,…,hph_1,\ldots,h_p sum to nn, their XOR under gg is strictly less than g(n)g(n).

Write hi=6xqi+rih_i=6xq_i+r_i with 1≤ri≤6x1\le r_i\le6x, and put Q=∑iqiQ=\sum_i q_i, R=∑iriR=\sum_i r_i. Since all b(ri)<8b(r_i)<8, the XOR is exactly

8(q1⊕⋯⊕qp)+(b(r1)⊕⋯⊕b(rp)).8(q_1\mathbin\oplus\cdots\mathbin\oplus q_p) +(b(r_1)\mathbin\oplus\cdots\mathbin\oplus b(r_p)).

The XOR of the quotients is at most their sum QQ. If R>6xR>6x, then n=6xQ+Rn=6xQ+R gives g(n)≥8(Q+1)g(n)\ge8(Q+1), whereas the displayed value is at most 8Q+78Q+7.

It remains to consider 3x+2≤p≤R≤6x3x+2\le p\le R\le6x. Now g(n)=8Q+b(R)g(n)=8Q+b(R). Each residue uses ri−1r_i-1 units in excess of its mandatory first unit, for a total of R−pR-p.

Range of RR Consequence for the residues Upper bound on their XOR of bb-values Lower bound on b(R)b(R)
R≤4xR\le4x R−p≤x−2R-p\le x-2, so every residue is at most xx. 11 22
4x<R≤5x4x\lt R\le5x R−p≤2x−2R-p\le2x-2, so every residue is at most 2x2x and at most one exceeds xx. 33 44
5x<R≤6x5x\lt R\le6x R−p≤3x−2R-p\le3x-2, so every residue is at most 3x3x. If one exceeds 2x2x, all others are at most xx. 55 66

For the last row, if all residues are at most 2x2x, their values all lie between 00 and 33, which is closed under XOR. Otherwise the single larger residue has value 11, 44 or 55. All other values are 00 or 11, so their XOR with it is at most 55. This proves the strict inequality in every case.

Suppose y>3xy>3x and induct on nn. By induction every smaller pile has value gg in the enlarged game. The options from cuts in {1}∪X\{1\}\cup X therefore already have least excluded value g(n)g(n). Every added odd cut produces at least 3x+23x+2 piles and hence an option of value strictly below g(n)g(n). Adding such options leaves the least excluded value equal to g(n)g(n). The initial pile of size one has no moves. This proves sufficiency for all nn.

Why the cutoff is sharp

Suppose d=y<3xd=y<3x. Make a cut of size dd on a pile of size 4x4x. Choose one part of size x+1x+1 and the other dd parts in [1,x][1,x] with sum 3x−13x-1. This is possible since d≤3x−1≤dxd\le3x-1\le dx. Every sum between dd and dxdx is obtained by distributing up to x−1x-1 extra units per part.

The sum 3x−13x-1 and the count dd are both odd, so an even number of these dd parts are even. In the first block g(h)=1g(h)=1 exactly when hh is even. Their XOR is therefore zero. The whole move has base value g(x+1)=2g(x+1)=2, which equals g(4x)g(4x) by the last entry of the fourth block.

If the two games agree at every smaller pile, this legal move to value 22 forces the enlarged game's least excluded value at 4x4x to differ from 22. Otherwise a difference already occurs earlier. Finally, yy is odd and 3x3x is even, so the two cases exhaust Family B.

Verification and prior work

The accompanying checker computes options directly from pile splits and the least-excluded-value rule. It compares the two sequences on both sides of the cutoff, including multi-cut sets and piles spanning multiple periods. The proof above covers arbitrary sizes.

A literature search on 18 November 2026 by author names, conjecture number, Family B and the odd-cut threshold located the original conjecture and the authors' theorem about adding even cuts. A separate formal result explicitly treats their Family A conjecture. We found no earlier resolution of Conjecture 2 in those sources. Priority remains provisional. Ellis and Thanatipanonda, Family A result and scope