The i-Mark conjecture on positions with Sprague–Grundy value two

An infinite family of counterexamples to the conjectured Grundy-two characterization

In Some i-Mark games, Theoretical Computer Science 885 (2021), 116--124, Oren Friman and Gabriel Nivasch formulate Conjecture 4 for the normal-play game $i\text{-}\mathrm{Mark}(\{s\},\{d\})$. The published conjecture assumes only that $s$ and $d$ are relatively prime, where $s\geq1$ and $d\geq2$. We disprove it with infinitely many coprime parameters satisfying even the stronger condition $d>s$.

From a heap of size $n$, the legal options are $n-s$ when $n\geq s$, and $n/d$ when $n>0$ and $d\mid n$. The Sprague--Grundy value is therefore

$$g(0)=0,\qquad g(n)=\operatorname{mex}\Bigl( \{g(n-s):n\geq s\} \cup \{g(n/d):d\mid n\} \Bigr) \quad(n>0). \tag{1}$$

Conjecture 4 asserts that $g(n)=2$ is possible only when either $n=sd$, or $n$ lies in one of the forward orbits of

$$T(u)=d(u+s), \tag{2}$$

with respective starting points

$$a_0=2ds, \qquad b_0^{(j)}=jd\quad(1\leq j\leq s-1). \tag{3}$$

The smallest strict-interior counterexample. Choose

$$s=3,\qquad d=4,\qquad n=16. \tag{4}$$

Thus $\gcd(s,d)=1$ and $d>s$. Applying the defining recurrence (1) gives the complete initial values

$$\begin{array}{c|rrrrrrrrrrrrrrrrr} n&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline g(n)&0&0&0&1&1&1&0&0&2&1&1&0&0&0&1&1&2 \end{array}. \tag{5}$$

In particular, the two legal options from $16$ are $13$ and $4$, so

$$g(16)=\operatorname{mex}\{g(13),g(4)\} =\operatorname{mex}\{0,1\}=2. \tag{6}$$

However, the exceptional singleton in the conjecture is $sd=12$. Its orbit seeds are

$$a_0=24,\qquad b_0^{(1)}=4,\qquad b_0^{(2)}=8, \tag{7}$$

and the corresponding next terms are

$$T(4)=28,\qquad T(8)=44,\qquad T(24)=108. \tag{8}$$

Since $T(u)=4(u+3)>u$ for every nonnegative $u$, none of these increasing orbits contains $16$. Thus $g(16)=2$ although $16$ belongs to none of the conjectured exceptional families.

An infinite family. More generally, let

$$s=3,\qquad d\geq4\text{ even},\qquad 3\nmid d, \qquad n=4d. \tag{9}$$

All such parameters satisfy $\gcd(s,d)=1$ and $d>s$. For $0\leq t<d$, no division move is available, so (1) immediately yields

$$g(t)=\left\lfloor\frac{t}{3}\right\rfloor\bmod 2. \tag{10}$$

At $t=d$, the division option is $1$, which has Grundy value $0$. The subtraction option is $d-3$, whose value is determined by (10). Consequently,

$$g(d)= \begin{cases} 2,&d\equiv2\pmod6,\\ 1,&d\equiv4\pmod6. \end{cases} \tag{11}$$

Now consider the chain

$$d,\ d+3,\ d+6,\ \ldots,\ d+3(d-1)=4d-3. \tag{12}$$

For $1\leq j\leq d-1$, the integer $d+3j$ is not divisible by $d$, because $\gcd(d,3)=1$. Its only legal option is therefore the preceding term in (12). Hence

$$g(d+3j)=\operatorname{mex}\{g(d+3(j-1))\} \qquad(1\leq j\leq d-1). \tag{13}$$

Starting from either value $1$ or $2$ in (11), the first application of (13) gives $0$, after which the values alternate between $0$ and $1$. Since $d-1$ is odd, the final value is

$$g(4d-3)=0. \tag{14}$$

Furthermore $g(4)=1$ for every $d\geq4$: the subtraction option is $1$, and the only possible division option occurs when $d=4$ and also equals $1$. Therefore

$$g(4d) =\operatorname{mex}\{g(4d-3),g(4)\} =\operatorname{mex}\{0,1\} =2. \tag{15}$$

For these parameters, the conjecture lists the singleton $sd=3d$, the $a$-orbit starting at $6d$, and the two $b$-orbits starting at $d$ and $2d$. But

$$T(d)=d(d+3)>4d,\qquad T(2d)=d(2d+3)>4d,\qquad 6d>4d. \tag{16}$$

Since $T$ is strictly increasing on nonnegative integers, the only listed exceptional positions at most $4d$ are

$$d,\qquad 2d,\qquad 3d. \tag{17}$$

In particular $4d$ is excluded for every even $d\geq4$ with $3\nmid d$, although (15) proves that its Grundy value is $2$. Consequently the necessary condition in Conjecture 4 is false for infinitely many coprime parameter pairs.