On the Sprague–Grundy function of extensions of proper Nim

Abstract

We consider the game of proper Nim, in which two players alternately move by taking stones from n piles. In one move a player chooses a proper subset (at least one and at most $n-1$) of the piles and takes some positive number of stones from each pile of the subset. The player who cannot move is the loser. Jenkyns and Mayberry (Int J Game Theory 9(1):51–63, 1980) described the Sprague–Grundy function of these games. In this paper we consider the so-called selective compound of proper Nim games with certain other games, and obtain a closed formula for the Sprague–Grundy functions of the compound games, when $n\ge 3$. Surprisingly, the case of $n=2$ is much more complicated. For this case we obtain several partial results and propose some conjectures.

1 Introduction

In the classical game of Nim there are n piles of stones and two players move alternately. A move consists of choosing a nonempty pile and taking some positive number of stones from it. The player who cannot move is the loser.

In this paper we consider the following generalization of Nim, called Hypergraph Nim (Boros 2019a; Boros et al. 2019b; Boros 2019c). Let $\mathcal{H}\subseteq 2^I{\setminus }\{\emptyset \}$ be a hypergraph on vertex set $I=\{1, \ldots ,n\}$. We denote by ${\mathbb {Z}}_+$ the set of nonnegative integers, and by ${\mathbb {Z}}_+^I$ the set of positions of the associated Hypergraph Nim game. Starting from a position $x = (x_1, \ldots , x_n) \in {\mathbb {Z}}_+^I$ two players alternate in choosing a hyperedge $H\in \mathcal{H}$ and decreasing $x_i$ to a smaller nonnegative integer for every vertex $i\in H$. In particular, H cannot be chosen if $x_i=0$ for some $i\in H$. The player who cannot move is losing. We denote the obtained game by Nim $_\mathcal{H}$ and call the corresponding class of games Hypergraph Nim

This class generalizes several families of games considered in the literature. For instance, the case of $\mathcal{H}=\{\{1\}, \ldots , \{n\}\}$ is the classical Nim. The case of $\mathcal{H}=\{S\subseteq I\mid 1 \le |S| \le k\}$, where $k<n$, was considered by Moore (1910). He called this game Nim ${}_k$. Jenkyns and Mayberry (1980) analyzed further the special case of $k=n-1$. In these games an arbitrary proper subset of the piles can be chosen in a move. For this reason, we refer to these games as proper Nim. In Boros et al. (2018) the case of $\mathcal{H}=\{S\subseteq V\mid |S|=k\}$ was considered and called exact k-Nim.

Hypergraph Nim belongs to the family of impartial games, studied e.g., in (Albert et al. 2007; Berlekamp 2001–2004; Conway 1976; Grundy 1939; Sprague 1935–1936, 1937; Smith 1966). It is known that the set of positions of an impartial game can uniquely be partitioned into sets of winning and losing positions. Every move from a losing position goes to a winning one, while from a winning position there always exists a move to a losing one. This partition shows how to win the game whenever possible. The so-called Sprague–Grundy (in short, SG) function ${\mathcal {G}}_\varGamma$ of an impartial game $\varGamma$ provides a refinement of the above partition. Namely, for $x\in {\mathbb {Z}}_+^I$ we have ${\mathcal {G}}_\varGamma (x)=0$ if and only if x is a losing position. The notion of the SG function for impartial games was introduced by Sprague (1935–1936, 1937); Grundy (1939); it plays a fundamental role in the analysis of composite impartial games. We recall the precise definition of the SG function in the beginning of Sect. 2.

Bouton (1901–1902) solved the classical Nim and described the winning strategy for it. Moore (1910) characterized the set of losing positions of Nim ${}_k$. Jenkyns and Mayberry (1980) described also the set of positions in which the SG value is 1, and provided an explicit formula of the SG function for proper Nim. Let us note that it seems difficult to extend this result for Nim ${}_k$ such that $1<k<n-1$. For instance, no closed formula is known for the SG function when $n=4$ and $k=2$. In Boros et al. (2018) the SG function of exact k-Nim  was determined by a closed formula whenever $2k\ge n$. Let us add that even winning/losing positions are not known when $2k < n$, e.g., for $n=5$ and $k=2$.

To state our main result we need a few more definitions. To a position $x\in {\mathbb {Z}}_+^I$ we associate

$$\begin{aligned} m(x)=\min _{i\in I} x_i ~~~\text {and}~~~ s(x)=\sum _{i\in I} x_i. \end{aligned}$$

(1)

Furthermore, we say that a hypergraph $\mathcal{H}\subseteq 2^I$ satisfies the min-sum property, if for the SG function ${\mathcal {G}}_\mathcal{H}$ of Nim $_\mathcal{H}$ we have

$$\begin{aligned} {\mathcal {G}}_\mathcal{H}(x) ~=~ F(m(x),s(x)) \end{aligned}$$

(2)

for some function $F:{\mathbb {Z}}_+^2\rightarrow {\mathbb {Z}}_+$. We call $\mathcal{H}$ hereditary if for all $H\in \mathcal{H}$ and $\emptyset \ne H'\subseteq H$ we have $H'\in \mathcal{H}$. We call it non-isolated if each element $i\in I$ is contained in a hyperedge of size at least 2.

Let us consider a finite set J, disjoint from I and a hypergraph ${{\mathcal {K}}}\subseteq 2^J$. We define the extension of $\mathcal{H}\subseteq 2^I$ by ${{\mathcal {K}}}$ as follows:

$$\begin{aligned} \mathcal{H}\boxplus {{\mathcal {K}}}~=~ \mathcal{H}\cup {{\mathcal {K}}}\cup (\mathcal{H}\times {{\mathcal {K}}}), \end{aligned}$$

where $\mathcal{H}\times {{\mathcal {K}}}=\{H\cup K\mid H\in \mathcal{H},~ K\in {{\mathcal {K}}}\}$ is the usual direct product. The game Nim ${}_{\mathcal{H}\boxplus {{\mathcal {K}}}}$ is called the selective compound of the games Nim ${}_\mathcal{H}$ and Nim ${}_{{\mathcal {K}}}$. The selective compound of two games is defined as the game in which a player on its turn can make a move in either one of the two games, or in both (Conway 1976; Smith 1966). We denote by $(x^J;x^I)$ a position of the compound game, where $x^J\in {\mathbb {Z}}_+^J$ and $x^I\in {\mathbb {Z}}_+^I$.

For Nim $_{{\mathcal {K}}}$ and a position $x^J\in {\mathbb {Z}}_+^J$ the maximum number of consecutive moves the players could make in Nim $_{{\mathcal {K}}}$ starting form $x^J$ is called the height of $x^J$ and is denoted by $h_{{\mathcal {K}}}(x^J)$. We call a hypergraph ${{\mathcal {K}}}$ SG-decreasing if the SG function of Nim $_{{\mathcal {K}}}$ coincides with $h_{{\mathcal {K}}}$, in other words, when the SG value can only decrease in a move. There are many SG-decreasing hypergraphs, for instance intersecting hypergraphs, and recognizing if a hypergraph is SG-decreasing is an NP-hard problem Boros (2019a).

Theorem 1

Assume that $n=|I|\ge 3$, and $\mathcal{H}\subseteq 2^I$ is a hereditary non-isolated hypergraph satisfying the min-sum property (2). Assume further that ${{\mathcal {K}}}\subseteq 2^J$ ($I\cap J=\emptyset$) is an SG-decreasing hypergraph. Then for the SG function of the selective compound Nim $_{\mathcal{H}\boxplus {{\mathcal {K}}}}$ we have

$$\begin{aligned} {\mathcal {G}}_{\mathcal{H}\boxplus {{\mathcal {K}}}}(x^J;x^I) ~=~ F(m(x^I),s(x^I)+h_{{\mathcal {K}}}(x^J)). \end{aligned}$$

We can apply this theorem to the selective compound of a proper Nim game with any of the SG-decreasing Hypergraph Nim games, and obtain a closed formula for its SG function using the result of Jenkyns and Mayberry (1980). For instance, we can derive the following statement.

Corollary 1

For $n\ge 3$ let us consider hypergrahs $\mathcal{H}= 2^I{\setminus }\{I,\emptyset \}$ and ${{\mathcal {K}}}=\{\{0\}\}$. To positions $x\in {\mathbb {Z}}_+^I$ of Nim $_\mathcal{H}$ and $x_0\in {\mathbb {Z}}_+$ of Nim $_{{\mathcal {K}}}$ we associate $y=y(x_0;x)=s(x)+x_0-n$ and $z=z(x_0;x)=\left( {\begin{array}{c}y+1\\ 2\end{array}}\right)$. Then we have

$$\begin{aligned} {\mathcal {G}}_{\mathcal{H}\boxplus {{\mathcal {K}}}}(x_0;x) = {\left\{ \begin{array}{ll} s(x)+x_0 &{}\text {if~} m(x)<z,\\ (z-1)+((m(x)-z) \mod (y+1) &{}\text {if~} m(x)\ge z. \end{array}\right. } \end{aligned}$$

(3)

Remark 1

Let us recall that besides selective compounds, disjunctive and conjunctive compounds of impartial games were also considered in Conway (1976) and Smith (1966). In a disjunctive compound players can move in exactly one of the games, while in the conjunctive compound they have to move in all. The SG-theory was developed for disjunctive compounds. Let us note that Moore’s Nim $_k$ is a disjunctive compound only for $k=1$. In particular, proper Nim is not a disjunctive compound, unless $n=2$.

The rest of the paper is organized as follows. In Sect. 2 we prove Theorem 1. In Sect. 3 we study the case of $n=2$. In this case the SG function behaves in a chaotic way, and we only obtain some partial results and state some conjectures. Finally, in the Appendix we consider the SG function of a related game, the so-called slow Nim in which the size of a pile in a move can be reduced by at most one.

2 Proof of Theorem 1

For our proof let us recall first the definition of the SG function of an impartial game. For a subset $S\subseteq {\mathbb {Z}}_+$ of nonnegative integers we associate the value of the smallest integer, not belonging to S:

$$\begin{aligned} mex(S) ~=~ \min _{v\in {\mathbb {Z}}_+{\setminus } S} v. \end{aligned}$$

In particular, $mex(\emptyset )=0$.

To an impartial game $\varGamma$ we associate its Sprague–Grundy function ${\mathcal {G}}_\varGamma$ that assigns to every position x of the game a nonnegative integer defined by the following recursion

$$\begin{aligned} {\mathcal {G}}_\varGamma (x) ~=~ mex \{ {\mathcal {G}}_\varGamma (x') \mid \text {there is a move } x \rightarrow x'\}. \end{aligned}$$

Equivalently, a nonnegative integer valued function g coincides with the SG function ${\mathcal {G}}_\varGamma$ if and only if:

• (i) For any move $x\rightarrow x'$ we have $g(x')\ne g(x)$.

• (ii) For any position x with $g(x)>0$ and for any integer $0\le v< g(x)$ there is a move $x\rightarrow x'$ such that $g(x')=v$.

Lemma 1

It is enough to prove Theorem 1 for the case when the second game is the classical Nim with a single pile.

Proof

Let us consider an arbitrary move $(x^J;x^I)\rightarrow ((x')^J;(x')^I)$ in the compound game. Since Nim $_{{\mathcal {K}}}$ is SG-decreasing we have $h_{{\mathcal {K}}}(x^J) \ge h_{{\mathcal {K}}}((x')^J)$. Thus substituting $x_0=h_{{\mathcal {K}}}(x^J)$, and $x_0'=h_{{\mathcal {K}}}((x')^J)$ we get that $(x_0;x^I)\rightarrow (x_0';(x')^I)$ is a move in the selective compound of Nim $_\mathcal{H}$ and the single pile Nim. Since we use only $h_{{\mathcal {K}}}$ from the game Nim $_{{\mathcal {K}}}$ this substitution proves the lemma, because Nim $_{{\mathcal {K}}}$ is SG-decreasing. $\square$

In the rest of the proof we assume that $J=\{\{0\}\}$. To simplify notation we introduce $I_+=J\cup I=\{0,1,\ldots ,n\}$, and use $(x_0;x)\in {\mathbb {Z}}_+^{I_+}$ to denote a position in the compound game, i.e., $x_0\in {\mathbb {Z}}_+$ and $x\in {\mathbb {Z}}_+^I$. Finally, we denote by $\mathcal{H}_+=\mathcal{H}\boxplus \{\{0\}\}$.

For a position $(x_0;x)\in {\mathbb {Z}}_+^{I_+}$, let $k\in I$ be an index such that $x_k=m(x)$, where m(x) is defined in (1). To such a position we associate a set of positions of Nim $_\mathcal{H}$ as follows

$$\begin{aligned} Z(x_0;x)=\{ z\in {\mathbb {Z}}_+^I \mid z_k=x_k,~ z_i \ge x_i ~(\forall i\not =k), ~~ s(z)=s(x)+x_0\}. \end{aligned}$$

(4)

By the above definition, it holds that

$$\begin{aligned} m(z)=m(x)=x_k \text{ and } s(z)=s(x)+x_0 \text{ for } \text{ all } z \in Z(x_0;x). \end{aligned}$$

(5)

Let us further define

$$\begin{aligned} A(x_0;x)=\{(m(z'),s(z')) \mid \exists z \in Z(x_0;x), \exists \text{ a } \text{ move } z \rightarrow z' \text{ in } \text{ Nim }_{\mathcal{H}}\}. \end{aligned}$$

(6)

Lemma 2

Assume that $\mathcal{H}$ satisfies the min-sum property (2). Then, for any position $(x_0;x)$ of Nim $_{\mathcal{H}_+}$, we have

• (I) $F(m(x), s(x)+x_0) \not \in F(A(x_0;x))$, and

• (II) $\{0,1, \dots , F(m(x), s(x)+x_0)-1\} \subseteq F(A(x_0;x))$,

where $F(A(x_0;x))=\{F(m',s')\mid (m',s')\in A(x_0;x)\}$.

Proof

This follows from (5) and the min-sum property of $\mathcal{H}$. $\square$

Lemma 3

Assume that $\mathcal{H}$ is a hereditary hypergraph, and $(x_0;x)\in {\mathbb {Z}}_+^{I_+}$ is a position of Nim $_{\mathcal{H}_+}$. For any $z \in Z(x_0;x)$ and any move $z\rightarrow z'$ in Nim $_{\mathcal{H}}$, there exists a move $(x_0;x)\rightarrow (x_0';x')$ in Nim $_{\mathcal{H}_+}$ such that $m(x')=m(z')$ and $s(x')+x'_0=s(z')$.

Proof

Assume that $k\in I$ is the index we used in the definition of $Z(x_0;x)$. Let $z_i=x_i+\alpha _i$ for $i\in I$ such that $\alpha _k=0$, $\sum _{i\in I}\alpha _i=x_0$, and $\alpha _i\ge 0$ for all $i \in I$. Let us define $x'\in {\mathbb {Z}}_+^I$ by

$$\begin{aligned} x_i' = {\left\{ \begin{array}{ll} x_i &{} \text{ if } z_i' \ge x_i,\\ z_i' &{} \text{ otherwise }, \end{array}\right. } \end{aligned}$$

and set $x_0'=\sum _{i\in I}\max \{z_i'-x_i, 0\}$. Then $(x_0';x')\in {\mathbb {Z}}_+^{I_+}$, $x' \le x$ and $x_0'\le x_0$. Define $S=\{i\in I\mid x'_i<x_i\}$, and note that S is contained in the hyperedge $\{i\in I\mid z'_i<z_i\}$ of $\mathcal{H}$ by the above construction. Thus, if $S\ne \emptyset$ then $(x_0;x)\rightarrow (x_0';x')$ is a move in Nim $_{\mathcal{H}_+}$ by the hereditary property of $\mathcal{H}$. If $S=\emptyset$, then $x'_0<x_0$ because the move $z\rightarrow z'$ reduces at least one component strictly, and thus $(x_0;x)\rightarrow (x_0';x')$ is also a move in Nim $_{\mathcal{H}_+}$. $\square$

Lemma 4

Assume that $n\ge 3$ and the hypergraph $\mathcal{H}\subseteq 2^I$ is non-isolated and hereditary. Let us consider a position $(x_0;x)\in {\mathbb {Z}}_+^{I_+}$ of Nim $_{\mathcal{H}_+}$. For any move $(x_0;x)\rightarrow (x_0';x')$ in Nim $_{\mathcal{H}_+}$, there exist a $z \in Z(x_0;x)$ and a move $z\rightarrow z'$ in Nim $_{\mathcal{H}}$ such that $z' \in Z(x_0';x')$.

Proof

Assume that $k\in I$ is the index we used in the definition of $Z(x_0;x)$. Furthermore, let $\ell$ denote an index such that $x'_\ell =m(x')$ and $\ell \in I$. We consider separately four cases.

Case 1: $x_0'< x_0$ and $x_i' = x_i$ for all $i \in I$. For an arbitrary index $j\in I$, we define positions $z,z'\in {\mathbb {Z}}_+^I$ by

$$\begin{aligned} z_i = {\left\{ \begin{array}{ll} x_j+x_0 &{} \text{ if } i=j,\\ x_i &{} \text{ otherwise }, \end{array}\right. } ~~~~ z_i' = {\left\{ \begin{array}{ll} x'_j+x'_0 &{} \text{ if } i=j,\\ x'_i &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$

(7)

Note that $\{j\} \in \mathcal{H}$ by the assumption on $\mathcal{H}$. Since $z'_j < z_j$ and $z_i' = z_i$ for all $i \in I {\setminus } \{j\}$, we have $z \in Z(x_0;x)$ and $z\rightarrow z'$ is a move in Nim $_{\mathcal{H}}$.

Case 2: There is an index $j \in I$ such that $j\not = k,\ell$ and $x_j' < x_j$. In this case, we again can use positions $z,z'\in {\mathbb {Z}}_+^I$, defined in (7), since

$$\begin{aligned} \{i \in I \mid z'_i<z_i\} = \{i \in I \mid x'_i<x_i\} \in \mathcal{H}, \end{aligned}$$

(8)

implies that $z \in Z(x_0;x)$ and $z\rightarrow z'$ is a move in Nim $_{\mathcal{H}}$.

Case 3: $k=\ell$, $x'_k<x_k$ and $x'_i=x_i$ for all $i \in I{\setminus } \{k\}$. Since $\mathcal{H}$ is non-isolated and hereditary, there must exist an index $j \in I{\setminus } \{k\}$ such that $\{k,j\} \in \mathcal{H}$. Similarly to the previous case we consider the positions $z,z'\in {\mathbb {Z}}_+^I$ as defined in (7). Then we have again $z \in Z(x_0;x)$ and that $z\rightarrow z'$ is a move in Nim $_{\mathcal{H}}$, since $\{i\mid z'_i<z_i\}\subseteq \{k,j\}$ and $\mathcal{H}$ is hereditary.

Case 4: $k \not =\ell$ and $x'_i=x_i$ for all $i\in I{\setminus }\{k,\ell \}$. Note that in this case we must have $x'_\ell < x_\ell$, because $\emptyset \ne \{i\in I\mid x'_i<x_i\}\subseteq \{k,\ell \}$, $x_k=m(x)$, and $x'_\ell =m(x')$. Since $n\ge 3$, there is an index j such that $j \in I{\setminus } \{k,\ell \}$. Let us define positions $z,z'\in {\mathbb {Z}}_+^I$ by

$$\begin{aligned} z_i = {\left\{ \begin{array}{ll} x_\ell +(x_0-x_0') &{} \text{ if } i=\ell ,\\ x_j+x_0' &{} \text{ if } i=j,\\ x_i &{} \text{ otherwise }, \end{array}\right. } ~~~~ z_i' = {\left\{ \begin{array}{ll} x'_j+x_0' &{} \text{ if } i=j,\\ x'_i &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$

Then we have $z \in Z(x_0;x)$ and $z\rightarrow z'$ is a move in Nim $_{\mathcal{H}}$, because (8) holds in this case, too.

Finally note that in all four cases we have $z' \in Z(x'_0;x')$ by the definitions of $z'$ and $Z(x'_0;x')$. $\square$

Proof of Theorem 1

For a position $(x_0;x)$ of Nim $_{\mathcal{H}_+}$, let $B(x_0;x)=\{(x'_0;x') \mid (x_0;x)\rightarrow (x'_0;x')\}$. Then we have

$$\begin{aligned} \{(m(x'),s(x')+x_0') \mid (x'_0;x') \in B(x_0;x)\}=A(x_0;x), \end{aligned}$$

where $A(x_0;x)$ is as defined in (6). This is because $\{(m(x'),s(x')+x_0') \mid (x'_0;x') \in B(x_0;x)\}\supseteq A(x_0;x)$ follows by Lemmas 2 and 3, and the opposite inclusion follows from Lemmas 2 and 4.

This completes the proof. $\square$

Example 1

Let us illustrate Theorem 1 and Corollary 1 by some numerical examples for the proper Nim with $n=3$. Let us introduce $\varGamma =$ Nim $_\mathcal{H}$ and $\varGamma _+=$ Nim $_{\mathcal{H}_+}$.

Consider first the position $(x_0;x)=(0;3,3,4)$. In this case we have $m=m(x)=3$, $y=y(0;x)=1$ and thus $z=z(0;x)=\left( {\begin{array}{c}y(0;x)+1\\ 2\end{array}}\right) +1=2$, where $y(x_0;x)$ and $z(x_0;x)$ are as defined in Corollary 1. Since $m\ge z$ we get for the SG function by (3) that

$$\begin{aligned} {\mathcal {G}}_{\varGamma _+}(0;3,3,4)=(z-1)+((m-z)\mod (y+1))=1+(1\mod 2)=2. \end{aligned}$$

Note that for any move $x\rightarrow x'$ in $\varGamma _+$ (and since $x_0=0$, also in $\varGamma$) we have $s(x')\ge m(x)=3$. Thus, to argue that (3) provides the SG value of 2 for this position, we only need to consider moves to positions $x'$ for which $m(x')\ge z(0;x')$. We list these positions (up to a permutation of the coordinates) in the table below:

$$\begin{aligned} \begin{array}{c|c|c|c|l} (0;x') &{} \,m(x')\, &{} \,y(0;x')\, &{} \,z(0;x')\, &{} \,{\mathcal {G}}=(z-1) + ((m-z) \mod (y+1)) \\ \hline (0;3,2,2) &{} 2 &{} 1 &{} 2 &{} \,1=(2-1)+((2-2)\mod (1+1)) \\ (0;3,3,3) &{} 3 &{} 0 &{} 1 &{} \,0=(1-1)+((3-1)\mod (0+1)) \end{array} \end{aligned}$$

Let us next consider the position $(x_0;x_1,x_2,x_3)=(1;3,3,4)\in {\mathbb {Z}}_+^4$ of the game $\varGamma _+$. In this case we have $m(x)=3$, $y(x_0;x)=2$, and thus $z(x_0;x)=\left( {\begin{array}{c}2+1\\ 2\end{array}}\right) +1=4$. Since $m(x)<z(x_0;x)$ we get by (3) that

$$\begin{aligned} {\mathcal {G}}_{\varGamma _+}(1;3,3,4)=s(x)+x_0=11. \end{aligned}$$

Note that for any move $(x_0;x)\rightarrow (x_0';x')$ we have ${\mathcal {G}}_{\varGamma _+}(x_0';x')\le x_0'+s(x')<x_0+s(x)=11$. We list below some moves $(x_0;x)\rightarrow (x_0';x')$ such that $m(x')<z(x_0';x')$ and the corresponding values by (3):

$$\begin{aligned} \begin{array}{c|c|c|c|c} (x_0';x') &{} \,m(x')\, &{} \,y(x_0';x')\, &{} \,z(x_0';x')\, &{} \,{\mathcal {G}}=s(x')+x_0' \\ \hline (1;3,2,4) &{} 2 &{} 4 &{} 11 &{} 10 \\ (1;3,1,4) &{} 1 &{} 6 &{} 22 &{} 9\\ (1;3,0,4) &{} 0 &{} 8 &{} 37 &{} 8\\ (1;3,0,3) &{} 0 &{} 7 &{} 29 &{} 7\\ (1;3,0,2) &{} 0 &{} 6 &{} 22 &{} 6\\ (1;3,0,1) &{} 0 &{} 5 &{} 16 &{} 5\\ (1;3,0,0) &{} 0 &{} 4 &{} 11 &{} 4\\ (0;3,0,0) &{} 0 &{} 3 &{} 7 &{} 3 \end{array} \end{aligned}$$

Note finally that (0; 3, 3, 4) is reachable from (1; 3, 3, 4) and any position reachable from (0; 3, 3, 4) is also reachable from (1; 3, 3, 4), and thus the above computations show that

$$\begin{aligned} 11={\text {mex}}\{{\mathcal {G}}_{\varGamma _+}(x_0';x_1',x_2',x_3') \mid (1;3,3,4)\rightarrow (x_0';x_1',x_2',x_3')\}. \end{aligned}$$

3 The case of $n=2$

Surprisingly, this case seems to be much more difficult than the case of $n\ge 3$. Here we present some partial results and conjectures. If Nim $_\mathcal{H}$ is a proper Nim game, then let us call Nim $_{\mathcal{H}_+}$ an extended proper Nim.

3.1 Upper and lower bounds for the SG function of extended proper Nim

For the analysis of the extended proper Nim with $n=2$, we will need a few more properties of the SG function of extended proper Nim games. Let us consider the hypergraph $\mathcal{H}=2^I{\setminus }\{\emptyset ,I\}$.

Lemma 5

The SG function ${\mathcal {G}}_{\mathcal{H}_+}(x_0;x)$ is strictly monotone with respect to $x_0$.

Proof

Consider two positions $(x_0;x)$ and $(x'_0;x)$ such that $x_0 > x'_0$. Since $(x'_0;x)$ and any position reachable from $(x'_0;x)$ are also reachable from $(x_0;x)$, we must have ${\mathcal {G}}_{\mathcal{H}_+}(x_0;x) > {\mathcal {G}}_{\mathcal{H}_+}(x'_0;x)$ by the definition of the SG function. $\square$

To a position $(x_0;x)\in {\mathbb {Z}}_+^{I_+}$ let us associate

$$\begin{aligned} \ell (x_0;x) = x_0 + {\mathcal {G}}_{\mathcal{H}}(x). \end{aligned}$$

Lemma 6

We have

$$\begin{aligned} \ell (x_0;x) \le {\mathcal {G}}_{\mathcal{H}_+}(x_0; x) \le x_0+s(x). \end{aligned}$$

(9)

Proof

The upper bound is obvious, while the lower one follows from Lemma 5. $\square$

In the rest of this section we consider $n=2$. In this case the extended game is Nim $_{\mathcal{H}_+}$ where $\mathcal{H}_+=\{\{0\},\{1\},\{2\},\{0,1\},\{0,2\}\}$. For simplicity, we change our notation. We denote by $x=(x_0,x_1,x_2)\in {\mathbb {Z}}_+^3$ a position of the extended game and by ${\mathcal {G}}(x)$ the value of its SG function. Since proper Nim with $n=2$ is the same as a 2-pile Nim, we also use $s(x)=x_0+x_1+x_2$ and $\ell (x)=x_0+(x_1\oplus x_2)$, where $\oplus$ is the so called Nim sum, see e.g., 3.

In this case Lemma 6 turns into the following inequalities

$$\begin{aligned} \ell (x) \le {\mathcal {G}}(x) \le s(x). \end{aligned}$$

(10)

If $x_0 = 0$, the lower bound is attained. Obviously, the upper bound is attained if $x_1 = 0$ or $x_2 = 0$. We shall see that both bounds are attained in many other cases.

3.2 Shifting $x_1$ and $x_2$ by the same power of 2

We present simple conditions under which the SG function ${\mathcal {G}}(x)$ is invariant with respect to a shift of $x_1$ and $x_2$ by the same power of 2.

Let us note that ${\mathcal {G}}$ is not a monotone increasing function of $x_1$ and/or $x_2$, in contrast to $x_0$. The next lemma shows that a weaker property still holds, if we use power of 2 increments.

Lemma 7

For any $k \in {\mathbb {Z}}_{+}$, let us set $\varDelta ^k=(0,2^k,2^k)$. Then,

$$\begin{aligned} \begin{array}{lll} \mathcal{G}(x +\varDelta ^k) &{}= \mathcal{G}(x) &{} {\text {if }} \mathcal{G}(x) < 2^k, {\text { and}}\\ \mathcal{G}(x +\varDelta ^k) &{}\ge 2^k &{} {\text {if }} {\mathcal {G}}(x)\ge 2^k. \end{array} \end{aligned}$$

Proof

We show this by induction on x. We first note that $\mathcal{G}(0,0,0)=\mathcal{G}(0,a,a)$ holds for any positive integer a, which proves the base of the induction.

For a position x, we assume that the statement is true for all $x'$ with $x' \le x$, $x'\ne x$ and show that it holds for x by separately considering the cases $\mathcal{G}(x)<2^k$ and $\mathcal{G}(x)\ge 2^k$.

Case 1: $\mathcal{G}(x) < 2^k$. We note that if $x \rightarrow x'$ is a move then so is $x+\varDelta ^k \rightarrow x'+\varDelta ^k$. For any v with $0 \le v< \mathcal{G}(x) < 2^k$, there exists a move $x \rightarrow x'$ such that $\mathcal{G}(x')=v$ by the definition of the SG function. It follows from the induction hypothesis that $\mathcal{G}(x'+\varDelta ^k)=\mathcal{G}(x')=v$. Since $x + \varDelta ^k \rightarrow x'+ \varDelta ^k$ is a move, we have $\mathcal{G}(x+\varDelta ^k)\ne v$. Since this applies for values $0\le v<\mathcal{G}(x)$, we can conclude that $\mathcal{G}(x+\varDelta ^k)\ge \mathcal{G}(x)$.

We will show next that for any position $x'$ obtained from $x + \varDelta ^k$ by a move $x + \varDelta ^k \rightarrow x'$, the SG function values of x and $x'$ differ, $\mathcal{G}(x') \not = \mathcal{G}(x)$.

Let $x'=(x'_0, x_1',x_2+2^k)$ without loss of generality. If $x_1'< 2^k$, then we have

$$\begin{aligned} \mathcal{G}(x')\ge \ell (x')\ge x_1' \oplus (x_2+2^k) \ge 2^k > \mathcal{G}(x). \end{aligned}$$

If $x_1' \ge 2^k$ and $\mathcal{G}(x'-\varDelta ^k)=\mathcal{G}(x_0',x_1'-2^k,x_2) \ge 2^k$, then by induction hypothesis, $\mathcal{G}(x')=\mathcal{G}((x'-\varDelta ^k)+\varDelta ^k)\ge 2^k$, which implies that $\mathcal{G}(x') \not =\mathcal{G}(x)$. Finally, if $x_1' \ge 2^k$ and $\mathcal{G}(x'-\varDelta ^k) < 2^k$, then $\mathcal{G}(x'-\varDelta ^k)\not =\mathcal{G}(x)$, since $x \rightarrow x'-\varDelta ^k$ is a move. By our induction hypothesis, we have $\mathcal{G}(x')=\mathcal{G}(x'-\varDelta ^k)\not =\mathcal{G}(x)$. This completes the proof of the case $\mathcal{G}(x) < 2^k$.

Case 2: $\mathcal{G}(x)\ge 2^k$. By definition, for any integer v with $0 \le v < 2^k \le \mathcal{G}(x)$, there exists a move $x \rightarrow x'$ such that $\mathcal{G}(x')=v$. By induction hypothesis, we have $\mathcal{G}(x')=\mathcal{G}(x'+\varDelta ^k)$. Since $x'+\varDelta ^k$ is reachable from $x+\varDelta ^k$, we obtain $\mathcal{G}(x+\varDelta ^k)\ge 2^k$.

$\square$

To illustrate the first claim of the lemma, let us note that:

$$\begin{aligned} \begin{array}{rll} \mathcal{G}(1,0,0) &{}= 1 &{}< 2\\ \mathcal{G}(2,0,0) &{}= 2 &{}< 4\\ \mathcal{G}(3,0,0) &{}= 3 &{}< 4\\ \mathcal{G}(4,0,0) &{}= 4 &{}< 8\\ \mathcal{G}(0,1,2) &{}= 3 &{}< 4\\ \mathcal{G}(1,0,1) &{}= 2 &{}< 4\\ \mathcal{G}(1,1,1) &{}= 3 &{}< 4\\ \mathcal{G}(1,1,2) &{}= 4 &{}< 8\\ \mathcal{G}(2,1,3) &{}= 6 &{}< 8\\ \mathcal{G}(3,1,1) &{}= 5 &{}< 8. \end{array} \end{aligned}$$

Furthermore, computations show that

$$\begin{aligned} \begin{array}{rll} \mathcal{G}(1,2,6) &{}= 5 &{}< 8 \\ \mathcal{G}(1,5,6) &{}= 11 &{}< 16\\ \mathcal{G}(2,5,5) &{}= 11 &{}< 16 \end{array} \end{aligned}$$

Hence, for all $i \in {\mathbb {Z}}_{+}$ we have

$$\begin{aligned} \begin{array}{rllll} \mathcal{G}(1,0,0) &{}= \mathcal{G}(1,2,2) &{}= \mathcal{G}(1,4,4) &{}= \cdots &{}= \mathcal{G}(1,2i,2i) = 1\\ \mathcal{G}(2,0,0) &{}= \mathcal{G}(2,4,4) &{}= \mathcal{G}(2,8,8) &{}= \cdots &{}= \mathcal{G}(2,4i,4i) = 2\\ \mathcal{G}(3,0,0) &{}= \mathcal{G}(3,4,4) &{}= \mathcal{G}(3,8,8) &{}= \cdots &{}= \mathcal{G}(3,1+4i,1+4i) = 3\\ \mathcal{G}(4,0,0) &{}= \mathcal{G}(4,8,8) &{}= \mathcal{G}(4,16,16) &{}= \cdots &{}= \mathcal{G}(4,8i,8i) = 4\\ \mathcal{G}(1,0,1) &{}= \mathcal{G}(1,4,5) &{}= \mathcal{G}(1,8,9) &{}= \cdots &{}= \mathcal{G}(1,4i,1+4i) = 2\\ \mathcal{G}(0,1,2) &{}= \mathcal{G}(0,5,6) &{}= \mathcal{G}(0,9,10) &{}= \cdots &{}= \mathcal{G}(0,1+4i,2+4i) = 3\\ \mathcal{G}(1,1,1) &{}= \mathcal{G}(1,5,5) &{}= \mathcal{G}(1,9,9) &{}= \cdots &{}= \mathcal{G}(1,1+4i,1+4i) = 3\\ \mathcal{G}(1,1,2) &{}= \mathcal{G}(1,9,10) &{}= \mathcal{G}(1,17,18) &{}= \cdots &{}= \mathcal{G}(1,1+8i,2+8i) = 4\\ \mathcal{G}(2,1,3) &{}= \mathcal{G}(2,9,11) &{}= \mathcal{G}(2,17,19) &{}= \cdots &{}= \mathcal{G}(2,1+8i,3+8i) = 6\\ \mathcal{G}(3,1,1) &{}= \mathcal{G}(3,9,9) &{}= \mathcal{G}(3,17,17) &{}= \cdots &{}= \mathcal{G}(3,1+8i,1+8i) = 5\\ \mathcal{G}(1,2,6) &{}= \mathcal{G}(1,10,14) &{}= \mathcal{G}(1,18,22) &{}= \cdots &{}= \mathcal{G}(1,2+8i,6+8i) = 5\\ \mathcal{G}(1,5,6) &{}= \mathcal{G}(1,21,22) &{}= \mathcal{G}(2,47,48) &{}= \cdots &{}= \mathcal{G}(1,5+16i,6+16i) = 11\\ \mathcal{G}(2,5,5) &{}= \mathcal{G}(2,21,21) &{}= \mathcal{G}(1,37,37) &{}= \cdots &{}= \mathcal{G}(2,5 + 16i, 5 + 16i) = 11. \end{array} \end{aligned}$$

To illustrate the second claim of the lemma, let us consider $k = 1$, $x = (1,2,3)$, $x + (0,2,2) = (1,4,5)$, and note that $\mathcal{G}(1,2,3) = 6$ while $\mathcal{G}(1,4,5)=2$.

Lemma 7 results immediately the following claim.

Corollary 2

For any $k \in {\mathbb {Z}}_+$, if $\mathcal{G}(x) < 2^k$ and $x \ge \varDelta ^k$ then $\mathcal{G}(x-\varDelta ^k)=\mathcal{G}(x)$. $\square$

We also need the following elementary arithmetic statement.

Lemma 8

Let a be an integer with $2^{k-1} \le a < 2^k$ for some positive integer k. Then we have $a\oplus b>b$ if $0\le b < 2^{k-1}$, and $a\oplus b< b$ if $2^{k-1} \le b < 2^k$.

Proof

The claim results immediately from the definition of the Nim-sum, since the binary representation of a includes $2^{k-1}$. $\square$

For a nonnegative integer v, let k(v) denote the unique nonnegative integer such that $2^{k(v)-1} \le v < 2^{k(v)}$.

The following consequence of Lemma 7 provides a characterization of the SG values.

Theorem 2

Let $x = (x_0, x_1, x_2)$ be a position with $\mathcal{G}(x) = v$ and $x_1 \le x_2$. Then there exists a position ${\hat{x}}$ such that ${\hat{x}} \le (v, 2^{k(v)-1}-1, 2^{k(v)}-1)$, $\mathcal{G}({\hat{x}})=\mathcal{G}(x)$, and $x={\hat{x}}+\lambda \varDelta ^{k(v)}$ for some $\lambda \in {\mathbb {Z}}_{+}$.

Proof

By Corollary 2, there exists a position ${\hat{x}}= ({\hat{x}}_0, {\hat{x}}_1, {\hat{x}}_2) = x-\lambda \varDelta ^{k(v)}$ for a nonnegative integer $\lambda$ such that $\mathcal{G}({\hat{x}})=\mathcal{G}(x)=v$ and ${\hat{x}}_1< 2^{k(v)}$. We show that ${\hat{x}}_0 \le v$, ${\hat{x}}_1< 2^{k(v)-1}$, and ${\hat{x}}_2< 2^{k(v)}$, which will imply the statement. Since

$$\begin{aligned} v=\mathcal{G}({\hat{x}})\ge \ell ({\hat{x}})={\hat{x}}_0+({\hat{x}}_1 \oplus {\hat{x}}_2), \end{aligned}$$

(11)

${\hat{x}}_0 \le v$ holds. Moreover, if ${\hat{x}}_2 \ge 2^{k(v)}$, then ${\hat{x}}_1 \oplus {\hat{x}}_2 \ge 2^{k(v)}$ by ${\hat{x}}_1< 2^{k(v)}$, which again contradicts (11), since $v < 2^{k(v)}$ by definition of k(v). Thus we have ${\hat{x}}_2 < 2^{k(v)}$. Suppose that $2^{k(v)-1} \le {\hat{x}}_1\le {\hat{x}}_2$. Then ${\hat{x}} \rightarrow (0,{\hat{x}}_1,{\hat{x}}_1\oplus v)$ is a move, since ${\hat{x}}_1\oplus v < {\hat{x}}_1 \le {\hat{x}}_2$ by Lemma 8. This together with $\mathcal{G}(0,{\hat{x}}_1,{\hat{x}}_1\oplus v)=v$ contradicts that $\mathcal{G}({\hat{x}})=v$. $\square$

For any nonnegative integer v, let us define

$$\begin{aligned} Core(v) ~=~ \{x=(x_0, x_1,x_2)\mid \mathcal{G}(x)=v, x_0\le v, x_1< 2^{k(v)-1}, x_2< 2^{k(v)}\}. \end{aligned}$$

Then, Theorem 2 shows that every position x with $\mathcal{G}(x)=v$ and $x_1 \le x_2$ has a position ${\hat{x}}\in Core(v)$ such that $x={\hat{x}}+\lambda \varDelta ^{k(v)}$ for some nonnegative integer $\lambda$.

Note that Core(v) has at most $2v^3$ positions, and by the definition of the SG function, we can compute their SG value in $O(v^5)$ time. This implies the following corollary.

Corollary 3

For any $v\in {\mathbb {Z}}_{+}$ and for any position x we can compute the value ${\mathcal {G}}(x)$, if ${\mathcal {G}}(x) \le v$, or prove that ${\mathcal {G}}(x)>v$ in $O(v^5)$ time. $\square$

This implies that we can compute the SG value of a position $x\in {\mathbb {Z}}_+^3$ in polynomial time in ${\mathcal {G}}(x)$, regardless the magnitude of the coordinates of x.

3.3 Some conjectures and partial results for them

In this subsection we assume that $x_1\le x_2$.

3.3.1 Case 1: $x_1$ is a power of 2

Computational results suggest that if $x_1$ is a power of 2 then ${\mathcal {G}}(x)$ equals either the lower or the upper bound in accordance with the following simple rule.

Conjecture 1

Given $x = (x_0, x_1, x_2)$ such that $x_0 \in {\mathbb {Z}}_+$ and $x_2 \ge x_1 = 2^k$ for some nonnegative integer k, then ${\mathcal {G}}(x) = \ell (x) = x_0 + (x_1 \oplus x_2)$ for any

$$\begin{aligned} x_2 = (2j+1) 2^k + m \text{ such } \text{ that } j \in {\mathbb {Z}}_+ \text{ and } 0 \le m < 2^k - x_0. \end{aligned}$$

(12)

Otherwise, ${\mathcal {G}}(x) = s(x) = x_0 + x_1 + x_2$.

Note that (12) can be equivalently rewritten as

$$\begin{aligned} 2^k \le (x_2 \mod 2^{k+1}) < 2^{k+1} - x_0. \end{aligned}$$

It is also convenient to equivalently reformulate this conjecture replacing ${\mathcal {G}}(x)$ by $\delta (x) = s(x) - {\mathcal {G}}(x)$. For any nonnegative integer $a,b,c \in {\mathbb {Z}}_{+}$ let us introduce the function

$$\begin{aligned} f(a, b, c) ~=~ {\left\{ \begin{array}{ll} 1, &{} \text{ if } (c \mod a) \ge b,\\ 0, &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$

In particular, $f(a, b, c) = 0$ whenever $b \ge a$.

It is not difficult to verify that Conjecture 1 can be reformulated as follows:

Given $x = (x_0, x_1, x_2)$ such that $x_0 \in {\mathbb {Z}}_+$ and $x_2 \ge x_1 = 2^k$ for some $k \in {\mathbb {Z}}_+$, then

$$\begin{aligned} \delta (x) = 2^{k+1} f(2^{k+1}, x_0 + 2^k, x_0 + x_2) = 2x_1 f(2x_1, x_0 + x_1, x_0 + x_2). \end{aligned}$$

(13)

We can illustrate this by several simple examples.

$$\begin{aligned} \begin{array}{c|c|c|l} x_0 &{} x_1 &{} x_2 &{} \delta (x)\\ \hline 0 &{} 1 &{} 1,2,3,\ldots &{} 2,0,2,0,2,\ldots \\ 0 &{} 2 &{} 2,3,4,\ldots &{} 4,4,0,0,4,4,0,0,4,4,\ldots \\ 0 &{} 4 &{} 4,5,6,\ldots &{} 8,8,8,8,0,0,0,0,8,8,8,8,\ldots \\ 2 &{} 4 &{} 4,5,6,\ldots &{} 8,8,0,0,0,0,0,0,8,8,0,0,0,0,0,0,\ldots \\ \end{array} \end{aligned}$$

The upper bound is attained, whenever $x_0 \ge x_1$; for instance if $x_0 = 2$ and $x_1 \le 2$ then $\delta (x) \equiv 0$.

Note that Conjecture 1, if true, would imply the following useful addition to Lemma 7. Note first that for $x=(x_0,0,x_2)$ we have

$$\begin{aligned} \ell (x_0,0,x_2)= {\mathcal {G}}(x_0, 0 , x_2) = s(x_0, 0, x_2) = x_0 + x_2. \end{aligned}$$

By the conjecture above we also have

$$\begin{aligned} {\mathcal {G}}(x_0, 2^k, x_2 + 2^k) = \ell (x_0, 2^k, x_2 + 2^k) = x_0+x_2, \end{aligned}$$

whenever vector $x' = (x_0, 2^k, x_2 + 2^k)$ satisfies condition (12). Otherwise,

$$\begin{aligned} {\mathcal {G}}(x_0, 2^k, x_2 + 2^k) = s(x_0, 2^k, x_2 + 2^k) = x_0 + x_2 + 2^{k+1}. \end{aligned}$$

The following examples illustrate the above statement: By Lemma 7 we have the equalities

$$\begin{aligned} \begin{array}{rlllll} 13 &{}= {\mathcal {G}}(0, 0, 13) &{}= {\mathcal {G}}(0, 16, 29) &{}= {\mathcal {G}}(0, 32, 45) &{}= {\mathcal {G}}(0, 64, 79) &{}= \cdots \\ 17 &{}= {\mathcal {G}}(1, 0, 16) &{}= {\mathcal {G}}(1, 32, 48) &{}= {\mathcal {G}}(1, 64, 80) &{}= \cdots \\ 19 &{}= {\mathcal {G}}(2, 0, 17) &{}= {\mathcal {G}}(2, 32, 49) &{}= {\mathcal {G}}(2, 64, 81) &{}= \cdots \end{array} \end{aligned}$$

In addition, our computations show the following equalities, in agreement with the above conjecture. For the lower bound equalities we have

$$\begin{aligned} \begin{array}{rlllll} 13 &{}= {\mathcal {G}}(0, 0, 13) &{}= {\mathcal {G}}(0, 2, 15) \\ 17 &{}= {\mathcal {G}}(1, 0, 16) &{}= {\mathcal {G}}(1, 2, 18) &{}= {\mathcal {G}}(1, 4, 20) &{}= {\mathcal {G}}(1, 8, 24) \\ 19 &{}= {\mathcal {G}}(2, 0, 17) &{}= {\mathcal {G}}(2, 4, 21) &{}= {\mathcal {G}}(2, 8, 25), \end{array} \end{aligned}$$

while the upper bound is attained in the following cases ${\mathcal {G}}(0, 1, 14) = 15$, ${\mathcal {G}}(0, 4, 17) = 21$, ${\mathcal {G}}(0, 8, 21) = 29$. ${\mathcal {G}}(1, 1, 17) = 19$, ${\mathcal {G}}(1, 16, 32) = 49$, ${\mathcal {G}}(2, 1, 18) = 21$, ${\mathcal {G}}(2, 2, 19) = 23$, and ${\mathcal {G}}(2, 16, 33) = 51$.

3.3.2 Case 2: $x_1$ is close to a power of 2

Our computations indicate that for a position $x = (x_0, x_1, x_2)$ the upper bound is attained whenever the semi-closed interval $(x_1, x_1 + x_0]$ contains a power of 2. Let us recall that $x_1 \le x_2$ is assumed.

Conjecture 2

If $x_1 < 2^k \le x_0 + x_1$ for some $k \in {\mathbb {Z}}_{+}$, then ${\mathcal {G}}(x) = s(x)$.

Instead, we are able to prove only the following special case.

Proposition 1

If $x_0 \ge 2^{k - 1}$ and $x_1 < 2^k$ for some $k \in {\mathbb {Z}}_{+}$, then $\mathcal{G}(x) =s(x)$.

Proof

We show the claim by induction on s(x). If $s(x) = 0$ (that is, $x=(0,0,0)$) then clearly $\mathcal{G}(x)=s(x)=0$. Assuming that the claim holds for all x with $s(x) \le p-1$, consider a position x with $s(x)=p$. We claim that for each integer v with $x_0 \le v < s(x)$, there exists a move $x \rightarrow x'$ such that $\mathcal{G}(x')=v$. This will imply $\mathcal{G}(x)=s(x)$, since $x_0$ and s(x) are lower and upper bounds for $\mathcal{G}(x)$, respectively.

Let $x'=(x_0',x_1',x_2')$ be a position such that $x'_0 = x_0$, $x_1' = x_1$, and $0 \le x'_2 < x_2$. Then $x \rightarrow x'$ is a move such that $x'$ satisfies $x'_0=x_0 \ge 2^{k-1}$ and $\min \{x_1',x_2'\}\le x_1 < 2^k$. Thus, by induction hypothesis, for any integer v satisfying $x_0 + x_1 \le v < s(x)$ there exists a move $x \rightarrow x'$ such that $\mathcal{G}(x')=v$.

Then, let us consider moves $x \rightarrow x'$ such that $0 \le x_0' < x_0$, $x_1'=x_1$, and $x_2'=0$. By definition, we have $\mathcal{G}(x')=s(x')$, which shows that for any integer v with $x_1 \le v < x_0+x_1$, there exists a move $x \rightarrow x'$ such that $\mathcal{G}(x')=v$. Hence, our claim is proven if $x_0 \ge x_1$, because $\ell (x) \ge x_0$.

If $x_0 < x_1$ then for each integer v with $2^{k-1} \le v < x_1$ consider a position $x'$ such that $x'_0=0$, $x_1'=x_1$, and $x_2'=x_1\oplus v$. It follows from Lemma 8 that $x_1\oplus v < x_1 \le x_2$, which implies that $x'$ is reachable from x. Since $\mathcal{G}(x')=v$, and $\ell (x)\ge x_0\ge 2^{k-1}$, the proof is completed. $\square$

Note that this Proposition is a special case of Conjecture 2 if we choose k to be the smallest integer satisfying $x_0 \ge 2^{k - 1}$ and $x_1 < 2^k$.

Corollary 4

If $x_0 \ge x_1$ then $\mathcal{G}(x)=s(x)$. $\square$

3.3.3 Case 3: $x_2$ is close to a multiple of a power of 2

Let us summarize the previous results and conjectures:

• (a) If $x_0 = 0$ then the lower bound is attained: ${\mathcal {G}}(x) = x_1 \oplus x_2$.

• (b) If $x_1$ is a power of 2 then the condition of Conjecture 1 holds.

• (c) If $x_1 < 2^k \le x_0 + x_1$ for some $k \in {\mathbb {Z}}_{+}$, then the condition of Conjecture 2 holds.

Thus, we assume from now on that

$$\begin{aligned} 2^{k-1}< x_1< x_0 + x_1 < 2^k \text{ for } \text{ some } k \in {\mathbb {Z}}_{+}. \end{aligned}$$

(14)

In this case, our computations show that ${\mathcal {G}}(x) = s(x)$ whenever $x_2$ differs from a multiple of $2^k$ by at most $x_0$.

Conjecture 3

If $x = (x_0, x_1, x_2)$ satisfies (14), $x_1 \le x_2$, and

$$\begin{aligned} j 2^k-x_0 \le x_2 \le j 2^k + x_0 \end{aligned}$$

for some $j,k\in {\mathbb {Z}}_+$, then ${\mathcal {G}}(x) = s(x)$.

Note that assumption (14) is essential. For example, by computations we have ${\mathcal {G}}(1, 4, 20) = \ell (1, 4, 20) = 1 + (4 \oplus 20) = 17<s(1,4,20)$, while the other conditions of Conjecture 3 hold.

3.3.4 Case 4: $x_2$ is large

Although the SG function looks chaotic in general, it seems that the pattern becomes much more regular when $x_2$ is large enough. Unfortunately, we cannot predict how large should it be or prove any observed pattern.

Conjecture 4

We have ${\mathcal {G}}(x) = s(x)$ whenever (14) and the following two conditions hold simultaneously:

• (i) either $x_0 > 1$, or $x_0 = 1$ and $x_1$ is odd, and

• (ii) $x_2$ is sufficiently large.

Let us start with several examples where ${\mathcal {G}}(x)=s(x)$ with $x_0 = 1$ and odd $x_1$, if $x_2> \tau (x_1)$ is large enough:

$$\begin{aligned} \begin{array}{c|c|c} x_1 &{} \tau (x_1) &{} \delta (1,x_1,\tau (x_1)) \\ \hline 5 &{} 14 &{} 1\\ 9 &{} 94 &{} 1\\ 11 &{} 30 &{} 1\\ 13&{} 30 &{} 1\\ 17&{} 446 &{} 1\\ 19&{}158 &{} 1\\ 21&{} 94 &{} 3\\ 23&{}62 &{} 1\\ 25&{} 126 &{} 1\\ 27&{} 62 &{} 3\\ 29&{} 30 &{} 10 \end{array} \end{aligned}$$

where $\delta (x)=s(x)-{\mathcal {G}}(x)$. Note that we skip the values $x_1 = 2^k - 1$, that is, $x_1 = 1, 3, 7, 15, 31$ because those cases are covered by Conjecture 2. When $x_1$ is even and $x_0=1$ the computations show a chaotic behavior.

It seems that for $x_0 > 1$ the upper bound is attained sooner (that is, for smaller $x_2$) and for both odd and even $x_1$. For $x_1 < 2^5 = 32$ and $x_0 = 2$ we obtain:

$$\begin{aligned} \begin{array}{c|c|c} x_1 &{} \tau (x_1) &{} \delta (1,x_1,\tau (x_1)) \\ \hline 5&{} 5 &{}1\\ 9&{} 45 &{}1\\ 10&{} 44 &{}1\\ 11&{} 13&{}1\\ 12&{} 13 &{}24\\ 13&{} 13 &{}2\\ 17&{} 125 &{}1\\ 18&{} 125&{}1\\ 19&{} 61 &{}1\\ 20&{} 93 &{}2\\ 21&{} 61 &{}1\\ 22&{} 61 &{}1\\ 23&{} 29 &{}2\\ 24&{} 92 &{}4\\ 25&{} 61 &{}1\\ 26&{} 61 &{}2\\ 27&{} 29 &{}1\\ 28&{} 29 &{}56\\ 29&{} 29 &{}4\\ \end{array} \end{aligned}$$

For $x_0 = 3$ the upper bound is achieved even faster; for $x_1 < 2^5 = 32$ we have:

$$\begin{aligned} \begin{array}{c|c|c} x_1 &{} \tau (x_1) &{} \delta (1,x_1,\tau (x_1)) \\ \hline 9 &{} 28 &{}1\\ 10 &{} 20 &{}1\\ 11 &{} 12 &{}1\\ 12&{} 12 &{}24\\ 17 &{} 92 &{}1\\ 18 &{} 92 &{}1\\ 19&{} 60 &{}1\\ 20 &{} 60 &{}1\\ 21 &{} 60 &{}1\\ 22 &{} 28 &{}2\\ 23 &{} 28 &{}2\\ 24 &{} 56 &{}47\\ 25 &{} 28 &{}3\\ 26 &{} 28 &{}3\\ 27 &{} 28 &{}3\\ 28 &{} 28 &{}56 \end{array} \end{aligned}$$

In all the above examples we skip the values of $x_1$ such that $x_1 < 2^k \le x_1 + x_0$ for some $k \in {\mathbb {Z}}_{+}$, since in this case the condition of Conjecture 2 holds. We also skip values of $x_1 = 2^k$ because the condition of Conjecture 1 holds in this case.

Finally, let us consider the case when $x_1$ is even and $x_0 = 1$.

Conjecture 5

Given $x_0 = 1$ and an even $x_1$ such that $2^{k-1}< x_1 < 2^k$ for some $k \in {\mathbb {Z}}_{+}$, then $\delta (x_0, x_1, x_2)$ takes only even values and becomes periodic in $x_2$ with period $2^k$, when $x_2$ is large enough.

The examples for $k \le 5$ are presented below. Note that for $x_1 = 2,4,8,16$ the condition in Conjecture 1 is satisfied and hence all remaining cases are presented in the table below. For a threshold integer $\tau (x_1)$ we define

$$\begin{aligned} \pi (x_1)=(\delta (1,x_1,i)\mid i=\tau (x_1)+1,\tau (x_1)+2,\ldots ), \end{aligned}$$

and write $(0,0,0,1,2,1,2)^*=((0)^3,(1,2)^2)^*$ for the infinite sequence $(0,0,0, 1, 2, 1, 2,0,0,0, 1, 2, 1, 2,\ldots )$.

$$\begin{aligned} \begin{array}{c|c|c|c|c} x_1 &{} \tau (x_1) &{} 2^k&{} \pi (x_1) &{}\delta (1,x_1,\tau (x_1)) \\ \hline 6&{}14&{}8&{}(0^3,4,(0,2)^2)^*&{}12\\ 10&{}109&{}16&{}(4,(0^3,4)^2,0,12,(0,4)^2,0)^*&{}2\\ 12&{}109&{}16&{}(2,0^5,6,8,2,(0,2,4,2,0,2,4)^*&{}2\\ 14&{}30&{}16&{}(0^3,4,(0,2)^6)^*&{}28\\ 18&{}446&{}32&{}((0^3,4)^4,(0,2)^8)^*&{}1\\ 20&{}400&{}32&{}((0,2,0,6)^3,0,2,(0^5,6,0,2)^2,0,22)^*&{}3\\ 22&{}94&{}32&{}((0^3,4,(0,2)^2)^2,(0,2)^8)^*&{}4\\ 24&{}456&{}32&{}((0,2)^2,0,16,((0,2)^3,0,10)^2,0^9,16)^*&{}10\\ 26&{}126&{}32&{}((0^3,4)^2,(0,2)^{12})^*&{}1\\ 28&{}104&{}32&{}((0,2,0,6)^5,0,2,0^5,6,0,2,0,14)^*&{}3\\ 30&{}30&{}32&{}(0^3,4,(0,2)^{14})^*&{}60 \end{array} \end{aligned}$$

Interestingly, $\delta (x) = 0$ whenever $x_2$ is odd, except for only one case: $x_1 = 12$, when $\delta (1, 12, x_2)$ takes non-zero values 8, 4, 4 for $x_2 = 5, 9, 13 \mod 16$, respectively.

Let us also recall that for $x_1 = 2^k$, Conjecture 1 of Sect. 3.3.1 gives similar periodical sequences, which take only two values: $\delta = 0$ and $\delta = 2x_1$.

Before concluding the section, we remark that we cannot separately prove the conjectures stated above. Indeed, to show that ${\mathcal {G}}(x) = v$, we have to verify that for any nonnegative integer $v' < v$, there exists a move $x \rightarrow x'$ such that ${\mathcal {G}}(x') = v'$. Thus to prove one of the conjectures by induction, we may need all other conjectures. It is natural to prove them simultaneously. However, at this moment we cannot, since for example, we have no bounds for $\tau$ in Conjectures 4 and 5.

Let us add finally that in the recent publication (Beideman et al. 2018) some of the above questions were studied. The authors considered auxiliary Nim, which is the selective compound of a single pile Nim and the classical Nim with n piles. For $n=2$ this coincides with the game we analyzed above. The authors obtained some interesting results, and in particular they proved our Conjecture 2 and some special cases of Conjecture 3,4, and 5.

Appendix: Slow Nim

In this section, we consider a variant of Nim, so called slow Nim. A move in a Hypergraph Nim game Nim$_\mathcal{H}$ is called slow if each pile is reduced by at most one token. Let us restrict both players by their slow moves, then the obtained game is called slow hypergraph Nim. We study SG functions and losing positions of slow Moore Nim and slow exact Nim, where they respectively correspond to hypergraphs $\mathcal{H}= \{H \subseteq I \mid 1 \le |H| \le k\}$ and $\mathcal{H}=\{H \subseteq I \mid |H|=k\}$ for some $k \le n$. We provide closed formulas for the SG functions of both games when $n = k = 2$ and $n = k+1 = 3$, where we remak that the SG function for slow exact Nim when $n = k = 2$ is trivial. We also characterize losing positions for slow Moore Nim if either $n \le k+2$ or $n = k+3 \le 6$ holds.

Here we only present the results, where all the proofs can be found in the preprint by Gurvich and Ho (2019).

Given a position $x = (x_1, \ldots , x_n) \in {\mathbb {Z}}_+^I$, we will always assume that its coordinates are nondecreasing $x_1 \le \cdots \le x_n$. The parity vector p(x) is defined as the vector $p(x) = (p(x_1), \ldots , p(x_n)) \in \{0,1\}^I$ such that $p(x_i) = 0$ if $x_i$ is even, and $p(x_i) = 1$ if $x_i$ is odd. It appears that the status of a position x in the slow Moore Nim in the cases below is defined by p(x) .

Proposition 2

The SG function ${\mathcal {G}}$ for slow Moore Nim  for $n = k = 2$ and $n = 3, k = 2$ are uniquely defined by p(x) as follows:

• (i) For $n = k = 2$,

  $$\begin{aligned} {\mathcal {G}}(x) = {\left\{ \begin{array}{ll} 0, \quad \text { if } p(x) = (0,0) \\ 1, \quad \text { if } p(x) = (0,1) \\ 2, \quad \text { if } p(x) = (1,1) \\ 3, \quad \text { if } p(x) = (1,0). \end{array}\right. } \end{aligned}$$

• (ii) For $n = 3$ and $k = 2$,

  $$\begin{aligned} {\mathcal {G}}(x) = {\left\{ \begin{array}{ll} 0 \quad \text { if } p(x) \in \{(0,0,0), (1,1,1)\} \\ 1 \quad \text { if } p(x) \in \{(0,0,1), (1,1,0)\} \\ 2 \quad \text { if } p(x) \in \{(0,1,1), (1,0,0)\}\\ 3 \quad \text { if } p(x) \in \{(0,1,0), (1,0,1)\}. \end{array}\right. } \end{aligned}$$

We next consider losing positions of slow Moore Nim.

Proposition 3

Consider a slow Moore Nim when $n \le k+2$ or $n = k+3 \le 6$. Then for a position $x \in {\mathbb {Z}}_+^I$, we have the following five cases.

• (1) for $n=k$, x is losing if and only if $p(x) = (0, 0, \ldots , 0)$.

• (2) for $n=k+1$, x is losing if and only if $p(x) \in \{(0, 0, \ldots , 0), (1, 1, \ldots , 1)\}$.

• (3) for $n=k+2$, x is losing if and only if $p(x) \in \{(0, 0, \ldots , 0), (0,1, \ldots , 1)$.

• (4) for $n=5$ and $k=2$, x is losing if and only if

  $$\begin{aligned} p(x) \in \{(0,0,0,0,0), (0,0,1,1,1), (1,1,0,0,1), (1,1,1,1,0)\}; \end{aligned}$$

• (5) for $n=6$ and $k=3$, x is losing if and only if

  $$\begin{aligned} p(x) \in \{(0,0,0,0,0,0), (0,0,1,1,1,1), (1,1,0,0,1,1), (1,1,1,1,0,0)\}. \end{aligned}$$

We note that Moore Nim games satisfy that $1\le k \le n$, and the case in which $n=4$ and $k=1$ is a standard 4-pile Nim.

We finally consider slow exact Nim. Note that this game is trivial when $k=1$ or $k=n$. We show that the game is tractable if $n=3$ and $k=2$. Again the parity vector plays an important role, although it does not define the SG function uniquely.

Define six sets of positions $x \in {\mathbb {Z}}_+^3$:

$$\begin{aligned} A&= \{(2a, 2b-1, 2(b+i)) \mid 0 \le a< b, 0 \le i< a, (a+i) \bmod {2} = 1\} \\ B&= \{(2a,2b,2(b+i)+1) \mid 0 \le a \le b, 0 \le i< a, (a+i) \bmod {2} = 1\} \\ C_0&= \{(2a-1, 2b-1, 2(b+i)-1) \mid 0 \le a \le b, 0 \le i< a, (a+i) \bmod {2} = 0\} \\ C_1&= \{(2a-1, 2b-1, 2(b+i)-1) \mid 0 \le a \le b, 0 \le i< a, (a+i) \bmod {2} = 1\} \\ D_0&= \{(2a-1, 2b, 2(b+i)) \mid 0 \le a< b, 0 \le i< a, (a+i) \bmod {2} = 1\} \\ D_1&= \{(2a-1, 2b, 2(b+i)) \mid 0 \le a< b, 0 \le i < a, (a+i) \bmod {2} = 0\}, \end{aligned}$$

and let $C = C_1 \cup C_2$, $D = D_1 \cup D_2$.

Proposition 4

For a slow exact Nim with $n=3$ and $k=2$, the SG function ${\mathcal {G}}$ can be represented by

$$\begin{aligned} {\mathcal {G}}(x) = {\left\{ \begin{array}{ll} 0 \quad \text { if } x \in (\{(2a,2b,c) \mid 2a \le 2b \le c\} {\setminus } B) \cup A \cup C_0 \cup D_0 \\ 1 \quad \text { if } x\in (\{(2a,2b+1,c) \mid 2a \le 2b+1 \le c\} {\setminus } A) \cup B \cup C_1 \cup D_1 \\ 2 \quad \text { if } x \in \{(2a+1,2b+1,c) \mid 2a+1 \le 2b+1 \le c\} {\setminus } C \\ 3 \quad \text { if } x \in \{(2a+1,2b,c) \mid 2a+1 \le 2b \le c\} {\setminus } D. \end{array}\right. } \end{aligned}$$