# On Remoteness Functions of Exact Slow $k$-NIM with $k+1$ Piles

Vladimir Gurvich  National Research University Higher School of Economics
(HSE), Moscow, Russia; e-mail<EMAIL_ADDRESS>and<EMAIL_ADDRESS>Denis Martynov  National Research University Higher School of Economics (HSE),
Moscow, Russia; e-mail<EMAIL_ADDRESS>Vladislav Maximchuk  National
Research University Higher School of Economics (HSE), Moscow, Russia; e-mail:
<EMAIL_ADDRESS>Michael Vyalyi National Research University
Higher School of Economics, Moscow, Russia; Institute of Physics and
Technology, Dolgorpudnyi, Russia; Federal Research Center “Computer Science
and Control” of the Russian Academy of Sciences, Moscow, Russia; e-mail:
<EMAIL_ADDRESS>
Abstract Given integer $n$ and $k$ such that $0<k\leq n$ and $n$ piles of
stones, two player alternate turns. By one move it is allowed to choose any
$k$ piles and remove exactly one stone from each. The player who has to move
but cannot is the loser. Cases $k=1$ and $k=n$ are trivial. For $k=2$ the game
was solved for $n\leq 6$. For $n\leq 4$ the Sprague-Grundy function was
efficiently computed (for both the normal and misère versions). For $n=5,6$ a
polynomial algorithm computing P-positions was obtained. Here we consider the
case $2\leq k=n-1$ and compute Smith’s remoteness function, whose even values
define the P-positions. In fact, an optimal move is always defined by the
following simple rule:

  * •

if all piles are odd, keep a largest one and reduce all other;

  * •

if there exist even piles, keep a smallest one of them and reduce all other.

Such strategy is optimal for both players, moreover, it allows to win as fast
as possible from an N-position and to resist as long as possible from a
P-position.

Keywords: Exact Slow NIM, Smith’s Remoteness Function, Sprague-Grundy Function

AMS subjects: 91A05, 91A46, 91A68

##  1 Introduction

We assume that the reader is familiar with basic concepts of impartial game
theory; see e.g., [1, 4] for an introduction.

###  1.1 Exact Slow NIM

Game Exact Slow NIM was introduced in [23] as follows: Given two integers $n$
and $k$ such that $0<k\leq n$ and $n$ piles containing $x_{1},\dots,x_{n}$
stones. By one move it is allowed to reduce any $k$ piles by exactly one stone
each. Two players alternate turns. One who has to move but cannot is the
loser. In [23], this game was denoted NIM${}^{1}_{=}(n,k)$. Here we will
simplify this notation to NIM$(n,k)$. We start with three simple properties of
this game.

Obviously, value $x_{1}+\dots+x_{n}\;\mod k$ is an invariant of game
NIM$(n,k)$. Hence, NIM$(n,k)$ is split into $k$ independent subgames, between
which there are no moves.

A position $x=(x_{1},\dots,x_{n})$ will be called even or odd if all its
coordinates are even or odd, respectively.

Every even position of game NIM$(n,k)$ is a P-position, because each move of
the first player can be repeated by the opponent. Respectively, every position
$x$ with exactly $k$ odd coordinates is an N-position, because there is a move
from $x$ to a P-position.

######  Remark 1.

Note that both above claims can be obviously extended from game NIM$(n,k)$ to
the slow NIM to arbitrary hypergraph [23]. Given a hypergraph
$\mathcal{H}\subseteq 2^{[n]}\setminus\\{\emptyset\\}$ on the ground set
$[n]=\\{1,\dots,n\\}$, and a nonnegative vector $x=(x_{i}\mid i\in[n])$, the
hypergraph slow game NIMH is defined as follows: By one move, a player can
choose any hyperedge $H\in\mathcal{H}$ such that $x_{i}>0$ for every $i\in H$
and reduce by 1 each $x_{i}$ for $i\in H$. Then, game NIM$(n,k)$ corresponds
to the hypergraph slow NIMH with $\mathcal{H}=\\{H\mid|H|=k\\}$. In any
hypergraph slow NIMH, every even $x$ is a P-position and, hence, $x$ is an
N-position when $x_{i}$ is odd if and only if $i\in H$ for some hyperedge
$H\in\mathcal{H}$.

Game NIM$(n,k)$ is trivial if $k=1$ or $k=n$. In the first case it ends after
$x_{1}+\dots+x_{n}$ moves and in the second one—after
$\min(x_{1},\dots,x_{n})$ moves. In both cases nothing depends on players’
skills. All other cases are more complicated.

The game was solved for $k=2$ and $n\leq 6$. In [24], an explicit formula for
the Sprague-Grundy (SG) function was found for $n\leq 4$ (for both, the normal
and misère versions of the game). This formula allows us to compute the SG
function in linear time. Then, in [10] the P-positions were found for $n\leq
6$. For the subgame with even $x_{1}+\dots+x_{n}$ a simple formula for the
P-positions was obtained. It allows for a given position, in linear time, to
verify if it is a P-position and, if not, to find a move from it to a
P-position. The subgame with odd $x_{1}+\dots+x_{n}$ is more difficult. Still,
a more sophisticated formula for the P-positions was found and it gives a
linear time algorithm for recognizing P-positions.

###  1.2 Case $n=k+1$

In this paper we solve the game in case $n=k+1$. In every position an optimal
move is always defined by the following simple rule:

  * if all piles are odd, keep a largest one and reduce all other;

  * if there exist even piles, keep a smallest one of them and reduce all other.

We will call this strategy the M-rule and the corresponding moves by the
M-moves. Obviously, in every position there exists a unique M-move, up to re-
numeration of piles. We will show that M-rule solves the game, moreover, it
allows to win as fast as possible in an N-position and to resist as long as
possible in a P-position.

Given a position $x=(x_{1},\ldots,x_{n})$, assume that both players follow the
M-rule and denote by $\mathcal{M}(x)$ the number of moves from $x$ to a
terminal position. We will prove that $\mathcal{M}=\mathcal{R}$, where
$\mathcal{R}$ is the so-called remoteness function considered in the next
subsection.

Let us note that in some positions the M-move may be a unique winning move.
For example, in positions (1,1,2) and (1,1,3) of NIM(3,2) the M-move reduces
1,1 to 0,0, and wins immediately, while moves to (0,1,1) and (0,1,2) are
losing.

Let us note that there exists no M-move to an odd position. Yet, the latter
may be a P- or N-position. For example, in NIM(3,2), position (1,1,1) is an
N-position, while (3,3,3) is a P-position, $\mathcal{M}(3,3,3)=4$. The
corresponding sequence of M-moves is:
$(3,3,3)\to(2,2,3)\to(1,2,2)\to(0,1,2)\to(0,0,1).$

###  1.3 Smith’s Remoteness Function

In 1966 Smith [34] introduced a remoteness function $\mathcal{R}$ for
impartial games by the following algorithm.

Consider an impartial game given by a finite acyclic directed graph (digraph)
$G$. Set $\mathcal{R}=0$ for all terminal positions of $G$ and
$\mathcal{R}(x)=1$ if and only if there is a move from $x$ to a terminal
position. Delete all labeled positions from $G$ and repeat the above procedure
increasing $\mathcal{R}$ by 2, that is, assign 2 and 3 instead of 0 and 1;
etc.

This algorithm was considered as early as in 1901 by Bouton [3], but only for
a special graphs corresponding to the game of NIM. In 1944 this algorithm was
extended to arbitrary digraphs by von Neumann and Morgenstern [31]. In graph
theory, the set of positions with even $\mathcal{R}$ they called the kernel of
a digraph; in theory of impartial games, this set is referred to as the set of
P-positions.

Function $\mathcal{R}$ has also the following, stronger, properties: Position
$x$ is a P-position if and only if $\mathcal{R}(x)$ is even. In this case the
player making a move from $x$ cannot win, yet, can resist at least
$\mathcal{R}(x)$ moves, but not longer. Position $x$ is an N-position if and
only if $\mathcal{R}(x)$ is odd. In this case the player making a move from
$x$ wins in at most $\mathcal{R}(x)$ moves, but not faster. In both cases the
player making a move from $x$ should reduce $\mathcal{R}$ by one, which is
always possible unless position $x$ is terminal, in which case
$\mathcal{R}(x)=0$.

###  1.4 Sprague-Grundy and Smith’s Theories

Given $n$ impartial games $\Gamma_{1},\dots,\Gamma_{n}$, by one move a player
chooses one of them and makes a move in it. The player who has to move but
cannot is the looser. The obtained game
$\Gamma=\Gamma_{1}\oplus\dots\oplus\Gamma_{n}$ is called the disjunctive
compound. For example, NIM with $n$ piles is the disjunctive compound of $n$
one-pile NIMs. The SG function $\mathcal{G}$ of $\Gamma$ is uniquely
determined by the SG functions of $n$ compound games by formula
$\mathcal{G}(\Gamma)=\mathcal{G}(\Gamma_{1})\oplus\dots\oplus\mathcal{G}(\Gamma_{n})$
where $\oplus$ is the so-called NIM-sum. These results were obtained by Bouton
[3] for the special case of NIM and then extended to arbitrary impartial games
by Sprague [36] and Grundy [19].

Now suppose that by one move a player makes a move in each of the $n$ compound
games, rather than in one of them. Again, the player who has to move but
cannot is the looser. The obtained game
$\Gamma=\Gamma_{1}\wedge\dots\wedge\Gamma_{n}$ is called the conjunctive
compound. Remoteness function $\mathcal{R}$ of $\Gamma$ is uniquely determined
by the remoteness functions of $n$ compound games by formula
$\mathcal{R}(\Gamma)=\min(\mathcal{R}(\Gamma_{1}),\dots,\mathcal{R}(\Gamma_{n}))$.
This result was obtained in 1966 by Smith [34].

###  1.5 On $m$-critical positions of game NIM$(n,n-1)$

The relation $x\succeq y$ is defined standardly as follows. Order, monotone
increasingly, the coordinates of $n$-vectors $x$ and $y$ and denote the
obtained $n$-vectors by $x^{*}$ and $y^{*}$. We write $x\succeq y$ if
$x^{*}_{i}\geq y^{*}_{i}$ for all $i\in\\{1,\dots,n\\}$ and $x\succ y$ if, in
addition, $x^{*}\neq y^{*}$, or in other words, if at least one of these $n$
inequalities is strict.

In the set of positions $x$ with fixed value $\mathcal{M}(x)$ we distinguish
minimal with respect to the relation $\succeq$. Given a nonnegative integer
$m$, a position $x=(x_{1},\dots x_{n})$ of game NIM$(n,k)$ with $n=k+1$ is
called $m$-critical if $\mathcal{M}(x)=m$ and $x\succ y$ fails for any
position $y$ with $\mathcal{M}(y)=m$.

By this definition, for any position $y$ there exists a unique $m=m(y)$ such
that $y\succeq x$ holds for some $m$-critical $x$ and $y\succeq x$ fails for
any $(m+1)$-critical $x$.

We will characterize $m$-critical positions of game NIM$(k+1,k)$ as follows.

######  Theorem 1.

Position $x=(x_{1},\dots,x_{n})$ of game NIM$(n,k)$ with $n=k+1$ is
$m$-critical if and only if one of the following two cases holds:

(A) $\;\;x_{1}+\dots+x_{n}=km$;

$\max(x_{1},\dots,x_{n})\leq m$;

if $m$ is even then $x$ is even (that is, all $n$ coordinates of $x$ are
even);

if $m$ is odd then exactly one of $n$ coordinates of $x$ is even.

(B) $\;\;x_{1}+\dots+x_{n}=km+k-1$;

$\max(x_{1},\dots,x_{n})<m$;

$m$ is even, $x$ is odd.

The proof will be given in Section 2.

Note that case (B) provides a large family of odd P-positions. Note also that
there are odd P-positions beyond this family too. For example,
$\mathcal{M}(3,5,5)=6$ in NIM$(3,2)$. The corresponding sequence of M-moves
is: $(3,5,5)\to(2,4,5)\to(2,3,4)\to(2,2,3)\to(1,2,2)\to(0,1,2)\to(0,0,1).$

Recall that, by definition, an M-move cannot lead to an odd position.

The following statement easily result from the above theorem.

######  Corollary 1.

(i) Let $x$ be an $m$-critical position with an even $m$. Then, $x$ is either
odd (Case (B)) or even (Case (A)). In the latter case, at least one of even
coordinates of $x$ is strictly less than $m$. A move from $x$ leads to an odd
$(m-1)$-critical position provided this move reduces all (maximal) coordinates
of $x$ that are equal to $m$. In particular, an M-move has such property.

(ii) For an $m$-critical position $x$ with an odd $m$ there exists exactly one
move leading to an even $(m-1)$-critical position. This move keeps the
(unique) even coordinate and reduces all other; furthermore, this move is a
unique M-move.

###### Proof.

(i) It is enough to note that all $n=k+1$ coordinates cannot be equal to $m$,
because in this case their sum would be $(k+1)m$ rather than $km$, as required
by Theorem 1. All other statements are immediate from the definitions and
Theorem 1.

(ii) If the largest coordinate $x_{i}$ of $x$ is even, then $x_{i}$ is unique
and $x_{i}<m$, since $m$ is odd. Hence, by Theorem 1, the M-move is unique and
leads to an $(m-1)$-critical position. All other statements are immediate from
the definitions and Theorem 1. ∎

Due to Theorem 2 below, a suitable generalization of $m$-critical positions on
arbitrary game uses the remoteness function $\mathcal{R}(x)$ instead of
$\mathcal{M}(x)$. Characterizing $m$-critical positions of game NIM$(n,k)$
remains an open problem.

######  Conjecture 1.

For any integer $k,n$ and $m$ such that $0<k<n$ and $0\leq m$, inequalities

$km\leq(x_{1}+\dots+x_{n})<k(m+1)\;$ and $\;\max(x_{1},\dots,x_{n})\leq m$

hold for any $m$-critical position $x=(x_{1},\dots,x_{n})$ of game NIM$(n,k)$.

It seems difficult to characterize the $m$-critical positions for arbitrary
$k,n$ and $m$. Consider, for example, $k=3,n=5$ and $m=8$. Computations show
that $(1,3,7,7,7),(1,5,5,7,7),(3,3,5,7,7)$, and $(5,5,5,5,5)$ are $m$-critical
positions of game NIM$(5,3)$, while $(3,5,5,5,7)$ is not; instead
$(3,5,5,6,7)$ is.

###  1.6 Main Results

Our main results are the following two properties of game NIM$(n,n-1)$.

######  Theorem 2.

Equalities $m(x)=\mathcal{M}(x)=\mathcal{R}(x)$ hold for any position $x$.

######  Theorem 3.

Function $\mathcal{R}$ can be computed in polynomial time, even if $n$ is a
part of the input and integers are presented in binary.

Hence, P-positions can be recognized in polynomial time.

###  1.7 On P-positions of game NIM$(n,n-1)$

Recall that P-positions of an impartial game can be characterized in two ways,
in other words, the following three statements are equivalent: $x$ is a
P-position, $\mathcal{G}(x)=0$, and $\mathcal{R}(x)$ is even. Hence, $x$ is a
P-position of NIM$(n,n-1)$ if and only if the number
$m(x)=\mathcal{M}(x)=\mathcal{R}(x)$ is even. Using the above theorems, we
will obtain a polynomial algorithm verifying if $x$ is a P-position and if not
computing a move from $x$ to a P-position.

Interestingly, we do not need this algorithm to play NIM$(n,n-1)$. It is much
simpler just to follow the M-rule (see subsection 1.1)—a peculiar situation in
impartial game theory, which somewhat downgrade the role of P-positions.

For NIM$(4,3)$ some pretty complicated formulas for P-positions were confirmed
by computations; see Appendix. Yet, we were not able to prove these formulas.
Furthermore, they differ in three cases: $x_{1}+x_{2}+x_{3}+x_{4}\equiv 0,1$,
or $2\;(\mod 3)$. Game NIM$(k+1,k)$ is split into $k$ disjoint subgames, which
makes the general case analysis even more difficult. Interestingly, the
$m$-critical positions, unlike the P-positions, are defined by the same
formulas for all $k$ subgames.

###  1.8 Related works

The ancient game of NIM was solved in 1901 by Bouton [3].

In 1907 Wythoff [38] introduced and solved modified NIM with two piles of
stones, where by one move a player can either reduce one pile, or both, but
then by the same number of stones. Wythoff found the P-positions. The game and
its generalizations were studied in many works; see, for example, [2, 13, 14,
16–18, 22, 37, 39].

The SG function of this game is still unknown despite many efforts; see, for
example, [2, 12, 32]. More precisely, it is unknown whether SG value
$\mathcal{G}(x)$ can be computed in polynomial time for a given position $x$.
In contrast, the remoteness function $\mathcal{R}(x)$ can be computed in
polynomial time for the Wythoff game and several its generalizations [8].

In 1910 Moore introduced and solved $k$-NIM. By one move a player can reduce
at most $k$ piles, and at least 1. Moore found the P-positions. The SG-
function is known only in the case $n=k+1$; see Jenkins and Mayberry [27].
Recently, their result was considerably strengthened and extended from
hypergraph $k$-NIM with $n=k+1$ piles to the so-called hypergraph NIM on
arbitrary JM hypergraphs; see [5, 6, 7, 9] for details.

For Moore’s game, there is a simple formula for $\mathcal{R}(x)$ when $x$ is a
P-position; in contrast, $\mathcal{R}(x)$ is NP-hard to compute when $x$ is an
N-position; see [8].

Both SG and remoteness functions can be computed in polynomial time for the
game Euclid [11]; see also [18, 21, 28, 29]. A very simple and elegant formula
for the SG function was given in 2006 by Nivasch [33]. A polynomial algorithm
computing the remoteness function was recently suggested in [8].

##  2 Proofs of Theorems 1 and 2

Here we always assume that coordinates in a position $x$ are ordered in the
non-decreasing order and after a move coordinates are re-ordered.

In the case $k=1$, the theorems trivially hold. We assume in this section that
$k>1$.

###  2.1 Function $\mathcal{B}(x)$

We introduce an auxiliary function $\mathcal{B}(x)$ using conditions (A) from
Theorem 1. Let $|x|=\sum_{i=1}^{k+1}x_{i}$ be the $\ell_{1}$-norm of $x$. A
position $z=(z_{1},\dots,z_{k+1})$ is called _basic_ , if

$\displaystyle|z|=kb(z),$ (1) $\displaystyle z_{i}\leq b(z),$ (2) for even
$b(z)$ all $z_{i}$ are even, and for odd $b(z)$ exactly one $z_{i}$ is even.
(3)

Then

$\mathcal{B}(x)=\max(b(z):x\succeq z,\ z\ \text{is basic}).$ (4)

It is clear that $\mathcal{B}(z)=b(z)$ for every basic position $z$. In
general, for a basic position $z$ such that $b(z)=\mathcal{B}(x)$, we say that
$z$ _supports_ $x$ (or $x$ is supported by $z$). If $\mathcal{B}(x)$ is even,
then $x$ is called $B$-even. Otherwise, it is called $B$-odd.

In general, coordinates in a basic position are not ordered. But it does not
matter due to the following observation.

######  Claim 1.

If $z\preceq x$ for a basic $z$, then there exists a basic position $z^{*}$
such that $z^{*}\preceq x$, and $b(z^{*})=b(z)$, and coordinates of $z^{*}$
are ordered in the non-decreasing order.

###### Proof.

All the conditions (1), (2) and (3) are invariant under permutations of
coordinates. If $x$ is ordered and $z_{i}>z_{j}$ for $i<j$, then $x_{j}\geq
x_{i}\geq z_{i}$ and $x_{i}\geq z_{i}>z_{j}$. Thus, transposition of $z_{i}$
and $z_{j}$ gives a basic position. Repeating the transpositions, we come to
an ordered basic $z^{*}$ such that $z^{*}\preceq x$. ∎

For ordered basic positions we have a useful inequality.

######  Claim 2.

If $z$ is an ordered basic position, then $z_{1}+z_{2}\geq b(z)$.

###### Proof.

The arithmetic mean of $z_{1}+z_{2}$, $z_{i}$, $i\geq 3$, is exactly $b(z)$.
The claim follows from $z_{i}\leq b(z)$ (the bound condition (2)). ∎

From this claim we immediately get a useful corollary.

######  Corollary 2.

If $z$ is an ordered basic position, then $z_{1}\geq 0$. If $z_{1}=0$ then
$z=\big{(}0,b(z),\dots,b(z)\big{)}$.

A move in NIM$(k+1,k)$ preserves exactly one coordinate. We use this
coordinate to indicate the move. Thus, a move $i$ from a position $x$ leads to
the position $x-d^{(i)}$, where $d^{(i)}_{j}=1-\delta_{ij}$ ($\delta_{ij}$ is
the Kronecker symbol).

Let $x\to x^{\prime}$ be a move in NIM$(k+1,k)$. To prove main results, we
relate $\mathcal{B}(x)$ and $\mathcal{B}(x^{\prime})$ in claims below.

######  Claim 3.

If $\mathcal{B}(x)=0$ then $x$ is a terminal position in NIM$(k+1,k)$.

###### Proof.

If $x_{2}>0$ then $z=d^{(1)}=(0,1,\dots,1)\preceq x$, $b(z)=1$, the parity
condition (3) and the bound condition (2) hold. Thus $z$ is basic and
$\mathcal{B}(x)\geq 1$.

If $x_{1}=x_{2}=0$ then $x$ is terminal. ∎

######  Claim 4.

If $x\to x^{\prime}$ is a move in NIM$(k+1,k)$ then
$\mathcal{B}(x^{\prime})\leq\mathcal{B}(x)$.

###### Proof.

Let $z^{\prime}$ be a basic position supporting $x^{\prime}$. Then
$z^{\prime}\preceq x^{\prime}\preceq x$ and
$\mathcal{B}(x)\geq\mathcal{B}(x^{\prime})$. ∎

######  Claim 5.

If $x\to x^{\prime}$ is a move in NIM$(k+1,k)$ from a $B$-odd position $x$,
then $\mathcal{B}(x^{\prime})\geq\mathcal{B}(x)-2$.

###### Proof.

Let $z$ be an ordered basic position that supports $x$ and $z_{p}$ is even
(other coordinates in $z$ are odd). If $b(z)\leq 2$ then the claim trivially
holds. For the rest of the proof assume that $b(z)\geq 3$. It implies
$z_{2}\geq 2$. If $p=2$, it follows from Claim 3. If $p\neq 2$, it follows
from Claim 2: $z_{1}+z_{2}\geq b(z)\geq 3$ and $z_{1}\leq z_{2}$ imply that
$z_{2}\geq 2$.

Define $z^{\prime}$ as follows.

If $p>1$ then $z^{\prime}_{1}=z_{1}-1$, $z^{\prime}_{p}=z_{p}-1$,
$z^{\prime}_{i}=z_{i}-2$ for $i\notin\\{1,p\\}$.

If $p=1$ and $z_{1}>0$ then $z^{\prime}_{1}=z_{1}-1$,
$z^{\prime}_{2}=z_{2}-1$, $z^{\prime}_{i}=z_{i}-2$ for $i\geq 3$.

In both cases, $b(z^{\prime})=b(z)-2$, the parity condition holds for
$z^{\prime}$, as well as the bound condition. Thus, $z^{\prime}$ is basic.

If $p=1$ and $z_{1}=0$ then $z=\big{(}0,b(z),\dots,b(z)\big{)}$ due to
Corollary 2. In this case $z^{\prime}_{1}=0$, $z^{\prime}_{i}=z_{i}-2$ for
$i\geq 2$. It is clear that $z^{\prime}$ is basic and $b(z^{\prime})=b(z)-2$.

In all three cases $0\preceq z^{\prime}\preceq x^{\prime}$. Thus
$\mathcal{B}(x^{\prime})\geq b(z^{\prime})=b(z)-2=\mathcal{B}(x)-2$. ∎

######  Claim 6.

If $x\to x^{\prime}$ is a move in NIM$(k+1,k)$ to a $B$-even position
$x^{\prime}$, then $\mathcal{B}(x^{\prime})<\mathcal{B}(x)$.

###### Proof.

If $x-x^{\prime}=d^{(i)}$ and $z^{\prime}$ supports $x^{\prime}$ then
$z=z^{\prime}+d^{(i)}\preceq x$, and $b(z)=b(z^{\prime})+1$, and $z_{i}\leq
b(z)$, and the parity condition (3) holds for $z$: since all coordinates are
even in $z^{\prime}$, exactly one coordinate is even in $z$. Thus
$\mathcal{B}(x)\geq\mathcal{B}(z)=\mathcal{B}(z^{\prime})+1=\mathcal{B}(x^{\prime})+1$.
∎

######  Lemma 1.

There are no moves from $B$-even positions to $B$-even positions in
NIM$(k+1,k)$.

###### Proof.

Suppose for the sake of contradiction that $x\to x^{\prime}=x-d^{(i)}$ is a
move and $x$, $x^{\prime}$ are $B$-even.

Let $b=\mathcal{B}(x)$ and $z$ be an ordered basic position supporting $x$.
Consider several cases. It follows from Claim 6 that
$\mathcal{B}(x^{\prime})\leq b-2$.

The case $z_{1}=0$. In this case $z=\big{(}0,b(z),\dots,b(z)\big{)}$, due to
Corollary 2, and $x^{\prime}_{j}\geq x_{j}-1\geq z_{j}-1$ for $j>1$, and
$x^{\prime}_{1}\geq 0=z_{1}$. Hence, $z^{\prime}=z-d^{(1)}$ is basic and
$z^{\prime}\preceq x^{\prime}$. It implies that $\mathcal{B}(x^{\prime})\geq
b(z^{\prime})=b(z)-1=\mathcal{B}(x)-1$. We come to a contradiction:
$b-2\geq\mathcal{B}(x^{\prime})\geq b(z^{\prime})=b-1$.

The case $z_{1}\geq 1$ and $z_{i}<b$. Let us prove that $z^{\prime}=z-d^{(i)}$
is a basic position and $z^{\prime}\preceq x^{\prime}$. The latter is clear
from the definitions. Since $b(z^{\prime})=b(z)-1$ is odd, the parity
condition (3) holds. The bound condition (2) is due to the assumption
$z_{i}<b$. Again, we come to a contradiction:
$b-2\geq\mathcal{B}(x^{\prime})\geq b(z^{\prime})=b-1$.

The case $z_{1}\geq 1$, and $z_{i}=b$, and there exists $j<i$ such that
$z_{j}<\min(x_{j},b)$. Now $z^{\prime}=z-d^{(i)}$ violates the bound condition
(2), but the conditions (1), (3) hold by the same reasons as before. That is,
$b(z^{\prime})$ is odd and the only even position in $z^{\prime}$ is $i$. Take
$z^{\prime\prime}=z-d^{(j)}$. In other words,

$z^{\prime\prime}_{r}=\left\\{\begin{aligned}
&z^{\prime}_{r}=z_{r}-1,&&\text{if}\ r\neq i,\ r\neq j,\\\
&z^{\prime}_{j}+1=z_{j},&&\text{if}\ r=j,\\\
&z^{\prime}_{i}-1=z_{i}-1,&&\text{if}\ r=i.\end{aligned}\right.$

The conditions (1), (3) hold for $z^{\prime\prime}$ and
$b(z^{\prime\prime})=b-1$. Since $z_{j}<x_{j}$, we get
$z^{\prime\prime}\preceq x^{\prime}$. From $z_{j}<b$ we get the bound
condition (2). Again, we come to a contradiction:
$b-2\geq\mathcal{B}(x^{\prime})\geq b(z^{\prime\prime})=b-1$.

The remaining case $z_{1}\geq 1$, and $z_{i}=b$, and for all $j$ either
$z_{j}=x_{j}$ or $z_{j}=b$. Since $z$ is ordered, the former holds for $j<t$
and the latter holds for $j\geq t$. W.l.o.g. we assume that $z_{j}<x_{j}$ for
$j\geq t$. Note that $t=k+2$ is possible (in this case $z=x$ and, w.l.o.g.,
$i=k+1$). Take a $B$-even ordered basic position $z^{\prime}$ supporting
$x^{\prime}$ (in particular, $z^{\prime}\preceq x^{\prime}$). It follows from
Claim 6 that $b(z^{\prime})\leq b-2$. All $z^{\prime}_{j}$ are even since
$x^{\prime}$ is $B$-even. Therefore
$z^{\prime}_{j}<x^{\prime}_{j}=x_{j}-1=z_{j}-1$ for $j<t$, since the former is
even and the latter is odd and $z^{\prime}_{j}\leq
b-2<x_{j}-2=x^{\prime}_{j}-1$ for $j\geq t$. Thus
$z^{\prime\prime}=z^{\prime}+d^{(j)}\preceq x^{\prime}$ for all $j$ and
$z^{\prime\prime}$ is a basic position such that
$b(z^{\prime\prime})=b(z^{\prime})+1$. It implies that
$\mathcal{B}(x^{\prime})\geq b(z^{\prime})+1=\mathcal{B}(x^{\prime})+1$, a
contradiction. ∎

Positions satisfying the condition (B) in Theorem 1 are called _exceptional_.
We establish several facts about exceptional positions.

######  Claim 7.

$\mathcal{B}(x)<m(x)$ for an exceptional position $x$.

###### Proof.

Let $z$ be a basic position that supports $x$. Then

$k\mathcal{B}(x)=|z|\leq|x|=km(x)+k-1=k\big{(}m(x)+1\big{)}-1,$

thus $\mathcal{B}(x)\leq m(x)$.

Suppose, for the sake of contradiction, that $\mathcal{B}(x)=m(x)\equiv
0\pmod{2}$. It implies $z_{i}<x_{i}$ for all $i$ (since the former is even and
the latter is odd). Therefore

$k\mathcal{B}(x)=|z|\leq\sum_{i}(x_{i}-1)=km(x)+k-1-k-1=km(x)-2,$

a contradiction. ∎

######  Claim 8.

If $x\succeq z$, and $x\neq z$, and $z$ is exceptional then
$\mathcal{B}(x)>m(z)$.

###### Proof.

Let $x_{i}>z_{i}$. Take $z^{\prime}=z+e^{(i)}$, where
$e^{(i)}_{j}=\delta_{ij}$. Then

$|z^{\prime}|=1+|z|=1+km(z)+k-1=k(m(z)+1),$

$z^{\prime}_{i}$ is even, while $z^{\prime}_{j}$ is odd for all $j\neq i$, and
$z^{\prime}_{j}<m(z)+1$. Thus $z$ is basic and $z^{\prime}\preceq x$. So,
$\mathcal{B}(x)\geq m(z)+1$. ∎

######  Corollary 3.

$\mathcal{B}(x)=m(x^{\prime})+1$ for any move $x\to x^{\prime}$ to an
exceptional position $x^{\prime}$.

###### Proof.

Claim 8 implies $\mathcal{B}(x)\geq m(x^{\prime})+1$. On the other hand,

$|x|=|x^{\prime}|+k=km(x^{\prime})+k-1+k<k\big{(}m(x^{\prime})+2\big{)}.$

Thus, $\mathcal{B}(x)\leq m(x^{\prime})+1$. ∎

######  Claim 9.

For any move $x\to x^{\prime}$ from an exceptional position,
$\mathcal{B}(x)=\mathcal{B}(x^{\prime})=m(x)-1$ is odd.

###### Proof.

From Claim 7 we get $\mathcal{B}(x)<m(x)$. Let $x^{\prime}=x-d^{(i)}$ and
$p=1$, if $i\neq 1$, $p=k+1$, if $i=1$. Define $z^{\prime}$ as follows

$z^{\prime}_{j}=\left\\{\begin{aligned} &x_{i}<m(x),&&\text{if}\ j=i,\\\
&x_{p}-1,&&\text{if}\ j=p,\\\
&x_{j}-2,&&\text{otherwise.}\end{aligned}\right.$

It follows from the definition that $z^{\prime}\preceq x^{\prime}\preceq x$,
and

$|z^{\prime}|=-1-2(k-1)+|x|=km(x)+k-1+1-2k=k\big{(}m(x)-1\big{)},$

and the only even coordinate in $z^{\prime}$ is $p$. Since $m(x)$ is even,
$z^{\prime}$ is basic and $m(x)>\mathcal{B}(x)\geq m(x)-1$,
$\mathcal{B}(x^{\prime})\geq m(x)-1$. Note that

$|x^{\prime}|=\big{(}km(x)+k-1\big{)}-k=km(x)-1,$

thus $m(x)>\mathcal{B}(x^{\prime})$. Therefore,
$\mathcal{B}(x)=\mathcal{B}(x^{\prime})=m(x)-1$. ∎

###  2.2 Relation to $\mathcal{M}(x)$ and $\mathcal{R}(x)$

At first, we prove several facts about changes of $\mathcal{B}(x)$ on M-moves.
We will use the following notation. Let $e(x)$ be the maximal index such that
$x_{e(x)}$ is the smallest even integer among $x_{i}$ if there are even
$x_{i}$. Otherwise, if all $x_{i}$ are odd, then $e(x)=k+1$. The M-move at $x$
is $x\to x^{\prime}=x-d^{(e(x))}$. Note that defined by this rule $x^{\prime}$
is ordered (assuming, as everywhere, that $x$ is ordered).

######  Claim 10.

If $x\to x^{\prime}=x-d^{(e(x))}$ is an M-move in NIM$(k+1,k)$ from a $B$-even
position $x$, then $\mathcal{B}(x^{\prime})=\mathcal{B}(x)-1$.

###### Proof.

$\mathcal{B}(x)>0$ due to Claim 3. By Lemma 1, $x^{\prime}$ is $B$-odd. Thus,
due to Claim 4, it is enough to prove
$\mathcal{B}(x^{\prime})\geq\mathcal{B}(x)-1$.

Let $z$ be an ordered basic position supporting $x$. Take
$z^{\prime}=z-d^{(e(x))}$. It is clear that $z^{\prime}\preceq x^{\prime}$ and
$b(z^{\prime})=b(z)-1$. The parity condition (3) holds for $z^{\prime}$: since
all coordinates are even in $z$, exactly one coordinate is even in
$z^{\prime}$. If the bound condition (2) also holds, we have
$z^{\prime}\preceq x^{\prime}$, $z^{\prime}$ is basic. Thus
$\mathcal{B}(x^{\prime})\geq b(z^{\prime})=b(z)-1=\mathcal{B}(x)-1$.

If the bound condition (2) is violated, then $z_{e(x)}=b(z)$. Choose the
minimal $i$ such that $z_{i}=z_{i+1}=\dots=z_{k+1}=b(z)$. Note that $i>1$,
otherwise $|z|=(k+1)b(z)\neq kb(z)$ and (1) is violated. Since $e(x)\geq i$,
$x_{j}$ is odd for $j<i$. In particular, $x_{i-1}$ is odd and $z_{i-1}$ is
even. Thus $z_{i-1}<x_{i}$. Therefore $z^{\prime\prime}=z-d^{(i-1)}$ satisfies
$z^{\prime\prime}\preceq x^{\prime}$ and all the conditions (1–3).

Since $b(z^{\prime\prime})=b(z)-1$, we get $\mathcal{B}(x^{\prime})\geq
b(z^{\prime\prime})=b(z)-1=\mathcal{B}(z)-1=\mathcal{B}(x)-1$. ∎

######  Claim 11.

An M-move from a basic position $z$ leads to a basic position $z^{\prime}$
such that $\mathcal{B}(z^{\prime})=\mathcal{B}(z)-1$.

###### Proof.

The sum of coordinates decreases by $k$ at a move. Thus (1) holds for
$z^{\prime}$ and $b(z^{\prime})=b(z)-1$.

Let us prove that $z_{e(z)}<b(z)$, it guarantees that (2) holds for
$z^{\prime}$. If $b(z)$ is even, then all coordinates of $z$ are even and the
smallest coordinate is strictly less than $b(z)$ (otherwise,
$|z|=(k+1)b(z)>kb(z)$). If $b(z)$ is odd, then exactly one coordinate is even
and it is less than $b(z)$.

The parity condition is verified in a similar way. If $b(z)$ is even then
there is exactly one even coordinate in $z^{\prime}$. If $b(z)$ is odd then
the M-move $z\to z^{\prime}$ keeps the even coordinate and decreases the rest
of coordinates by 1. So, all coordinates in $z^{\prime}$ are even.

Thus $z^{\prime}$ is basic, and
$\mathcal{B}(z^{\prime})=b(z^{\prime})=b(z)-1=\mathcal{B}(z)-1$. ∎

######  Claim 12.

If $x\to x^{\prime}$ is an M-move in NIM$(k+1,k)$ from a $B$-odd non-
exceptional position $x$. Then $\mathcal{B}(x^{\prime})=\mathcal{B}(x)-1$.

###### Proof.

The equality follows from two inequalities
$\mathcal{B}(x^{\prime})\geq\mathcal{B}(x)-1$ and
$\mathcal{B}(x^{\prime})\leq\mathcal{B}(x)-1$.

To prove $\mathcal{B}(x^{\prime})\geq\mathcal{B}(x)-1$, take an ordered basic
position $z$ that supports $x$ and make an M-move $p=e(z)$ from $z$ to
$z^{\prime}$. Note that $z^{\prime}$ is basic due to Claim 11 and
$z_{p}=z^{\prime}_{p}\leq b(z^{\prime})=b(z)-1$, since $z_{p}$ is even and
$b(z)$ is odd.

If $x_{p}>z_{p}$ then $x^{\prime}_{p}\geq z_{p}$ and $z^{\prime}\preceq
x^{\prime}$. Thus $\mathcal{B}(x^{\prime})\geq
b(z^{\prime})=b(z)-1=\mathcal{B}(x)-1$ and we are done.

If $e(x)=p$ then, again, $z^{\prime}\preceq x^{\prime}$ and we are done.

Assume now that $x_{p}=z_{p}$ (so there are even coordinates in $x$) and
$e(x)\neq p$. Therefore $z_{e(x)}<x_{e(x)}$, since the former is odd (the even
coordinate in $z$ is $p$) and the latter is even.

Note also that $z_{p}=x_{p}>0$. Otherwise, $z_{p}=x_{p}=0$ and, since $z$ is
ordered, $p=1$ and $x_{p}=z_{p}$ is the smallest even coordinate in $x$ which
implies $e(x)=p=1$, a contradiction to the above assumptions.

Now define $z^{\prime\prime}$ by the rules

$z^{\prime\prime}_{j}=\left\\{\begin{aligned} &z^{\prime}_{j},&&\text{if}\
j\neq e(x),\ j\neq p,\\\ &z_{e(x)}+1,&&\text{if}\ j=e(x),\\\
&z_{p}-2,&&\text{if}\ j=p.\end{aligned}\right.$

We are going to prove that $z^{\prime\prime}$ is basic and
$b(z^{\prime\prime})=b(z)-1$. All coordinates in $z^{\prime\prime}$ are even.
Note that $|z^{\prime}|=|z^{\prime\prime}|=kb(z)-k$, since

$(z_{e(x)}-1)+z_{p}=(z_{e(x)}+1)+(z_{p}-2).$

In the case under consideration, the bound condition (2) for
$z^{\prime\prime}$ can be violated in the coordinate $e(x)$ only. Suppose, for
the sake of contradiction, that $z_{e(x)}+1>b(z)-1$. Both $z_{e(x)}$ and
$b(z)$ are odd and $z_{e(x)}\leq b(z)$. Therefore $z_{e(x)}=b(z)$. Recall that
$z$ is ordered and $z_{p}$ is even while $b(z)$ is odd. Thus $z_{p}<b(z)$
which implies $p<e(x)$. Since $x_{p}=z_{p}$ is even, from the definition of
$e(x)$ we get

$b(z)=z_{e(x)}\geq z_{p}=x_{p}=x_{p+1}=\dots=x_{e(x)}\geq z_{e(x)}.$

Thus $z_{e(x)}=z_{p}$, a contradiction with parities of $z_{e(x)}$ and $z_{p}$
(the former is odd and the latter is even).

We conclude that $z^{\prime\prime}$ is basic, $b(z^{\prime\prime})=b(z)-1$,
and $z^{\prime\prime}\leq x^{\prime}$. Therefore $\mathcal{B}(x^{\prime})\geq
b(z^{\prime\prime})=b(z)-1=\mathcal{B}(x)-1$.

To prove that $\mathcal{B}(x^{\prime})\leq\mathcal{B}(x)-1$, take a basic
position $z^{\prime}$ that supports $x^{\prime}$.

If $b(z^{\prime})$ is even, then Claim 6 implies
$\mathcal{B}(x^{\prime})<\mathcal{B}(x)$ and we are done.

Assume now that $b(z^{\prime})$ is odd. Let $p$ be the even coordinate in
$z^{\prime}$.

If $p=e(x)$, $z=z^{\prime}+d^{(e(x))}\preceq x$ and $z$ is basic, since all
coordinates are even, and $|z|=k(b(z^{\prime})+1)$, and the bound condition
(2) holds. Thus $\mathcal{B}(x)\geq
b(z^{\prime})+1=\mathcal{B}(x^{\prime})+1$.

If $e(x)\neq p$ and $z^{\prime}_{e(x)}<x^{\prime}_{e(x)}=x_{e(x)}$, then all
coordinates are even in $z^{\prime\prime}=z^{\prime}+d^{(p)}$, and
$|z^{\prime\prime}|=k(b(z^{\prime})+1)$, and the bound condition (2) holds for
$z^{\prime\prime}$, and $z^{\prime\prime}\leq x$. Thus, we get
$\mathcal{B}(x)\geq b(z^{\prime})+1=\mathcal{B}(x^{\prime})+1$.

In the remaining case $e(x)\neq p$ and
$z^{\prime}_{e(x)}=x^{\prime}_{e(x)}=x_{e(x)}$. It implies that $x_{e(x)}$ is
odd, thus all $x_{i}$ are odd by definition of M-moves and $e(x)=k+1$. We have
proved already that $\mathcal{B}(x^{\prime})\geq\mathcal{B}(x)-1$ and
$\mathcal{B}(x^{\prime})\leq\mathcal{B}(x)$ (Claim 4). So, to complete the
proof, we need to exclude the case $\mathcal{B}(x^{\prime})=\mathcal{B}(x)$
(provided $x$ is non-exceptional).

Suppose, for the sake of contradiction, that
$\mathcal{B}(x^{\prime})=\mathcal{B}(x)$. We are going to construct a basic
position $z^{*}$ such that $z^{*}\preceq x$ and $b(z^{*})=b(z^{\prime})+1$. It
would imply that $\mathcal{B}(x)\geq b(z^{*})>\mathcal{B}(x^{\prime})$, a
contradiction.

Note that $z^{\prime}_{i}\leq x^{\prime}_{i}=x_{i}-1$ for all $1\leq i\leq k$.
It implies that $z^{\prime}_{i}<x^{\prime}_{i}=x_{i}-1$ for $i\neq p$ (the
former is odd, the latter is even).

If $z^{\prime}_{i}\geq x^{\prime}_{i}-1=x_{i}-2$ for all $i\notin\\{p,k+1\\}$,
then $z^{\prime}_{i}=x_{i}-2$, since $x_{i}$ is odd. Thus

$|x|=2(k-1)+(x_{p}-z^{\prime}_{p})+|z^{\prime}|=(x_{p}-z^{\prime}_{p})+(k-2)+k(b(z^{\prime})+1)$

(recall that now $z^{\prime}_{e(x)}=z^{\prime}_{k+1}=x_{k+1}=x_{e(x)}$). If
$z^{\prime}_{p}=x^{\prime}_{p}=x_{p}-1$ then $x_{p}-z^{\prime}_{p}=1$ and we
come to a contradiction with the assumption that $x$ is not exceptional.

So we get a dichotomy: either $x_{p}-z^{\prime}_{p}>1$ or
$x_{p}-z^{\prime}_{p}=1$ and there exists $j\notin\\{p,k+1\\}$ such that
$z^{\prime}_{j}<x_{j}-2$.

In the first case $z^{*}$ is defined as follows

$z^{*}_{i}=\left\\{\begin{aligned} &z^{\prime}_{p}+2,&&\text{if}\ i=p,\\\
&z^{\prime}_{k+1}-1,&&\text{if}\ i=k+1,\\\
&z^{\prime}_{i}+1,&&\text{otherwise.}\end{aligned}\right.$

By definition, $z^{*}\preceq x$, and all $z^{*}_{i}$ are even, and

$|z^{*}|=kb(z^{\prime})+2-1+(k-1)=k(b(z^{\prime})+1),$

and the bound condition holds for $z^{*}$, since
$z^{\prime}_{p}<b(z^{\prime})$ (the former is even, the latter is odd). We
come to a contradiction $\mathcal{B}(x)\geq
b(z^{\prime})+1=\mathcal{B}(x^{\prime})+1=\mathcal{B}(x)+1$.

In the second case $z^{*}$ is defined as follows

$z^{*}_{i}=\left\\{\begin{aligned} &z^{\prime}_{j}+3,&&\text{if}\ i=j,\\\
&z^{\prime}_{k+1}-1,&&\text{if}\ i=k+1,\\\ &z^{\prime}_{p},&&\text{if}\
i=p,\\\ &z^{\prime}_{i}+1,&&\text{otherwise.}\end{aligned}\right.$

Again, $z^{*}\preceq x$, and all $z^{*}_{i}$ are even, and

$|z^{*}|=kb(z^{\prime})+3-1+(k-2)=k(b(z^{\prime})+1),$

and the bound condition holds for $z^{*}$. We come to a contradiction
$\mathcal{B}(x)\geq
b(z^{\prime})+1=\mathcal{B}(x^{\prime})+1=\mathcal{B}(x)+1$. ∎

######  Lemma 2.

$\mathcal{M}(x)=\mathcal{B}(x)$ for non-exceptional $x$ and
$\mathcal{M}(x)=\mathcal{B}(x)+1$ for exceptional $x$.

###### Proof.

Induction on values of $\mathcal{B}(x)$. The base case is Claim 3. Note that
there are no M-moves to exceptional positions, since after an M-move at least
one coordinate is even. Also, there are no moves between exceptional
positions. Thus the induction step for non-exceptional positions follows from
Claims 10 and 12 depending on parity of $\mathcal{B}(x)$, while for
exceptional positions it follows from Claim 9. ∎

######  Corollary 4.

$\mathcal{M}(x)=m(x)$ for all $x$.

###### Proof of Theorem 1..

From Claim 8 we conclude that an exceptional $m$-critical position (the
condition (B)) supports only itself. For the rest of positions, the theorem
follows from Lemma 2, since $m$-critical non-exceptional positions and basic
positions supporting a non-exceptional $x$ are the same. ∎

###### Proof of Theorem 2..

Due to Lemma 2, Theorem 1 and Corollary 4 it remains to prove that
$\mathcal{R}(x)=\mathcal{M}(x)$ for all $x$; in other words,
$\mathcal{R}(x)=\mathcal{B}(x)$ for all non-exceptional $x$ and
$\mathcal{R}(x)=\mathcal{B}(x)+1$ for all exceptional $x$.

We prove it by induction on the sum of coordinates. In the proof we use an
equivalent definition of $\mathcal{R}(x)$. Let $N^{+}(x)$ be the set of
positions such that there exists a move $x\to x^{\prime}$. Then the remoteness
function is defined by the following recurrence

$\mathcal{R}(x)=\left\\{\begin{aligned} &0,&&\text{ if
}\mathcal{R}(N^{+}(x))=\emptyset,\\\ &1+\min\mathcal{R}(N^{+}(x))\cap
2\mathbb{Z}_{\geq 0}\,,&&\text{ if }\mathcal{R}(N^{+}(x))\cap
2\mathbb{Z}_{\geq 0}\neq\emptyset,\\\ &1+\max\mathcal{R}(N^{+}(x))\cap
2\mathbb{Z}_{\geq 0}\,,&&\text{ if
}\emptyset\neq\mathcal{R}(N^{+}(x))\subseteq 1+2\mathbb{Z}_{\geq
0}\,.\end{aligned}\right.$ (5)

The base case $x=0$ trivially holds.

Assume that $\mathcal{R}(x)=\mathcal{M}(x)$ for all $x$ such that
$\sum_{i}x_{i}<q$. Take $y$ such that $\sum_{i}y_{i}=q$.

If $y$ is exceptional, then, due to Claim 9 and Corollary 4, for any move
$y\to y^{\prime}$, we have
$m(y)=\mathcal{M}(y)=\mathcal{B}(y)+1=\mathcal{B}(y^{\prime})+1=\mathcal{R}(y^{\prime})+1$
(the last equality is the induction hypothesis) and $\mathcal{R}(y^{\prime})$
is odd. Therefore $\mathcal{R}(y)=1+\mathcal{R}(y^{\prime})=\mathcal{M}(y)$.

If $y$ is $B$-odd and non-exceptional, then $y\to x=y-d^{(e(y))}$ is an M-move
to $B$-even position. Due to Claim 12, $\mathcal{B}(x)=\mathcal{B}(y)-1$.
Also, $\mathcal{B}(x)\geq\mathcal{B}(y)-2$ for any other move from $y$ due to
Claim 5. From (5) we conclude that
$\mathcal{R}(y)=1+(\mathcal{B}(y)-1)=\mathcal{B}(y)$.

If $y$ is $B$-even, it is non-exceptional and there are no moves to $B$-even
positions from $y$ due to Lemma 1. It follows from Claim 10 that there is a
move to $x$ such that $\mathcal{B}(x)=\mathcal{B}(y)-1$. From (5) we conclude
that $\mathcal{R}(y)=1+(\mathcal{B}(y)-1)=\mathcal{B}(y)$. ∎

##  3 Structural and algorithmic complexity

It follows from Theorem 2 that $x$ is a P position in NIM$(k+1,k)$ iff
$m(x)=\mathcal{R}(x)$ is even.

For a fixed $k$, conditions (A) and (B) in Theorem 1 are easily expressed in
Presburger arithmetic (see, e.g. [26]): they include inequalities and
congruences modulo fixed integers. Therefore the predicate $\mathcal{R}(x)=2y$
is also expressed in Presburger arithmetic. It implies that the set of
P-positions is semilinear [26], i.e. can be expressed as a finite union of
solutions of systems of linear inequalities combined with equations modulo
some integer (fixed for the set). It was conjectured in [25] that the set of
P-positions of any multidimensional subtraction game with nonnegative vectors
of differences is semilinear. The conjecture was supported by several sporadic
examples from [24, 10]. Games NIM$(k+1,k)$ provide an infinite family of
nontrivial subtraction games having this property.

Thus, for a fixed $k$, there exists a very simple linear time algorithm
recognizing P-positions in NIM$(k+1,k)$. Theorem 3 gives more. It claims that
there exists an algorithm recognizing P-positions even if $k$ is a part of the
input.

It follows from Theorems 1 and 2 that, to compute $\mathcal{R}(x)$
efficiently, it is enough to compute $\mathcal{B}(x)$ efficiently for non-
exceptional positions and compute $m(x)$ for exceptional ones. Verifying the
conditions (B) in Theorem 1 can be done in polynomial time as well as
computing $m(x)$ for exceptional positions.

To compute $\mathcal{B}(x)$ efficiently for non-exceptional positions, we use
an enhanced version of Claim 1. We need the reverse lexicographical order on
$(k+1)$-dimensional integer vectors, which is defined as follows:
$x\mathrel{<_{\text{lex}}}y$ if $x_{i}=y_{i}$ for all $i>t$ and $x_{t}<y_{t}$.

For even $b$, let $\ell(x,b)$ be the maximal (w.r.t. the reverse
lexicographical order) basic position $z$ such that $z\preceq x$, $b(z)=b$.

######  Lemma 3.

For all $x$ and for all even $b$, there exists $1<t\leq k+2$ such that
$\ell(x,b)_{i}=b$ for $i\geq t$ and $0\leq x_{i}-\ell(x,b)_{i}\leq 1$ for all
$1<i<t$.

###### Proof.

If $i<j$ then decreasing the coordinate $i$ by 2 and increasing the coordinate
$j$ by 2 transforms a basic position $z$ to a basic position $z^{\prime}$ such
that $z\mathrel{<_{\text{lex}}}z^{\prime}$. This operation is called a
_shift_.

Note also that re-ordering a vector in the non-increasing order gives a vector
that is not smaller than initial one with respect to the reverse
lexicographical order.

Take now an ordered basic position $z$ such that $z\preceq x$, $b(z)=b$ and no
shift can be applied to $z$. It means that $z_{i}\geq\min(x_{i}-1,b-1)$ for
all $1<i\leq k+1$. Since $b$ is even, then either $z_{i}\geq x_{i}-1$ or
$z_{i}=b$. ∎

Note that $\ell(x,b)$ is uniquely determined by $t$: there is exactly one even
integer among $x_{i}-1$, $x_{i}$. It is a key observation for the proof of
Theorem 3.

###### Proof of Theorem 3..

For exceptional positions $m(x)$ can be found in polynomial time. For the rest
of the proof we assume that $x$ is non-exceptional and our goal is to compute
$\mathcal{B}(x)$.

Let $b_{t}(x)$, $1<t\leq k+2$, be the maximal value $b(z)$ for $B$-even basic
positions $z$ such that the conditions of Lemma 3 hold for the specific value
of $t$. If there are no $z$ satisfying the requirements, then $b_{t}=-\infty$.
Let $E(x)=\max_{t}b_{t}(x)$.

Due to Lemma 3, $E(x)\leq\mathcal{B}(x)$ and equality holds exactly for
$B$-even $x$. Let $x\to x^{\prime}=x-d^{(e(x))}$ be an M-move. If $x$ is
$B$-odd then $x^{\prime}$ is $B$-even and
$\mathcal{B}(x)=\mathcal{B}(x^{\prime})+1=E(x^{\prime})+1$. Therefore
$E(x^{\prime})=\mathcal{B}(x^{\prime})=\mathcal{B}(x)-1>E(x)-1$. Similarly,
for a $B$-even position $x$ we have
$E(x)=\mathcal{B}(x)=\mathcal{B}(x^{\prime})+1>E(x^{\prime})+1$.

It gives the rule to compute $\mathcal{B}(x)$ by $E(x)$:

$\mathcal{B}(x)=\left\\{\begin{aligned} &E(x),&&\text{if}\
E(x)>E(x^{\prime})+1,\\\ &E(x^{\prime})+1,&&\text{if}\
E(x)<E(x^{\prime})+1,\end{aligned}\right.$

where $x\to x^{\prime}$ is an M-move.

To complete the proof, we provide an efficient algorithm that computes $E(x)$.
For brevity we use the following notation:

$A_{t}=\sum_{i=2}^{t-1}2\cdot\lfloor x_{i}/2\rfloor.$

To find $b_{t}(x)$, one need to find the maximal $q$ satisfying the
requirements

$\displaystyle 2s+A_{t}+q\cdot 2(k+2-t)=q\cdot 2k,$ (6) $\displaystyle 2s\leq
x_{1},$ $\displaystyle 2q\leq x_{t},$

and set $b_{t}(x)=2q$. (Here $2s$ is the value of $z_{1}$.)

Eq. (6) is equivalent to

$q\cdot 2(t-2)=2s+A_{t}\,.$

Thus, we have two linear inequalities on $q$ and the maximal value of $q$ is

$\min\left(\left\lfloor\frac{2\lfloor
x_{1}/2\rfloor+A_{t}}{2(t-2)}\right\rfloor,\lfloor\frac{x_{t}}{2}\rfloor\right)\,.$

If $t=2$ the first inequality becomes irrelevant.

Combining all the arguments above, we get the polynomial algorithm to compute
$\mathcal{B}(x)$ and $\mathcal{R}(x)$. ∎

## Acknowledgements:

This research was prepared within the framework of the HSE University Basic
Research Program. The fourth author was supported in part by the state
assignment topic no. 0063-2016-0003.

## References

  * [1] M.H. Albert, R.J. Nowakowski, and D. Wolfe, Lessons in play: An introduction to combinatorial game theory, second ed., A. K. Peters Ltd., Wellesley, MA, 2007.
  * [2] U. Blass and A.S. Fraenkel, The Sprague–Grundy function for Wythoff’s game, Theoret. Comput. Sci. 75 (1990) 311–333.
  * [3] C.L. Bouton, Nim, a game with a complete mathematical theory, Ann. of Math., 2-nd Ser. 3 (1901-1902) 35-39.
  * [4] E.R. Berlekamp, J.H. Conway, and R.K. Guy, Winning Ways for Your Mathematical Plays, second ed., vol. 1–4, A.K. Peters, Natick, MA, 2001–2004.
  * [5] E. Boros, V. Gurvich, N. B. Ho, and K. Makino, On the Sprague–Grundy function of extensions of proper NIM; International Journal of Game Theory 50:3 (2021) 635–654; an earlier version: On the Sprague-Grundy Function of Tetris Extensions of Proper Nim, RUTCOR Research Report, RRR-1-2015, Rutgers University, http://arxiv.org/abs/1504.06926.
  * [6] E. Boros, V. Gurvich, N.B. Ho, K. Makino, and P. Mursič, On the Sprague–Grundy function of Exact $k$-Nim, Discrete Appl. Math. 239 (2018) 1–14.
  * [7] E. Boros, V. Gurvich, N. B. Ho, K. Makino, and P. Mursič, Sprague-Grundy function of matroids and related hypergraphs, Theor. Comput. Sci. 799 (2019) 40–58.
  * [8] E. Boros, V. Gurvich, K. Makino, M. Vyalyi, On Remoteness function of Classic Impartial Games, Manuscript, 2023.
  * [9] E. Boros and V. Gurvich, N.B. Ho, K. Makino, and P. Mursič, Sprague-Grundy function of symmetric hypergraphs, J. Combinatorial Theory A 165 (2019) 176–186.
  * [10] N. Chikin, V. Gurvich, K. Knop, M. Paterson, and M. Vyalyi, More about Exact Slow k-Nim, Integers 21 (2021) 1–14 #G4.
  * [11] A.J. Cole, A.J.T. Davie, A game based on the Euclidean algorithm and a winning strategy for it, Math. Gaz. 53 (1969) 354–357.
  * [12] J.H. Conway, On Numbers and Games, Academic Press, London, New York, San Francisco, 1976.
  * [13] H. S. M. Coxeter, The golden section, Phyllotaxis and Wythoff’s game, Scripta Math. 19 (1953) 135–143.
  * [14] E. Duchene, A. S. Fraenkel, V. Gurvich, Nhan N.B. Ho, C. Kimberling, and U. Larsson, Wythoff Visions, in Games of No Chance 5, U. Larsson, ed., MSRI Publ. 70, Cambridge Univ. Press, Berkeley, Ca. (2019) 35–88.
  * [15] A.S.Fraenkel and I. Borosh, A generalization of Wythoff’s game Journal of Combinatorial Theory, Series A 15:2 (1973) 175–191.
  * [16] A.S. Fraenkel, How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly 89 (1982) 353–361.
  * [17] A.S. Fraenkel, Wythoff games, continued fractions, cedar trees and Fibonacci searches, Theoret. Comput. Sci. 29 (1984) 49–73.
  * [18] A.S. Fraenkel, Euclid and Wythoff games, Discrete Math. 304 (2005) 65–68.
  * [19] P.M. Grundy, Mathematics of games, Eureka 2 (1939) 6–8.
  * [20] P.M. Grundy and C.A.B. Smith, Disjunctive games with the last player losing, Proc. Cambridge Philos. Soc. 52 (1956) 523–527.
  * [21] V. Gurvich, On the misère version of game Euclid and miserable games, Discrete Math. 307:9–10 (2007) 1199–1204.
  * [22] V. Gurvich. Further Generalizations of the Wythoff Game and Minimum Excludant, Discrete Applied Math. 160 (2012) 941–947.
  * [23] V. Gurvich and N.B. Ho, Slow k-Nim, RUTCOR Research Report, RRR-03-2015, Rutgers University, online preprint http://arxiv.org/abs/1508.05777
  * [24] V. Gurvich, S. Heubach, N.B. Ho, and N. Chikin, Slow k-Nim, Integers 20 (2020) 1–19 #G3.
  * [25] V. Gurvich and M. Vyalyi, On Computational Hardness of Multidimensional Subtraction Games, Algorithms 2021, 14(3), 71.
  * [26] C. Haase, A survival guide to Presburger arithmetic, ACM SIGLOG News 2018, 5, 67–-82.
  * [27] T.A. Jenkyns and J.P. Mayberry, Int. J. of Game Theory 9:1 (1980) 51–63, The skeletion of an impartial game and the Nim-Function of Moore’s Nimk.
  * [28] T. Lengyel, A Nim-type games and continued fraction, Fibonacci Quart 41 (2003) 310–320.
  * [29] T. Lengyel, On calculating the Sprague–Grundy function for the game Euclid, Proceedings of the 11th International Conference on Fibonacci Numbers and Their Applications, July 5–9, 2004, Technical University of Carolo-Wilhelmina, Braunschweig, Germany (2004), 169–175;
  * [30] E. H. Moore, A generalization of the game called Nim, Annals of Math., Second Series, 11:3 (1910) 93–94.
  * [31] J. von Neumann, O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, NJ, 1944.
  * [32] G. Nivasch, More on the Sprague–Grundy function for Wythoff’s game: on the location of the q-values, Games of No Chance 3, MSRI Publications 56 (2009) 377–410; earlier version: M.Sc. Thesis, Weizmann Institute of Sciences, Rehovot 76100, Israel, 2004.
  * [33] G. Nivasch, The Sprague–Grundy function of the game Euclid, Discrete Mathematics 306:21 (2006) 2798–2800.
  * [34] C. A. B. Smith, Graphs and composite games, J. of Combinatorial theory 1 (1966) 51–81.
  * [35] E.L. Spitznagel Jr., Properties of a game based on Euclid’s algorithm, Math. Mag. 46 (1973) 87–92.
  * [36] R. Sprague, Über mathematische Kampfspiele, Tohoku Math. J. 41 (1936) 438–444.
  * [37] P.D. Straffin, A Nim-type game, solution to problem # 1537, Math. Mag. 71 (1998) 394–395.
  * [38] W.A. Wythoff, A modification of the game of Nim, Niew Archief voor Wiskunde 7 (1907) 199–202.
  * [39] A.M. Yaglom and I.M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol. II, Holden-Day, San Francisco, translated by J. McCawley Jr., revised and edited by B. Gordon, 1967.

## Appendix: P- and N-positions of NIM(4,3)

Here we use notation $[A]$ for the indicator function: $[A]=1$ if $A$ is true
and $[A]=0$ otherwise; and $a\bmod b$ for the residue of $a$ modulo $b$.

Case 0. $x_{1}+x_{2}+x_{3}+x_{4}=0\pmod{3}$

  * •

If $x_{1}$ and $x_{2}$ are both odd then $x$ is an N-position.

  * •

Otherwise, if $(x_{3}-x_{2}-x_{1})\geq 0$ then $x$ is a P-position if and only
if $(x_{1}+x_{2})$ is even.

  * •

Otherwise, if $(x_{3}-x_{2}-x_{1})=-1$ then $x$ is a P-position if and only if
$(x_{1}+x_{2})$ is odd.

  * •

Otherwise, if $(x_{1}+x_{3}-x_{2})$ is even then $x$ is a P-position if and
only if $(x_{1}+x_{2})$ is even.

  * •

Otherwise, $x$ is a P-position if and only if $(x_{2}+p+q)$ is even, where

$\displaystyle p=\left[(x_{1}+x_{3}-x_{2})\equiv 3\pmod{4}\right],$
$\displaystyle q=\left[(x_{1}+x_{2}+x_{3}-2x_{4}-3)=12k,\ k\in\mathbb{Z}_{\geq
0}\right].$

Case 1. $x_{1}+x_{2}+x_{3}+x_{4}=1\pmod{3}$

  * •

If $x_{1}$ and $x_{2}$ are both odd then $x$ is an N-position.

  * •

Otherwise, if $(x_{3}-x_{2}-x_{1})\geq 0$, or $(x_{3}-x_{2}-x_{1})$ is even,
or $(x_{3}-x_{2}-x_{1})=-3$ then $x$ is a P-position if and only if
$(x_{1}+x_{2})$ is even.

  * •

Otherwise, if $(x_{3}-x_{2}-x_{1})=-1$ or $(x_{3}-x_{2}-x_{1})=-5$ then $x$ is
a P-position if and only if $(x_{1}+x_{2})$ is odd.

  * •

Otherwise, $x$ is a P-position if and only if $(x_{2}+p+q)$ is odd, where

$\displaystyle p=\left[(x_{1}+x_{3}-x_{2})\equiv 1\pmod{4}\right],$
$\displaystyle q=\left[(x_{1}+x_{2}+x_{3}-2x_{4}-7)=12k,\ k\in\mathbb{Z}_{\geq
0}\right].$

Case 2. $x_{1}+x_{2}+x_{3}+x_{4}=2\pmod{3}$

  * •

Let $x_{1}$ and $x_{2}$ be both odd:

    * $\circ$

If $(x_{3}-x_{2}-x_{1})\geq 0$ or $(x_{3}-x_{2}-x_{1})\in\\{-1,-3,-4,-7\\}$
then $x$ is an N-position.

    * $\circ$

Otherwise, $x$ is a P-position if and only if $p$ is odd, where

$p=\left[\begin{aligned} &(x_{1}+x_{2}+x_{3}-2x_{4}-c)=12k,\
k\in\mathbb{Z}_{\geq 0},\\\ &c=2+3\big{(}(x_{1}+x_{2})\bmod
4\big{)}\end{aligned}\right].$

  * •

Let $x_{1}$ be odd and $x_{2}$ even.

    * $\circ$

If $(x_{3}-x_{2}-x_{1})\geq 0$ or $(x_{3}-x_{2}-x_{1})\in\\{-2,-3,-6\\}$ then
$x$ is an N-position.

    * $\circ$

Otherwise, if $(x_{3}-x_{2}-x_{1})=-1$ then $x$ is an P-position.

    * $\circ$

Otherwise, $x$ is a P-position if and only if $(p+q)$ is odd, where

$\displaystyle p=\left[(x_{1}+x_{3}-x_{2})\equiv 1\pmod{4}\right],$
$\displaystyle q=\left[\begin{aligned}
&(x_{1}+x_{2}+x_{3}-2x_{4}-c)=12k,&&k\in\mathbb{Z}_{\geq 0},\\\
&c=5,&&\text{if $(x_{1}+x_{2})$ is odd},\\\ &c=(8-3((x_{1}+x_{2})\bmod
4)),&&\text{otherwise.}\end{aligned}\right]$

  * •

Let $x_{1}$ be even.

    * $\circ$

If $(x_{3}-x_{2}-x_{1})\geq 0$ or $(x_{3}-x_{2}-x_{1})\in\\{-2,-3,-6\\}$ then
$x$ is a P-position if and only if $x_{2}$ is even.

    * $\circ$

Otherwise if $(x_{3}-x_{2}-x_{1})=-1$ then $x$ is a P-position if and only if
$x_{2}$ is odd.

    * $\circ$

Otherwise $x$ is a P-position if and only if $(p+q+x_{2})$ is even, where

$\displaystyle p=\left[(x_{1}+x_{3}-x_{2})\equiv 3\pmod{4}\right],$
$\displaystyle q=\left[\begin{aligned}
&(x_{1}+x_{2}+x_{3}-2x_{4}-c)=12k,&&k\in\mathbb{Z}_{\geq 0},\\\
&c=5,&&\text{if $(x_{1}+x_{2})$ is odd},\\\ &c=2+3\big{(}(x_{1}+x_{2})\bmod
4\big{)},&&\text{otherwise.}\end{aligned}\right]$