Grundy-number and nim-sum conjecture for amalgamation Nim with restriction

An explicit Grundy formula for restricted amalgamation Nim

Hikaru Manabe, An Amalgamation Nim with Restriction, arXiv:2411.14488, Conjecture 1, asks whether the Grundy value of every three-heap position belongs to the same consecutive even-odd pair as its ordinary nim-sum. We prove the conjecture by obtaining the full Grundy value explicitly.

The legal moves are those of Definitions 4 and 5 of the source: decrease one heap by any positive amount, or merge two heaps when each contains at least two stones. Thus a merge replaces heaps $x_i,x_j\geq2$ by $x_i+x_j$ and $0$.

The formula

For a position $X=(x_1,x_2,x_3)$, write

$$x_i=2u_i+\varepsilon_i, \qquad u_i\geq0, \qquad \varepsilon_i\in\{0,1\}. \tag{1}$$

Here $\oplus$ denotes bitwise exclusive-or and $\mathbin{\&}$ denotes bitwise conjunction. Form a simple graph $H_X$ on the three heap indices by declaring

$$ij\in E(H_X) \quad\Longleftrightarrow\quad u_i>0,\quad u_j>0,\quad u_i\mathbin{\&}u_j=0. \tag{2}$$

Let $e(X)=|E(H_X)|$, and define

$$\delta(X)= \begin{cases} 1,&e(X)=1\text{ or }e(X)=2,\\ 0,&e(X)=0\text{ or }e(X)=3. \end{cases} \tag{3}$$

Then the exact Sprague--Grundy value is

$$\boxed{ \mathcal G(x_1,x_2,x_3) =\bigl(x_1\oplus x_2\oplus x_3\bigr)\oplus\delta(X). } \tag{4}$$

In particular, restricted amalgamation changes the ordinary nim-sum exactly when the compatibility graph has one or two edges, and then changes only its least significant bit.

Proof by the mex characterization

Put

$$q(X)=u_1\oplus u_2\oplus u_3, \qquad \eta(X)=\varepsilon_1\oplus\varepsilon_2\oplus\varepsilon_3, \qquad h(X)=\eta(X)\oplus\delta(X). \tag{5}$$

The proposed value in (4) is equivalently

$$F(X)=2q(X)+h(X). \tag{6}$$

We induct on the strictly decreasing game rank

$$\operatorname{rk}(X) =x_1+x_2+x_3+ \bigl|\{i:x_i>0\}\bigr|. \tag{7}$$

A heap reduction decreases the number of stones, while a merge preserves that number and decreases the number of nonempty heaps. Hence every legal follower has strictly smaller rank, and we may assume its Grundy value equals $F$.

First, fix any integer $q'$ with $0\leq q'<q(X)$. The standard nim move on the half-heaps gives an index $i$ and an integer $u_i'<u_i$ such that

$$u_1\oplus\cdots\oplus u_i' \oplus\cdots\oplus u_3=q'. \tag{8}$$

Both replacements

$$x_i\longmapsto 2u_i', \qquad x_i\longmapsto 2u_i'+1 \tag{9}$$

are legal, because $u_i'<u_i$. Their half-heaps and compatibility graphs agree, while their least significant bits are opposite. Consequently their proposed values are precisely

$$2q' \quad\text{and}\quad 2q'+1. \tag{10}$$

Thus every integer smaller than $2q(X)$ occurs among the Grundy values of the followers.

We next classify the followers satisfying $q(Y)=q(X)$. If $Y$ is obtained by reducing one heap, equality of the half-heap nim-sums forces its half-heap to remain unchanged. Therefore the only possibility is

$$2u_i+1\longmapsto 2u_i. \tag{11}$$

The compatibility graph stays fixed, whereas $\eta$ changes; hence

$$h(Y)=h(X)\oplus1. \tag{12}$$

Suppose instead that heaps $x_i=2u_i+\varepsilon_i$ and $x_j=2u_j+\varepsilon_j$ are merged. Their new half-heap is

$$\left\lfloor\frac{x_i+x_j}{2}\right\rfloor =u_i+u_j+\varepsilon_i\varepsilon_j. \tag{13}$$

Consequently $q(Y)=q(X)$ holds exactly when

$$u_i\oplus u_j =u_i+u_j+\varepsilon_i\varepsilon_j. \tag{14}$$

Using

$$u_i+u_j =(u_i\oplus u_j)+2(u_i\mathbin{\&}u_j), \tag{15}$$

we see that (14) is equivalent to

$$u_i\mathbin{\&}u_j=0, \qquad \varepsilon_i\varepsilon_j=0. \tag{16}$$

Because a legal merge requires $u_i,u_j>0$, the merged pair is an edge of $H_X$. If the remaining half-heap satisfies $u_k>0$, then it is compatible with the merged half-heap precisely when it was compatible with both original half-heaps:

$$(u_i+u_j)\mathbin{\&}u_k=0 \quad\Longleftrightarrow\quad u_i\mathbin{\&}u_k=0 \ \text{and}\ u_j\mathbin{\&}u_k=0. \tag{17}$$

If $u_k=0$, none of the three relevant edges involving $k$ exists. Thus, in all cases, the possible edge-count transitions are exactly

$$e(X)=1\longmapsto e(Y)=0, \qquad e(X)=2\longmapsto e(Y)=0, \qquad e(X)=3\longmapsto e(Y)=1. \tag{18}$$

In every case $\delta(Y)=\delta(X)\oplus1$. A merge preserves the xor of the least significant heap bits, so $\eta(Y)=\eta(X)$. Therefore (12) also holds for every merge preserving $q$.

It follows that no follower $Y$ has $F(Y)=F(X)$: followers with different $q$ lie in different consecutive even-odd pairs, and followers with the same $q$ have the opposite bit by (12).

Finally, if $h(X)=1$, the remaining smaller value $2q(X)$ must also occur. If some $\varepsilon_i=1$, the legal reduction (11) preserves $q$ and changes $h$ to $0$. Otherwise all three $\varepsilon_i$ vanish, and

$$1=h(X)=\delta(X). \tag{19}$$

Hence $e(X)=1$ or $2$. Choose any edge of $H_X$. Its two heaps are positive even integers at least two, so their merge is legal; by (16)--(18), it preserves $q$ and changes $h$ to $0$. In either case there exists a follower with value $2q(X)$.

We have proved that every integer smaller than $F(X)$ occurs as a follower value, while $F(X)$ itself does not. Hence

$$\mathcal G(X) =\operatorname{mex}\{\mathcal G(Y):Y\text{ is a legal follower of }X\} =F(X), \tag{20}$$

completing the induction and proving (4).

Resolution of the conjecture

Since $\delta(X)\in\{0,1\}$, equation (4) immediately gives

$$\left\lfloor\frac{\mathcal G(x_1,x_2,x_3)}{2}\right\rfloor = \left\lfloor\frac{x_1\oplus x_2\oplus x_3}{2}\right\rfloor. \tag{21}$$

Thus, for every $n\geq0$,

$$\mathcal G(x_1,x_2,x_3)\in\{2n,2n+1\} \quad\Longleftrightarrow\quad x_1\oplus x_2\oplus x_3\in\{2n,2n+1\}. \tag{22}$$

This proves both clauses of Manabe's Conjecture 1 and strengthens them to the exact closed formula (4).