Multi-player Last Nim with Passes

Abstract

We introduce a class of impartial combinatorial games, Multi-player Last Nim with Passes, denoted by MLNim$^{(s)}(N,n)$: there are N piles of counters which are linearly ordered. In turn, each of n players either removes any positive integer of counters from the last pile, or makes a choice ‘pass’. Once a ‘pass’ option is used, the total number s of passes decreases by 1. When all s passes are used, no player may ever ‘pass’ again. A pass option can be used at any time, up to the penultimate move, but cannot be used at the end of the game. The player who cannot make a move wins the game. The aim is to determine the game values of the positions of MLNim$^{(s)}(N,n)$ for all integers $N\ge 1$ and $n\ge 3$ and $s\ge 1$. For $n>N+1$ or $n=N+1\ge 3$, the game values are completely determined for any $s\ge 1$. For $3\le n\le N$, the game values are determined for infinitely many triplets (N, n, s). We also present a possible explanation why determining the game values becomes more complicated if $n\le N$.

1 Introduction

Combinatorial game theory is a branch of mathematics devoted to studying the optimal strategy in perfect-information games where typically two players are involved. In a 2-person perfect information game two players alternate moves until one of them is unable to move at his turn. Among the games of this type, as a non-exhaustive list, are Nim (Albert and Nowakowski 2004; Bouton 1901; Flammenkamp et al. 2003; Holshouser et al. 2003; Liu and Zhao 2016), End-Nim (Albert and Nowakowski 2001; Fraenkel and Lorberbom 1991), etc.

Last Nim with two players introduced by Friedman (2000) is played with piles of counters which are linearly ordered. The two players take turns removing any positive integer of counters from the last pile. Under normal play convention, all P-positions of Last Nim with two players are those containing an odd number of piles containing 1 counter.

1.1 Multi-player combinatorial game

During the last few years, the theory of 2-player perfect information games has been widely studied. Naturally it is of interest to generalize as much as possible of the theory to n-player games. In 2-player perfect information games, one can always talk about what the outcome of the game should be, when each player plays it right, i.e. when each player adopts an optimal strategy. But when there are more than two players, it may not make sense to talk about the same thing. For instance, it may so happen that one of the players can help any of the players to win, but anyhow, he himself has to lose. So the outcome of the game depends on how coalitions are formed among the players. In previous literature, several possibilities were investigated: multi-player without alliance, multi-player with two alliances and multi-player with alliance system.

• Multi-player without alliance

N -player Nim without alliance was introduced by Li (1978). Straffin (1985) attempted to classify three-player games using somewhat restrictive assumptions regarding the behavior of each player. This work was also investigated by Loeb (1996) by introducing the notion of a stable winning coalition (where a member of this coalition is guaranteed a winner). Other work done by Propp (1996) analyzed the required circumstances which allow one player to have a winning strategy against the combined forces of the others. Cincotti (2010) gave an analysis of n-player partizan games.

• Multi-player with two alliances

The game of n -player one-pile bounded Nim with two alliances, denoted by OBN, was investigated by Kelly (2006, 2011): given an integer $m\ge 1$ and a pile of counters, suppose that $n\ge 2$ players form two alliances and that each player is in exactly one alliance. Also assume that each player will support his alliance’s interests. Each player is allowed to remove $\ell$ counters from the pile, where $\ell \in \{1,2,\ldots , m\}$. Under misère play convention, the alliance which takes the last counter is the loser (the other alliance is the winner); under normal play convention, the alliance which takes the last counter is the winner (the other alliance is the loser).

A position is defined to be an unsafe position of one alliance if the game begins from this position and no matter what move this alliance makes, when the other alliance plays optimally, this alliance must lose. Under misère play convention, Kelly (2006, 2011) gave all unsafe positions of OBN for some special structures of two alliances.

More general structures of two alliances were investigated by Zhao and Liu (2016), and all unsafe positions of OBN were determined for more general structures of two alliances. Moreover, the authors also pointed out that some conclusions given by Kelly are not correct, and presented a possible explanation for Kelly’s inaccurate conclusions.

• Multi-player with alliance system

Krawec (2012) assumed that every player has a fixed set of allegiances to all n players, i.e. an alliance system may be defined arbitrarily before the start of a game. While the alliance system used is fixed for the duration of the game, Krawec provided a method of analyzing n-player impartial games, and derived a recursive function capable of determining which of the n players has a winning strategy.

Krawec (2015) also developed a method of analyzing n-player impartial combinatorial games where $n-1$ players behave optimally while one of the players plays randomly, i.e. one player chooses games at random without strategy.

1.2 Two-player combinatorial games with pass

Guy and Nowakowski (2009) wrote that “David Gale would like to see an analysis of Nim played with the option of a single pass by either of the players, which may be made at any time up to the penultimate move. It may not be made at the end of the game. Once a player has passed, the game is as in ordinary Nim. The game ends when all heaps have vanished.”

Morrison et al. (2012) used a dynamical systems approach to analyze ‘Three-Heap Nim with a Pass’. Their findings indicated a deep and rich complexity when a pass is added, and suggested that obtaining a complete analytical solution (in the spirit of Bouton) may be intractable. Low and Chan (2015) gave a partial analysis of ‘Nim with a pass’. To the best of our knowledge, no further result was proved.

1.3 Our games and results

In the present paper we introduce a class of impartial combinatorial games, Multi-player Last Nim with Passes, assuming that the standard alliance matrix (to be defined shortly) is adopted.

Definition 1

• (i) “Multi-player Last Nim without Passes”: There are N piles of counters $(x_1,x_2,\ldots ,x_N)$ which are linearly ordered. There are n players, who take turns in sequential unchanging order. Each player, at his turn, removes any positive integer number of counters from the last pile if that pile contains at least one counter (if the last pile contains no counter, the pile of size $x_{N-1}$ becomes a new last pile, and the game continues). The first player who cannot make any legal move wins. For brevity, this game is denoted by MLNim(N, n).

• (ii) “Multi-player Last Nim with s passes”, denoted by MLNim$^{(s)}(N,n)$: It is played like MLNim(N, n) with s passes and each pass can be used only once. Once a pass option is used, the game continues in MLNim$^{(s-1)}(N,n)$, i.e. the total number of passes decreases by 1. Once all s passes are used, no further pass option can be used, and the game continues as in “Multi-player Last Nim without Passes”, i.e. MLNim$^{(0)}(N,n) =$MLNim(N, n). A pass option can be used at any time, up to the penultimate move, but cannot be used at the end of the game. The player who cannot make a move wins the game.

Let $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{N};s)$ with $x_{i}\ge 1$ for all $i\in \{1,2,\ldots , N\}$ be a position of MLNim$^{(s)}(N,n)$. The aim of the present paper is to determine the game values $g(\mathbf p ;s)$ (to be defined shortly, but loosely speaking, the game value $g(\mathbf p ;s)$ determines the winning player of game $(\mathbf p ;s)$) for all integers $N\ge 1$ and $n\ge 3$ and $s\ge 0$. In order to determine the game values $g(\mathbf p ;s)$ where $s\ge 1$ (with s passes), we must first determine the game values $g(\mathbf p ;0)$ (without pass).

In Sect. 3 the game values $g(\mathbf p ;0)$ (for brevity, $g(\mathbf p )$) of MLNim(N, n) are completely determined for two cases: $n>N+1$ (Theorem 1) and $n=N+1$ (Theorem 2). For $3\le n\le N$, by letting $d=N-n\ge 0$, MLNim(N, n) can be rewritten as MLNim$(n+d,n)$ with $d\ge 0$ and $n\ge 3$. The game values $g(\mathbf p )$ of MLNim($n+d,n$) are completely determined for three cases: $n\ge d+3$ (Theorem 3), $n=d+2\ge 3$ (Theorem 4), and $n=d+1\ge 3$ (Theorem 5). Theorem 6 gives the game values $g(\mathbf p )$ where $n=d=3$, which explains partly why determining the game values $g(\mathbf p )$ for the case $3\le n\le d$ is more difficult.

Section 4 aims to determine the game values $g(\mathbf p ;s)$ of MLNim$^{(s)}(N,n)$ for any integer $s\ge 1$:

• For the case $n>N+1$, Theorem 7 in Sect. 4.1 shows that $g(\mathbf p ;s)=g(\mathbf p ;0)=N$ for all integers $s,N\ge 1$, i.e. the game value of a position $(\mathbf p ;s)$ is equal to the number N of the piles of $\mathbf p$ which do not depend on the number s of the total passes.

• For $n=N+1\ge 3$, Theorem 9 in Sect. 4.2 shows that $g(\mathbf p ;s)=g(\mathbf p ;\bar{s})$ for all integers $s\ge 1$ and $N\ge 2$, where $\bar{s}=s$ mod n. Before giving this result, Theorem 8 in Sect. 4.2 shows that for $\bar{s}\in \{1,2,\ldots ,n-2\}$, $g(\mathbf p ;\bar{s})=\bar{s}-1$ if $x_{n-1}=1$, or $\bar{s}$ if $x_{n-1}>1$; and that for $\bar{s}=n-1$, $g(\mathbf p ;\bar{s})=\bar{s}-1$ if $x_{n-1}=1$, or $\bar{s}$ if $x_{n-1}=2$, or $\bar{s}+1(=0)$ if $x_{n-1}>2$.

• The case $3\le n\le N$ is also investigated in Sects. 4.3, 4.4 and 4.5:

Theorem 10 shows that $g(\mathbf p ;s)\in \{d+s,d+s+1\}$ if $n\ge s+d+3$. Theorem 11 shows that $g(\mathbf p ;s)\in \{n-2,n-1,0\}$ if $n=s+d+2\ge 3$. Based on Theorems 10 and 11, we see that $g(\mathbf p ;s)=g(\mathbf p ;0)+s$, i.e. the game value of $(\mathbf p ;s)$ (with s passes) is equal to the sum of the game value of $(\mathbf p ;0)$ (without passes) and the number s of the total passes.

Theorem 12 gives $g(\mathbf p ;s)\in \{n-1,0,1\}$ for the case $n=s+d+1$. It turns out that $g(\mathbf p ;s)=g(\mathbf p ;0)+s$ does not hold for this case.

In Sect. 5 we give a summary of our findings and in Sect. 6 we present some future work.

2 Basic definitions

Throughout the paper, we employ some definitions and notation used by Krawec (2012, 2015).

Definition 2

• (i) A player shall be referenced as $P_{i}$ where i is an integer between 0 and $n-1$ inclusive. Unless otherwise stated, player $P_{0}$ is the first to move followed by $P_{1}$ and so on. After player $P_{n-1}$’s turn, $P_{0}$ will play again. Hence any arithmetic in the subscript (e.g., $P_{i+j}$) is done modulo n.

• (ii) Given an n-player game G, the game value of G (denoted by g(G, i)) is an integer between 0 and $n-1$ (inclusive) which specifies the player, relative to the current player $P_i$, that can win. For instance, if it is player $P_{i}$’s turn, and the game value $g(G,i)=j$, then $P_{i+j}$ (with subscript mod n) has a wining strategy, i.e. $P_{(i+j)\bmod n}$ is the winning player.

• (iii) An endgame, denoted by $\emptyset$, is a game where no legal move is available to the current player. Given an n-player game G, we denote by Opt(G) the set of all options that the current player can move to in one legal move.

Definition 3

• (i) An alliance system, is represented by an $n\times n$ matrix of the following form, known to all players before the start of the game,

  $$\begin{aligned} \left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} A_{0,0} &{}A_{0,1} &{}\cdots &{}A_{0,n-1} \\ A_{1,0} &{}A_{1,1} &{}\cdots &{}A_{1,n-1} \\ \vdots &{}\vdots &{} &{}\vdots \\ A_{n-1,0} &{}A_{n-1,1} &{}\cdots &{}A_{n-1,n-1} \\ \end{array}\right) \end{aligned}$$

  where each entry $A_{i,j}$ determines the most preferred player choice for player $P_{i}$, with left-most entries being more preferred over right-most entries (i.e., smaller values of j specify more preferred players).

• (ii) The following alliance system is called the Standard Alliance Matrix (for brevity, SAM)

  $$\begin{aligned}\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} 0 &{}1 &{}\cdots &{}n-1 \\ 0 &{}1 &{}\cdots &{}n-1 \\ \vdots &{}\vdots &{} &{}\vdots \\ 0 &{}1 &{}\cdots &{}n-1 \\ \end{array}\right) \end{aligned}$$

Definition 3 implies that, given any $i,j\in \{0,1,2,\ldots ,n-1\}$, the j-th preferred player for player $P_{i}$ would be $P_{(i+A_{i,j})\mod n}$ ($P_{i}$ prefers $P_{(i+A_{i,0})\mod n}$ over $P_{(i+A_{i,1})\mod n}$ over $P_{(i+A_{i,2})\mod n}$ $\ldots$ over $P_{(i+A_{i,n-1})\bmod n}$). For example, let $n=4$, i.e. there are four players $P_{0},P_{1},P_{2}$ and $P_{3}$. Assume that

$P_{0}$ prefers $P_{0}$ over $P_{1}$ over $P_{2}$ over $P_{3}$,

$P_{1}$ prefers $P_{1}$ over $P_3$ over $P_{0}$ over $P_{2}$,

$P_{2}$ prefers $P_2$ over $P_{0}$ over $P_{3}$ over $P_{1}$ and

$P_{3}$ prefers $P_{2}$ over $P_{1}$ over $P_{0}$ over $P_{3}$.

Then the alliance system is

$$\begin{aligned}\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} 0 &{}1 &{}2 &{}3 \\ 0 &{}2 &{}3 &{}1 \\ 0 &{}2 &{}1 &{}3 \\ 3 &{}2 &{}1 &{}0 \\ \end{array}\right) \end{aligned}$$

In particular, if we adopt SAM then for each $i\in \{0,1,2,\ldots ,n-1\}$, player $P_{i}$ prefers $P_{i}$ over $P_{i+1}$ over $\ldots$ over $P_{n-1}$ over $P_0$ over $\ldots$ over $P_{i-1}$.

Using above definitions, Krawec (2012) introduced a function $g: \mathcal {C}_{G}\times \mathbb {Z}_{n}\rightarrow \mathbb {Z}_{n}$ (where $\mathcal {C}_{G}$ denotes the set of all impartial combinatorial games and $\mathbb {Z}_{n}=\{0,1,\ldots ,n-1\}$): for any $i \in \mathbb {Z}_{n}$,

$$\begin{aligned} g(G,i)=\left\{ \begin{array}{ll} 0, &{}\quad \text{ if } G=\emptyset ,\\ A_{i,\ell }, &{}\quad \text{ otherwise, } \end{array}\right. \end{aligned}$$

(1)

such that

$$\begin{aligned} \ell =\min \{j\in \mathbb {Z}_n\mid g(G',i+1)+1=A_{i,j}\quad \text{ with } \quad G'\in Opt(G)\}, \end{aligned}$$

where all arithmetic are done modulo n.

When using SAM, the game value function g(G, i) defined by Eq. (1) actually takes on a much simpler form shown below in Eq. (2). To see this just note that since every row in SAM is identical there is no need to keep track of turn parameter i. Furthermore $A_{i,j}=j$ so $A_{i,\ell }=\ell =\min \{j\in \mathbb {Z}_n\mid g(G',i+1)+1=j\}=\min \{g(G',i+1)+1\}$.

$$\begin{aligned} g(G) = \left\{ \begin{array}{ll} 0, &{}\quad \hbox {if }G=\emptyset ,\\ \min \{g(G')+1 \mid G'\in Opt(G) \}, &{}\quad \hbox {otherwise.} \end{array} \right. \end{aligned}$$

(2)

Applying Eq. (2), we have the following observations: for a fixed n and game G,

Observation 1

$g(G)=0$ if and only if $G=\emptyset$ or there exists an option $G'$ of G such that $g(G')=n-1$.

Observation 2

$g(G)=i\in \{1,2,\ldots ,n-2\}$ if and only if $i-1\le g(G')\le n-2$ for any option $G'\in Opt(G)$ and there exists at least one option $G'\in Opt(G)$ such that $g(G')=i-1$.

Observation 3

$g(G)=n-1$ if and only if $g(G')=n-2$ for any option $G'\in Opt(G)$.

3 Game values of MLNim(N, n) without passes

In this section we consider the games MLNim(N, n) for all integers $N\ge 1$ and $n\ge 3$, assuming that SAM is adopted. Any position of MLNim(N, n) can be represented by a vector $\mathbf p =(x_{1},x_{2},\ldots ,x_{N})$ with $x_{i}\ge 1$ for all $i\in \{1,2,\ldots , N\}$, as any pile of size 0 can be omitted. We also use the notation $\mathbf p \rightarrow \mathbf p '$ to represent that there exists a legal move which leads $\mathbf p$ to an option $\mathbf p '$. Given a position $\mathbf p =(x_1,x_{2},\ldots ,x_{N-1},x_{N})$ of MLNim(N, n), let $\mathbf p _{m}=(x_1,x_{2},\ldots ,x_{N-1},m)$ be the position obtained from $\mathbf p$ by replacing $x_{N}$ with m. In particular, $\mathbf p _0=(x_{1},x_{2},\ldots ,x_{N-1})$ is obtained from $\mathbf p$ by removing all counters from the last pile of size $x_{N}$ ($\mathbf p _0$ and $\mathbf p _m$ ($m\ge 1$) are positions of $N-1$ and N piles, respectively). It follows from the definition of MLNim(N, n) that the set of all options of a given position $\mathbf p =(x_{1},x_{2},\ldots ,x_{N-1},x_N)$ is

$$\begin{aligned} Opt(\mathbf{p })=\{\mathbf{p }_0\}{\cup } \{\mathbf{p }_m=(x_{1},x_{2},\ldots ,x_{N-1},m)| 1\le m\le x_N-1\}. \end{aligned}$$

(3)

Hence Eq. (2) can be rewritten as

$$\begin{aligned} g(\mathbf p ) = \left\{ \begin{array}{ll} 0, &{} \quad \text {if }{} \mathbf p =\emptyset ,\\ \min \{g(\mathbf p _t)+1\mid 0\le t\le x_N-1\}, &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

(4)

The game values $g(\mathbf p )$ of MLNim(N, n) are completely determined for two cases: $n>N+1$ (Sect. 3.1, Theorem 1) and $n=N+1$ (Sect. 3.2, Theorem 2). The case $n\le N$ is analyzed in Sect. 3.3.

3.1 Game values of MLNim(N, n) where $n>N+1$

Theorem 1

Consider MLNim(N, n) and any position $\mathbf p =(x_{1},x_{2},\ldots ,x_{N})$. If $n>N+1$, then $g(\mathbf p )=N$ for all $N\ge 1$. In other words, if $n>N+1$ then the game value of a position $\mathbf p$ is equal to the number of the piles of $\mathbf p$.

Proof

If $N=0$, $P_{0}$ cannot make any legal move i.e., $P_{0}$ wins. Hence $g(0) = 0$. We proceed by induction on $N\ge 1$:

• (i) For $N=1$, we will show that $g(x_1)=1$ by induction on $x_1\ge 1$: For $x_1=1$, we have $g(1)=\min \{g(0)+1\}=1$. Assume that $g(m)=1$ for $1\le m<x_1$. By Eq. (4) we have $g(x_1)=\min (\{g(0)+1\}\cup \{g(m)+1\mid 1\le m<x_1\})=\min \{1,2\}=1$. Hence $g(x_1)=1$ for all $x_1\ge 1$.

• (ii) Assume that $g(x_{1},x_{2},\ldots ,x_{N'})=N'$ if $1\le N'\le N-1$. We take some fixed $N\ge 2$ and show that $g(\mathbf p _t)=N$ by induction on $t\ge 1$:

Base case: $t=1$. Now $\mathbf p _1$ only has one option $\mathbf p _0=(x_1,x_{2},\ldots ,x_{N-1})$ with $N'=N-1$ piles. By induction hypothesis on $N'=N-1$ we have $g(\mathbf p _0)=N-1$. Thus $g(\mathbf p _1)=\min \{g(\mathbf p _0)+1\}=N$.

Induction step: $t\ge 2$. Assume that $g(\mathbf p _m)=N$ for all $1\le m<t$. It follows from Eq. (4) that

$$\begin{aligned} \begin{array}{rcl} g(\mathbf p _t)&{}=&{}\min (\{g(\mathbf p _0)+1\}\cup \{g(\mathbf p _{m})+1\mid 1\le m<t\})\\ &{}=&{}\min \{N,N+1\}=N. \end{array} \end{aligned}$$

(5)

By letting $t=x_N$ in Eq. (5), we have $g(\mathbf p )=N$, as required. $\square$

3.2 Game values of MLNim(N, n) where $n=N+1$

Theorem 2

Consider MLNim(N, n) and any position $\mathbf p =(x_{1},x_{2},\ldots ,x_{N})$. If $n=N+1\ge 3$ then for any $N\ge 2$,

$$\begin{aligned} g(\mathbf p )= \left\{ \begin{array}{ll} N, &{}\quad \text{ if } x_{N}=1,\\ 0, &{}\quad \text{ if } x_{N}>1.\\ \end{array} \right. \end{aligned}$$

(6)

Proof

• (i) For $x_{N}=1$, the position $\mathbf p =(x_{1},x_{2},\ldots ,x_{N-1},1)$ only has one option $\mathbf p _0=(x_{1},x_{2},\ldots ,x_{N-1})$ with $N'=N-1$ piles and $n=N+1=N'+2>N'+1$. Theorem 1 gives $g(\mathbf p _0)=N'=N-1$. Thus $g(\mathbf p )=\text{ min }\{g(\mathbf p _0)+1\}=N$.

• (ii) For $x_{N}>1$, the position $\mathbf p$ has $\mathbf p _1=(x_{1},x_{2},\ldots ,x_{N-1},1)$ as an option. By (i) we have $g(\mathbf p _1)=N=n-1$. Observation 1 gives $g(\mathbf p )=0$. $\square$

Remark 1

If $n=N+1$ then $g(x_{1},x_{2},\ldots ,x_{N})\in \{N,0\}=\{n-1,0\}$. This implies that any player $P_i$, $i\in \{1,2,3,\ldots , n-2\}$, has no chance to win the game $\mathbf p =(x_{1},x_{2},\ldots ,x_{n-2},x_{n-1})$. In other words, if $P_0$ is the first player then the winner will be $P_{n-1}$ if $x_{n-1}=1$, or $P_0$ if $x_{n-1}>1$:

• (i) For the position $\mathbf p _1=(x_{1},x_{2},\ldots ,x_{n-2},x_{n-1})$ with $x_{n-1}=1$, the first player $P_0$ must remove 1 counter from the pile of size $x_{n-1}=1$, the player $P_1$ removes all counters from the pile of size $x_{n-2}$, $\cdots$, the player $P_{n-2}$ removes all counters from the pile of size $x_{1}$. Now the player $P_{n-1}$ faces an endgame and wins, i.e. the first player $P_0$ has no chance to win.

• (ii) For the position $\mathbf p =(x_{1},x_{2},\ldots ,x_{n-2},x_{n-1})$ with $x_{n-1}>1$, $P_0$ has chance to win! The first player $P_0$ removes $x_{n-1}-1$ counters from the pile of size $x_{n-1}$ and leaves $P_1$ to the position $\mathbf p _1=(x_1,x_{2},\ldots ,x_{n-2},1)$ to play. By the analysis of (i), starting from $\mathbf p _1$, the player $P_1$ must remove 1 counter from the pile of size $x_{n-1}=1$, the player $P_2$ removes all counters from the pile of size $x_{n-2}$, $\cdots$, the player $P_{n-1}$ removes all counters from the pile of size $x_{1}$. Hence the first player $P_{0}$ faces an endgame and wins. $\square$

3.3 Game values of MLNim(N, n) where $n\le N$

In this subsection we consider MLNim(N, n) where $3\le n\le N$. Let $d=N-n$ and rewrite MLNim(N, n) as MLNim($n+d,n$) where $n\ge 3$ and $d\ge 0$. We will give the game values of MLNim($n+d,n$) by distinguishing $n\ge d+3$ (Theorem 3), $n=d+2$ (Theorem 4) and $n=d+1$ (Theorem 5).

Theorem 3 gives the game values of MLNim($n+d,n$) for all integers $d\ge 0$ and $n\ge d+3$. It turns out that the game values of MLNim($n+d,n$) only have two values, d and $d+1$, which depend only on whether $x_{n-1}=1$. All games MLNim($n+d,n$) solved by Theorem 3 are labeled by under-dash-line in Table 1.

Theorem 4 gives the game values of MLNim($n+d,n$) for $n=d+2\ge 3$, i.e. $(n+d,n)\in \mathbb {W}=\{(2d+2,d+2)\mid d\ge 1\}=\{(4,3),(6,4),(8,5),(10,6),\ldots \}$. All games MLNim($n+d,n$) solved by Theorem 4 are labeled by under-wave-line in Table 1.

Theorem 5 gives the game values of MLNim($n+d,n$) for $n=d+1\ge 3$, i.e. $(n+d,n)\in \mathbb {W}^*=\{(2d+1,d+1)\mid d\ge 2\}=\{(5,3),(7,4),(9,5),(11,6),\ldots \}$. All games MLNim($n+d,n$) solved by Theorem 5 are labeled by under-line in Table 1.

Table 1 All games of MLNim($n+d,n$) where $n\ge 3$ and $d\ge 0$

Given a position $\mathbf p =(x_{1},x_{2},\ldots ,x_{n-1},x_n,x_{n+1},\ldots ,x_{n+d})$ of MLNim($n+d,n$), we define an auxiliary function

$$\begin{aligned}\delta =\left\{ \begin{array}{ll} 0, &{} \text{ if } x_{n-1}=1,\\ 1, &{} \text{ if } x_{n-1}>1.\\ \end{array}\right. \end{aligned}$$

Theorem 3

Consider MLNim($n+d,n$) and a position $\mathbf p =(x_{1},x_{2},\ldots ,x_{n+d})$. For any $d\ge 0$, if $n\ge d+3$ then

$$\begin{aligned} g(\mathbf p )=d+\delta = \left\{ \begin{array}{ll} d, &{}\quad \text{ if } x_{n-1}=1,\\ d+1, &{}\quad \text{ if } x_{n-1}>1.\\ \end{array} \right. \end{aligned}$$

(7)

Proof

We proceed by induction on $d\ge 0$.

• (i) Base case: $d=0$. Now $\mathbf p =(x_{1},x_2,\ldots ,x_{n-2},x_{n-1},x_n)$. We show that $g(\mathbf p )=\delta$ for all integers $n\ge 3$: The position $\mathbf p$ has $\mathbf p _0$ as an option. Note that $\mathbf p _0$ is a position of MLNim($N',n$) with $N'=n-1\ge 2$ i.e. $n=N'+1\ge 3$. We consider the following two cases:

  • $x_{n-1}=1$. Theorem 2 gives $g(\mathbf p _0)=N'=n-1$ as $x_{N'}=x_{n-1}=1$. By Observation 1 we have $g(\mathbf p )=0$.

  • $x_{n-1}>1$. Theorem 2 shows that $g(\mathbf p _0)=0$ as $x_{N'}=x_{n-1}>1$. We will show that $g(\mathbf p _t)=1$ by induction on $t\ge 1$: For $t=1$, the position $\mathbf p _1=(x_{1},\ldots ,x_{n-2},x_{n-1},1)$ only has one option $\mathbf p _0$, thus $g(\mathbf p _1)=\text{ min }\{g(\mathbf p _0)+1\}=1$. Suppose that $g(\mathbf p _m)=1$ for all $1\le m<t$. Thus $g(\mathbf p _t)=\text{ min }(\{g(\mathbf p _0)+1\}\cup \{g(\mathbf p _m)+1\mid 1\le m<t\})= \text{ min }\{1,2\}=1$. By letting $t=x_{n}$, we have $g(\mathbf p )=1$, as required.

• (ii) Induction step: $d\ge 1$. Assume that $g(x_{1},x_2,\ldots , x_{n+d'})=d'+\delta$ for $0\le d'<d$ and $n\ge d'+3$. We will show that $g(\mathbf p _t)=d+\delta$ by induction on $t\ge 1$:

Base case: $t=1$. Now $\mathbf p _1$ only has an option $\mathbf p _0$ which is a position of MLNim($n+d',n$) with $d'=d-1$ and $n\ge d+3=d'+4>d'+3$. The induction hypothesis on $d'$ implies that $g(\mathbf p _0)=d'+\delta$. Thus $g(\mathbf p _1)=g(\mathbf p _0)+1=d+\delta$.

Induction step: $t\ge 2$. Suppose that $g(\mathbf p _m)=d+\delta$ for all $1\le m<t$. It follows from Eq. (4) that

$$\begin{aligned} \begin{array}{rcl} g(\mathbf p _t)&{}=&{}\text{ min }(\{g(\mathbf p _0)+1\}\cup \{g(\mathbf p _m)+1\mid 1\le m<t\})\\ &{}=&{}\text{ min }\{d+\delta ,d+\delta +1\}=d+\delta . \end{array} \end{aligned}$$

(8)

By letting $t=x_{n+d}$ in Eq. (8), we have $g(\mathbf p )=d+\delta$, as required. $\square$

Remark 2

If $n\ge d+3$ then starting from $\mathbf p =(x_{1},x_{2},\ldots ,x_{n+d})$, the winner will be $P_{d}$ if $x_{n-1}=1$, or $P_{d+1}$ if $x_{n-1}>1$. The winning strategy is as follows:

The first $d+1$ players $P_0, P_1, \ldots , P_{d}$ remove all counters from the piles of size $x_{n+d}$, $x_{n+d-1}$, $\ldots$, $x_{n}$, respectively. Now it is $P_{d+1}$’s turn and begin to play the game $\mathbf p ^*=(x_{1},x_{2},\ldots ,x_{n-1})$ which is a position of MLNim($N',n$) with $N'=n-1$. It follows from Theorem 2 that $g(\mathbf p ^*)=N'=n-1$ if $x_{n-1}=1$, or 0 if $x_{n-1}>1$. This means that the player $P_{d+1}$ starts from $\mathbf p ^*$, the winer is $P_{d+1+n-1}=P_{d}$ if $x_{n-1}=1$, or $P_{d+1+0}=P_{d+1}$ if $x_{n-1}>1$ (Remark 1 gives the corresponding winning strategy).

Theorem 4

Consider MLNim($n+d,n$) and a position $\mathbf p =(x_{1},x_{2},\ldots ,x_{n+d})$. If $n=d+2\ge 3$ then for any $d\ge 1$, we have

$$\begin{aligned} g(\mathbf p )= \left\{ \begin{array}{ll} d(=n-2), &{}\quad \text{ if } x_{n-1}=1 ,\\ d+1(=n-1), &{}\quad \text{ if } x_{n-1}>1 \text{ and } x_{n+d}=1,\\ d+2(=0), &{}\quad \text{ if } x_{n-1}>1 \text{ and } x_{n+d}>1.\\ \end{array} \right. \end{aligned}$$

(9)

Proof

• (i) If $x_{n-1}>1$ and $x_{n+d}=1$, $\mathbf p =\mathbf p _1$ only has an option $\mathbf p _0$. By letting $d'=d-1$ we have $n=d+2=d'+3$. Theorem 3 gives $g(\mathbf p _0)=d'+1=d$. Hence $g(\mathbf p _1)=d+1$.

• (ii) If $x_{n-1}>1$ and $x_{n+d}>1$, $\mathbf p$ has $\mathbf p _1=(x_{1},x_2,\ldots ,x_{n+d-1},1)$ as an option. By (i) we have $g(\mathbf p _1)=d+1=n-1$. Observation 1 gives $g(\mathbf p )=0$.

• (iii) For the case $x_{n-1}=1$, we show that $g(\mathbf p _t)=d$ by induction on $t\ge 1$: for $t=1$, $\mathbf p _1$ only has an option $\mathbf p _0$. By letting $d'=d-1\ge 0$ we have $n=d+2=d'+3$. Theorem 3 gives $g(\mathbf p _0)=d'=d-1$, thus $g(\mathbf p _1)=\text{ min }\{g(\mathbf p _0)+1\}=d'+1=d$. Suppose that $g(\mathbf p _m)=d$ for all values $1\le m<t$. Then $g(\mathbf p _t)=\text{ min }(\{g(\mathbf p _0)+1\}\cup \{g(\mathbf p _m)+1\mid 1\le m<t\})= \text{ min }\{d,d+1\}=d$. By letting $t=x_{n+d}$, we have $g(\mathbf p )=d$, as required.$\square$

Theorem 5

Consider MLNim($n+d,n$) and a position $\mathbf p =(x_{1},x_{2},\ldots ,x_{n+d})$. If $n=d+1\ge 3$ then

$$\begin{aligned} \ g(\mathbf p )= \left\{ \begin{array}{ll} d(=n-1), &{} \text{ if } x_{n-1}=1 \text{ and } x_{n+d}=1 ,\\ d+1(=0), &{} \text{ if } (x_{n-1}=1 \text{ and } x_{n+d}>1)\\ &{} \text{ or } (x_{n-1}>1 \text{ and } x_{n+d-1}=1),\\ d+2(=1), &{} \text{ if } x_{n-1}>1 \text{ and } x_{n+d-1}>1.\\ \end{array} \right. \end{aligned}$$

(10)

Proof

• (i) $x_{n-1}=1$ and $x_{n+d}=1$. Now $\mathbf p =\mathbf p _1=(x_{1},x_{2},\ldots ,x_{n+d-1},1)$ only has one option $\mathbf p _0=(x_{1},\ldots ,x_{n-2},1,x_{n},\ldots ,x_{n+d-1})$. By letting $d'=d-1\ge 1$ we have $n=d+1=d'+2\ge 3$. Theorem 4 gives $g(\mathbf p _0)=d'=d-1$. Hence $g(\mathbf p )=d'+1=d$.

• (ii) $x_{n-1}=1$ and $x_{n+d}>1$. Now $\mathbf p$ has $\mathbf p _1$ as an option. By (i) we have $g(\mathbf p _1)=d=n-1$. Observation 1 gives $g(\mathbf p )=0$.

• (iii) $x_{n-1}>1$ and $x_{n+d-1}=1$. Now $\mathbf p =(x_{1},x_{2},\ldots ,x_{n+d-2},1,x_{n+d})$ has $\mathbf p _0=(x_{1},x_{2},\ldots ,x_{n+d-2},1)$ as an option. By letting $d'=d-1\ge 1$ we have $n=d+1=d'+2\ge 3$. Theorem 4 gives $g(\mathbf p _0)=d'+1=d=n-1$. Observation 1 means that $g(\mathbf p )=0$.

• (iv) $x_{n-1}>1$ and $x_{n+d-1}>1$. Now $\mathbf p _0=(x_{1},x_{2},\ldots ,x_{n+d-1})$. By letting $d'=d-1\ge 1$ we have $n=d+1=d'+2\ge 3$. Theorem 4 gives $g(\mathbf p _0)=d'+2=d+1=0$. We show that $g(\mathbf p _t)=1$ by induction on $t=x_{n+d}\ge 1$: For $t=1$, $\mathbf p _1$ only has an option. Thus $g(\mathbf p _1)=1$. Suppose that $g(\mathbf p _m)=1$ for all $1\le m<t$. It follows from Eq. (4) that $g(\mathbf p _t)=\text{ min }(\{g(\mathbf p _0)+1\}\cup \{g(\mathbf p _m)+1\mid 1\le m<t\})= \text{ min }\{1,2\}=1$. By letting $t=x_{n+d}$, we have $g(\mathbf p )=1$, as required.

$\square$

Remark 3

Let $\mathbf p =(x_{1},x_2,\ldots ,x_{n+d-1},x_{n+d})$ and $\mathbf p _0=(x_{1},x_{2},\ldots ,x_{n+d-1})$. Theorems 3, 4 and 5 show that the game values $g(\mathbf p )$ depend on one parameter $x_{n-1}$ if $n\ge d+3$, two parameters $x_{n-1}$ and $x_{n+d}$ if $n=d+2$, three parameters $x_{n-1}$ and $x_{n+d}$ and $x_{n+d-1}$ if $n=d+1$, respectively.

We analyze the case $n=d+1$. Now the position $\mathbf p$ has $\mathbf p _0$ as an option, which is a position of MLNim($n+d',n$) with $d'=d-1$ and $n=d+1=d'+2$. In order to determine $g(\mathbf p _0)$, we must use Theorem 4 which shows that the value $g(\mathbf p _0)$ depends on a new parameter $x_{n+d'}=x_{n+d-1}$. This fact implies that the game value $g(\mathbf p )$ depends on three parameters $x_{n-1}$, $x_{n+d}$ and $x_{n+d-1}$.

Similarly, if $n=d$ then the position $\mathbf p$ has $\mathbf p _0$ as an option, which is a position of MLNim($n+d',n$) with $d'=d-1$ and $n=d=d'+1$. In order to determine $g(\mathbf p _0)$, we must use Theorem 5, and hence a new parameter $x_{n+d'-1}=x_{n+d-2}$ appears. This fact implies that the game value $g(\mathbf p )$ depends on four parameters $x_{n-1}$, $x_{n+d}$, $x_{n+d-1}$ and $x_{n+d-2}$. The following Theorem 6 gives an example where $n=d=3$ and the four parameters are $x_{n-1}=x_2$, $x_{n+d}=x_6$, $x_{n+d-1}=x_5$ and $x_{n+d-2}=x_4$.

Theorem 6

Consider MLNim(6, 3), i.e. three players and six piles. Then for any position $\mathbf p =(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})$ with $x_{i}\ge 1$ for all $i\in \{1,2,\ldots ,6\}$, we have

$$\begin{aligned} g(\mathbf p )= \left\{ \begin{array}{ll} 2, &{} \text{ if } x_{2}>1 \text{ and } x_{4}>1 \text{ and } x_{6}=1,\\ 0, &{} \text{ if } (x_{2}>1 \text{ and } x_{4}>1 \text{ and } x_{6}>1)\\ &{}\ \ \text{ or } (x_{2}=1 \text{ and } x_{5}=1),\\ 1, &{} \text{ if } (x_{2}=1 \text{ and } x_{5}>1) \text{ or } (x_2>1 \text{ and } x_4=1). \end{array} \right. \end{aligned}$$

(11)

Proof

Let $\mathbf p _0=(x_{1},x_{2},x_3,x_{4},x_5)$ and $\mathbf p _t=(x_{1},x_{2},\ldots ,x_{5},t)$ for any $t\ge 1$. Note that $\mathbf p _0$ is a position of MLNim(5, 3) with $d=5-3=2$ and $n=3=d+1$. We proceed by considering the following cases:

• (i) $x_{2}>1$ and $x_{4}>1$ and $x_{6}=1$. Theorem 5 gives $g(\mathbf p _0)=1$. The position $\mathbf p =\mathbf p _1$ only has one option $\mathbf p _0$, thus $g(\mathbf p )=\text{ min }\{g(\mathbf p _0)+1\}=2$.

• (ii) $x_{2}>1$ and $x_{4}>1$ and $x_{6}>1$. Now $\mathbf p$ has $\mathbf p _1=(x_{1},x_{2},x_3,x_{4},x_5,1)$ as an option ($\mathbf p _1$ is obtained by removing $x_6-1$ counters from the last pile). By (i) we have $g(\mathbf p _1)=2=n-1$. Observation 1 gives $g(\mathbf p )=0$.

• (iii) $x_{2}=1$ and $x_{5}=1$. The position $\mathbf p$ has $\mathbf p _0=(x_{1},x_{2},x_{3},x_{4},1)$ as an option. Theorem 5 gives $g(\mathbf p _0)=2=n-1$. By Observation 1 we have $g(\mathbf p )=0$.

• (iv) ($x_{2}=1$ and $x_{5}>1$) or ($x_2>1$ and $x_{4}=1$). For both cases, we show that $g(\mathbf p _t)=1$ by induction on $t\ge 1$: for $t=1$, $\mathbf p _1$ only has one option $\mathbf p _0$ and Theorem 5 gives $g(\mathbf p _0)=0$, thus $g(\mathbf p _1)=\text{ min }\{g(\mathbf p _0)+1\}=1$. Suppose that $g(\mathbf p _m)=1$ for all integers $1\le m<t$. Thus $g(\mathbf p _t)=\text{ min }(\{g(\mathbf p _0)+1\}\cup \{g(\mathbf p _m)+1\mid 1\le m<t\})= \text{ min }\{1,2\}=1$. By letting $t=x_{6}$, we have $g(\mathbf p )=1$, as required. $\square$

4 Multi-player Last Nim with s passes

In this section we consider the games MLNim$^{(s)}(N,n)$ for all integers $N\ge 1$ and $n\ge 3$ and $s\ge 1$, assuming that SAM is adopted. A position of MLNim$^{(s)}(N,n)$ can be represented by $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{N};s)$ with $x_{i}\ge 1$ for each $i\in \{1,2,\ldots ,N\}$. By $g(\mathbf p ;s)$ we denote the game value of the position $(\mathbf p ;s)$. In particular, $g(\mathbf p ;0)=g(\mathbf p )$. Given a position $(\mathbf p ;s)$ with $s\ge 1$, it follows from the definition of MLNim$^{(s)}(N,n)$ that $(\mathbf p ;s)$ has two kinds of legal moves:

• The player makes a choice ‘pass’ i.e. $(\mathbf p ;s)\rightarrow (\mathbf p ;s-1)$ if $s>0$.

• The player removes $1\le m\le x_N$ counters from the pile of size $x_N$ i.e. $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{N};s)\rightarrow (\mathbf p _t;s)=(x_{1},x_{2},\ldots ,x_{N-1},t;s)$ where $t=x_N-m$.

Hence Eq. (2) can be rewritten as

$$\begin{aligned} g(\mathbf p ) = \left\{ \begin{array}{ll} 0, &{}\quad \text {if }{} \mathbf p =\emptyset ,\\ \min (\{g(\mathbf p ;s-1)+1\}\cup \{g(\mathbf p _t;s)+1\mid 0\le t\le x_N-1\}), &{}\quad \text {otherwise.} \end{array} \right. \end{aligned}$$

(12)

This section is to determine the game values $g(\mathbf p ;s)$ of MLNim$^{(s)}(N,n)$. Section 4.1 is devoted to the case $n>N+1$. Theorem 7 shows that the game value $g(\mathbf p ;s)=g(\mathbf p ;0)=N$ for any $N\ge 1$ and $s\ge 1$ i.e. the game value of a position $(\mathbf p ;s)$ is equal to the number of the piles of $\mathbf p$. In other words, the game value $g(\mathbf p ;s)$ depends on neither the size $x_i$ nor the total number s of passes.

Section 4.2 is devoted to the case $n=N+1\ge 3$. The game values $g(\mathbf p ;s)$ of MLNim$^{(s)}(N,n)$ are completely determined for all $N\ge 2$ and $s\ge 1$.

The case $3\le n\le N$ is analyzed in Sects. 4.3, 4.4 and 4.5.

4.1 Game values of MLNim$^{(s)}(N,n)$ where $n>N+1$

Theorem 7

Consider MLNim$^{(s)}(N,n)$ and $\mathbf p =(x_{1},x_{2},\ldots ,x_{N})$. For all integers $s\ge 0$ and $N\ge 1$, if $n>N+1$ then

$$\begin{aligned} g(\mathbf p ;s)=g(\mathbf p ;0)=N. \end{aligned}$$

(13)

In other words, if $n>N+1$ then the game value of a position $(\mathbf p ;s)$ is equal to the number of the piles of $(\mathbf p ;s)$. In particular, this does not depend on the parameter s.

Proof

It suffices to show that $g(\mathbf p _t;s)=N$ for all $s\ge 0$, $N\ge 1$ and $t\ge 1$.

We proceed by induction on $s\ge 0$. Theorem 1 gives $g(\mathbf p _t;0)=N$ for all $N\ge 1$ and $t\ge 1$. Assume that $g(\mathbf p _t;s')=N$ for $0\le s'\le s-1$ and all $N\ge 1$ and $t\ge 1$. We take some fixed $s\ge 1$ and show that $g(\mathbf p _t;s)=N$ by induction on $N\ge 1$:

• (i) Base case: $N=1$. For $N=1$ and $n>N+1=2$, we show that $g(x_{1};s)=1$ by induction on $x_{1}\ge 1$:

• (i.1) Base case: $x_{1}=1$. The position (1; s) only has two options $(1;s-1)$ and (0; s). The induction hypothesis on $s'=s-1$ implies that $g(1;s-1)=1$. We have $g(0;s)=0$ as (0; s) is an endgame. Hence $g(1;s)=\min \{g(1;s-1)+1,g(0;s)+1\}=\min \{2,1\}=1$.

• (i.2) Induction step: $x_{1}\ge 2$. Assume that $g(m;s)=1$ for all $1\le m<x_{1}$. It follows from Eq. (12) that $g(x_{1};s)=\min (\{g(x_{1};s-1)+1,g(0;s)+1\}\cup \{g(m;s)+1\mid 1\le m<x_1\})=\min \{2, 1, 2\}=1.$

• (ii) Induction step: $N\ge 2$. Assume that $g(x_{1},x_{2},\ldots ,x_{N'};s)=N'$ for $1\le N'\le N-1$. We take some fixed $N\ge 2$ and show that $g(\mathbf p _t;s)=N$ by induction on $t\ge 1$.

• (ii.1) Base case: $t=1$. Now $(\mathbf p _1;s)$ only has two options: $(\mathbf p _1;s-1)$ and $(\mathbf p _0;s)$ with $N'=N-1$ pile. The induction hypothesis on $s'=s-1$ implies that $g(\mathbf p _1;s-1)=N$. The induction hypothesis on $N'=N-1$ means that $g(\mathbf p _0;s)=N'=N-1$. Thus $g(\mathbf p _1;s)=\min \{g(\mathbf p _1;s-1)+1,g(\mathbf p _0;s)+1\}=\min \{N+1, N\}=N$.

• (ii.2) Induction step: $t\ge 2$. Assume that $g(\mathbf p _m;s)=N$ for all $1\le m<t$. The induction hypothesis on $s'=s-1$ implies that $g(\mathbf p _t;s-1)=N$. It follows from Eq. (12) that

  $$\begin{aligned} \begin{array}{lll} &{}&{}g(\mathbf p _t;s)\\ &{}&{}\quad =\min (\{g(\mathbf p _t;s-1)+1,g(\mathbf p _0;s)+1\}\cup \{g(\mathbf p _m;s)+1\mid 1\le m<t\})\\ &{}&{}\quad =\min \{N+1, N,N+1\}=N. \end{array} \end{aligned}$$

  (14)

By letting $t=x_{N}$ in Eq. (14), we have $g(\mathbf p ;s)=N$, as required. $\square$

4.2 Game values of MLNim$^{(s)}(N,n)$ where $n=N+1$

This subsection is to determining the game values $g(\mathbf p ;s)$ of MLNim$^{(s)}(N,n)$ where $n=N+1\ge 3$. Theorem 9 shows that $g(\mathbf p ;s)=g(\mathbf p ;\bar{s})$ for all integers $s\ge 0$ and $N\ge 2$, where $\bar{s}=s$ mod n. Theorem 8 determines the game values $g(\mathbf p ;\bar{s})$ by distinguishing two cases $\bar{s}\in \{0,1,2,\ldots ,n-2\}$ and $\bar{s}=n-1$, respectively.

Theorem 8

Consider any position $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{N};s)$ with $n=N+1$. For any $N\ge 2$, we have

• (A) if $s\in \{0,1,\ldots ,n-2\}$ then

  $$\begin{aligned} g(\mathbf p ;s) =g(\mathbf p ;0)+s=s-1+\delta =\left\{ \begin{array}{ll} s-1, &{}\quad \text{ if } x_{n-1}=1,\\ s, &{}\quad \text{ if } x_{n-1}>1.\\ \end{array} \right. \end{aligned}$$

  (15)

• (B) if $s=n-1$ then

  $$\begin{aligned} g(\mathbf p ;s) =\left\{ \begin{array}{ll} s-1, &{}\quad \text{ if } x_{n-1}=1,\\ s, &{}\quad \text{ if } x_{n-1}=2,\\ s+1(=0), &{} \quad \text{ if } x_{n-1}>2.\\ \end{array} \right. \end{aligned}$$

  (16)

Proof

Claim (A) We will show that $g(\mathbf p _t;s)=s-1+\delta$ by induction on $0\le s\le n-2$:

Theorem 2 gives that $g(\mathbf p _t;0)=N=n-1$ if $t=1$, or 0 if $t>1$. In other words, we have $g(\mathbf p _t;s)=s-1+\delta$ for $s=0$. Assume that $g(\mathbf p _t;s')=s'-1+\delta$ holds for $0\le s'<s\le n-2$. We take some fixed $1\le s\le n-2$ and show that $g(\mathbf p _t;s)=s-1+\delta$:

• The induction hypothesis on $s'=s-1$ implies that $g(\mathbf p _t;s-1)=s-2+\delta$ for any $t\ge 1$.

• Theorem 7 means that $g(\mathbf p _0;s)=N-1=n-2$ as $(\mathbf p _0;s)$ has $N'=N-1$ piles and $n=N+1=N'+2>N'+1$.

  • (A.1) If $t=1$, $(\mathbf p _1;s)$ only has two options $(\mathbf p _1;s-1)$ and $(\mathbf p _0;s)$. Hence $g(\mathbf p _1;s)=\min \{g(\mathbf p _1;s-1)+1,g(\mathbf p _0;s)+1\}=\min \{s-1, n-1\}=s-1=s-1+\delta$ as $\delta =0$.

  • (A.2) If $t>1$, we show that $g(\mathbf p _t;s)=s-1+\delta =s$ by induction on $t\ge 2$: In fact, $g(\mathbf p _2;s-1)=s-2+\delta =s-1$. By (A.1) we have $g(\mathbf p _1;s)=s-1$. Hence $g(\mathbf p _2;s)=\min \{g(\mathbf p _2;s-1)+1,g(\mathbf p _0;s)+1,g(\mathbf p _1;s)+1\}=\min \{s, n-1,s\}=s$.

    Assume that $g(\mathbf p _m;s)=s$ for all $2\le m<t$. Note that $g(\mathbf p _t;s-1)=s-2+\delta =s-1$. It follows from Eq. (12) that $g(\mathbf p _t;s)=\min (\{g(\mathbf p _t;s-1)+1,g(\mathbf p _0;s)+1,g(\mathbf p _1;s)+1\}\cup \{g(\mathbf p _m;s)+1\mid 2\le m<t\})=\min \{s, n-1, s, s+1\}=s$, as required.

    Claim (B) We consider $s=n-1$ and show that $g(\mathbf p _t;s) =s-1$ if $t=1$, or s if $t=2$, or $s+1(=0)$ if $t>2$:

  • (B.1) If $t=1$, $(\mathbf p _1;s)$ only has two options $(\mathbf p _1;s-1)$ and $(\mathbf p _0;s)$. The claim (A) gives that $g(\mathbf p _1;s-1)=s'-1=s-2$ where $s'=s-1=n-2$. Hence $g(\mathbf p _1;s)=\min \{g(\mathbf p _1;s-1)+1,g(\mathbf p _0;s)+1\}=\min \{s-1, n-1\}=s-1$.

  • (B.2) If $t=2$ then $g(\mathbf p _2;s)=\min \{g(\mathbf p _2;s-1)+1,g(\mathbf p _0;s)+1,g(\mathbf p _1;s)+1\}=\min \{s, n-1,s\}=s=n-1$ as the claim (A) gives $g(\mathbf p _2;s-1)=s-1$.

  • (B.3) If $t>2$, $(\mathbf p _t;s)=(x_{1},x_{2},\ldots ,x_{N-1},t;s)$ has $(\mathbf p _2;s)$ as an option. By (B.2) we have $g(\mathbf p _2;s)=s=n-1$. Observation 1 gives $g(\mathbf p _t;s)=0$, as required. $\square$

Theorem 9

Consider MLNim$^{(s)}(N,n)$ and $\mathbf p =(x_{1},x_{2},\ldots ,x_{N})$. If $n=N+1\ge 3$ then for any $s\ge 0$ and $N\ge 2$, we have

$$\begin{aligned} g(\mathbf p ;s) = g(\mathbf p ;\bar{s}), \end{aligned}$$

(17)

where $\bar{s}=s$ mod n denotes the remainder of s divided by n. In other words, the game value of a position $(\mathbf p ;s)$ with s passes is equal to that of $(\mathbf p ;\bar{s})$ with $\bar{s}$ passes.

Proof

Note that $(\mathbf p _0;s)$ has $N'=N-1$ piles. Theorem 7 shows that for any $s\ge 0$, we have $g(\mathbf p _0;s)=N'=N-1=n-2$ as $n=N+1=N'+2>N'+1$.

Let $s=qn+\bar{s}$ where $q\ge 0$ and $0\le \bar{s}\le n-1$. It suffices to show that

$$\begin{aligned} g(\mathbf p ;qn+\bar{s}) = g(\mathbf p ;\bar{s}). \end{aligned}$$

(18)

We proceed by showing the following three facts by induction on $q\ge 0$:

Fact A: $g(\mathbf p ;qn+\bar{s})=g(\mathbf p ;\bar{s})$ if $\bar{s}\in \{0,1,2,\ldots ,n-2\}$.

Fact B: $g(\mathbf p ;qn+\bar{s})= g(\mathbf p ;\bar{s})$ if $\bar{s}=n-1$.

Fact C: $g(\mathbf p ;(q+1)n)=g(\mathbf p ;0)$.

• (i) Base case: $q=0$. Facts A and B are obvious. In order to prove Fact C, it suffices to show that $g(\mathbf p ;n)=n-1$ if $x_N=1$, or 0 if $x_N>1$, as Theorem 2 shows that $g(\mathbf p ;0)=n-1$ if $x_N=1$, or 0 if $x_N>1$.

• (i.1) If $x_N=1$ then $g(\mathbf p _1;n)=\min \{g(\mathbf p _1;n-1)+1,g(\mathbf p _0;n)+1\}=\min \{n-1,n-1\}=n-1$ as Fact B and Theorem 8(B) show that $g(\mathbf p _1;n-1)=g(\mathbf p _1;s)=s-1=n-2$.

• (i.2) If $x_N>1$, the position $(\mathbf p ;n)$ has $(\mathbf p _1;n)=(x_1,x_{2},\ldots ,x_{N-1},1;n)$ as an option. By (i.1) we have $g(\mathbf p _1;n)=n-1$. Observation 1 implies that $g(\mathbf p ;n)=0$.

• (ii) Induction step: $q\ge 1$. Assume that Facts A, B and C hold for $0\le q'\le q-1$. We take some fixed $q\ge 1$ and show that Facts A, B and C hold for q:

• (ii.1) Proof of Fact A. We proceed by induction on $\bar{s}\ge 0$. By letting $q'=q-1$ in Fact C, we have $g(\mathbf p ;qn)=g(\mathbf p ;0)$ i.e. $g(\mathbf p ;qn+\bar{s}) =g(\mathbf p ;\bar{s})$ holds for $\bar{s}=0$. Assume that $g(\mathbf p ;qn+s') =g(\mathbf p ;s')$ holds for $0\le s'< \bar{s}\le n-2$. We take some fixed $\bar{s}\ge 1$ and show that $g(\mathbf p ;qn+\bar{s}) =g(\mathbf p ;\bar{s})$:

• (ii.1.1) If $x_{N}=1$ then $g(\mathbf p _1;qn+\bar{s})=\min \{g(\mathbf p _1;qn+\bar{s}-1)+1,g(\mathbf p _0;qn+\bar{s})+1\} =\min \{\bar{s}-1, n-1\}=\bar{s}-1$ as the induction hypothesis on $s'=\bar{s}-1$ implies that $g(\mathbf p _1;qn+\bar{s}-1)=\bar{s}-2$.

• (ii.1.2) We show that $g(\mathbf p _t;qn+\bar{s})=\bar{s}$ by induction on $t\ge 2$: If $t=2$ then

  $$\begin{aligned}\begin{array}{rcl} &{}&{}g(\mathbf p _2;qn+\bar{s})\\ &{}&{}\quad =\min \{g(\mathbf p _2;qn+\bar{s}-1)+1, g(\mathbf p _0;qn+\bar{s})+1,g(\mathbf p _1;qn+\bar{s})+1\}\\ &{}&{}\quad = \min \{\bar{s}, n-1,\bar{s}\}=\bar{s}, \end{array}\end{aligned}$$

  as the induction hypothesis on $s'=\bar{s}-1$ implies that $g(\mathbf p _2;qn+\bar{s}-1)=g(\mathbf p _2;qn+s')=g(\mathbf p _2;s')=s'=\bar{s}-1$.

Assume that $g(\mathbf p _m;qn+\bar{s})=\bar{s}$ for all $2\le m<t$. We take some fixed $t\ge 3$ and show $g(\mathbf p _t;qn+\bar{s})=\bar{s}$. The induction hypothesis on $s'=\bar{s}-1$ implies that $g(\mathbf p _t;qn+\bar{s}-1)=g(\mathbf p _t;qn+s')=g(\mathbf p _t;s')=s'=\bar{s}-1$. It follows from Eq. (12) that

$$\begin{aligned}\begin{array}{rcl} &{}&{}(\mathbf p _t;qn+\bar{s})\\ &{}&{}\quad =\min (\{g(\mathbf p _t;qn+\bar{s}-1)+1, g(\mathbf p _0;qn+\bar{s})+1,g(\mathbf p _1;qn+\bar{s})+1\}\\ &{}&{}\qquad \cup \ \{g(\mathbf p _m;qn+\bar{s})+1\mid 2\le m<t\})\\ &{}&{}\quad = \min \{\bar{s}, n-1, \bar{s}, \bar{s}+1\}=\bar{s}. \end{array} \end{aligned}$$

• (ii.2) Proof of Fact B. Theorem 8(B) shows that $g(\mathbf p ;n-1) =n-2$ if $x_N=1$, or $n-1$ if $x_N=2$, or 0 if $x_N>2$. It suffices to show that $g(\mathbf p ;qn+n-1)=n-2$ if $x_N=1$, or $n-1$ if $x_N=2$, or 0 if $x_N>2$:

• (ii.2.1) If $x_N=1$ then $g(\mathbf p _1;qn+n-1)=\min \{g(\mathbf p _1;qn+n-2)+1,g(\mathbf p _0;qn+n-1)+1\}=\min \{n-2,n-1\}=n-2$ as Fact A and Theorem 8(A) show that $g(\mathbf p _1;qn+s')=g(\mathbf p _1;s')=s'-1=n-3$ where $s'=n-2$.

• (ii.2.2) If $x_N=2$ then $g(\mathbf p _2;qn+n-1)=\min \{g(\mathbf p _2;qn+n-2)+1,g(\mathbf p _0;qn+n-1)+1,g(\mathbf p _1;qn+n-1)+1\} =\min \{n-1,n-1,n-1\}=n-1$ as Fact A and Theorem 8(A) show that $g(\mathbf p _2;qn+s')=g(\mathbf p _2;s')=s'=n-2$ where $s'=n-2$; Fact B and Theorem 8(B) show that $g(\mathbf p _1;qn+s')=g(\mathbf p _1;s')=s'-1=n-2$ where $s'=n-1$.

• (ii.2.3) If $x_N>2$, the position $(\mathbf p ;qn+n-1)$ has $(\mathbf p _2;qn+n-1)$ as an option. By (ii.2.2) we have $g(\mathbf p _2;qn+n-1)=n-1$. Observation 1 implies that $g(\mathbf p ;qn+n-1)=0$.

• (ii.3) Proof of Fact C. Theorem 2 shows us that $g(\mathbf p ;0)=n-1$ if $x_N=1$, or 0 if $x_N>1$. It suffices to show that $g(\mathbf p ;qn+n)=n-1$ if $x_N=1$, or 0 if $x_N>1$.

• (ii.3.1) If $x_N=1$ then $g(\mathbf p _1;qn+n)=\min \{g(\mathbf p _1;qn+n-1)+1,g(\mathbf p _0;qn+n)+1\}=\min \{n-1,n-1\}=n-1$ as Fact B and Theorem 8(B) show that $g(\mathbf p _1;qn+n-1)=g((\mathbf p _1;s')=s'-1=n-2$ where $s'=n-1$.

• (ii.3.2) If $x_N>1$, the position $(\mathbf p ;qn+n)$ has $(\mathbf p _1;qn+n)$ as an option. By (ii.3.1) we have $g(\mathbf p _1;qn+n)=n-1$. Observation 1 gives $g(\mathbf p ;qn+n)=0$, as required. $\square$

4.3 Game values of MLNim$^{(s)}(n+d,n)$ where $n\ge s+d+3$

In this subsection we consider MLNim$^{(s)}(N,n$) where $s+d+3\le n\le N$. Let $d=N-n$ and rewrite MLNim$^{(s)}(N,n$) as MLNim$^{(s)}(n+d,n$) where $n\ge s+d+3$ and $d\ge 0$. Theorem 10 gives the game values of MLNim$^{(s)}(n+d,n)$ for all integers $d\ge 0$ and $n\ge s+d+3$. It turns out that the game values of MLNim$^{(s)}(n+d,n$) only have two values, $s+d$ and $s+d+1$, which depend only on whether $x_{n-1}=1$.

Theorem 10

Consider MLNim$^{(s)}(n+d,n)$ and $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{n+d};s)$. If $n\ge s+d+3$ then for all integers $s\ge 0$ and $d\ge 0$,

$$\begin{aligned} g(\mathbf p ;s)=d+s+\delta =\left\{ \begin{array}{ll} s+d, &{}\quad \text{ if } x_{n-1}=1,\\ s+d+1, &{}\quad \text{ if } x_{n-1}>1.\\ \end{array}\right. \end{aligned}$$

(19)

In particular, $g(\mathbf p ;s)=g(\mathbf p ;0)+s$. In other words, if $n\ge s+d+3$ then the game value of a position $(\mathbf p ;s)$ is equal to the sum of the game value of the position $(\mathbf p ;0)$ and the number s of passes.

Proof

We proceed by induction on $s\ge 0$. Theorem 3 shows that $g(\mathbf p ;0)=d+\delta$ i.e. Theorem 10 holds for $s=0$. Assume that Theorem 10 holds for all $0\le s'\le s-1$. We take some fixed $s\ge 1$ and show that for any $t\ge 1$, we have $g(\mathbf p _t;s)=d+s+\delta$ by induction on $d\ge 0$:

(i) Base case: $d=0$. Now $(\mathbf p _t;s)=(x_{1},x_{2},\ldots ,x_{n-1},t;s)$ has the following options:

• $(\mathbf p _t;s-1)$ with $s'=s-1$ passes. The induction hypothesis on $s'=s-1$ implies $g(\mathbf p _t;s-1)=s'+\delta =s-1+\delta$.

• $(\mathbf p _0;s)=(x_1,x_{2},\ldots ,x_{n-1};s)$ with $N'=n-1$ piles. Theorem 8(A) gives $g(\mathbf p _0;s)=s-1+\delta$ as $n=N'+1$ and $s\le n-3$.

• $(\mathbf p _m;s)=(x_1,x_{2},\ldots ,,x_{n-1},m;s)$, $1\le m<t$, with $N=n$ piles.

We see that $g(\mathbf p _t;s-1)=g(\mathbf p _0;s)=s-1+\delta$. It follows from Eq. (12) that

$$\begin{aligned} \begin{array}{rcl} &{}&{}g(\mathbf p _t;s)\\ &{}&{}\quad =\min (\{g(\mathbf p _t;s-1)+1,g(\mathbf p _0;s)+1\}\cup \{g(\mathbf p _m;s)+1\mid 1\le m<t\})\\ &{}&{}\quad =\min (\{s+\delta \}\cup \{g(\mathbf p _m;s)+1\mid 1\le m<t\}). \end{array} \end{aligned}$$

(20)

We claim that $g(\mathbf p _t;s)=s+\delta$ by induction on $t\ge 1$: For $t=1$, Eq. (20) gives $g(\mathbf p _1;s)=\min \{s+\delta \}=s+\delta$. Assume that $g(\mathbf p _m;s)=s+\delta$ for all $1\le m<t$. It follows from Eq. (20) that $g(\mathbf p _t;s)=\min \{s+\delta ,s+\delta +1\}=s+\delta$.

• (ii) Induction step: $d\ge 1$. Assume that Theorem 10 holds for $0\le d'\le d-1$. We show that Theorem 10 holds for d. Now $(\mathbf p _t;s)=(x_{1},x_{2},\ldots ,x_{n+d-1},t;s)$ has the following options:

  • $(\mathbf p _t;s-1)$ with $N=n+d$ piles and $s'=s-1$ passes. The induction hypothesis on $s'=s-1$ implies $g(\mathbf p _t;s-1)=d+s'+\delta =d+s-1+\delta$.

  • $(\mathbf p _0;s)=(x_1,x_{2},\ldots ,x_{n+d-1};s)$ with $N'=n+d'$ piles where $d'=d-1$, and s passes. The induction hypothesis on $d'=d-1$ means that $g(\mathbf p _0;s)=d'+s+\delta =d+s-1+\delta$.

  • $(\mathbf p _m;s)=(x_1,x_{2},\ldots ,,x_{n+d-1},m;s)$, $1\le m<t$, with $N=n+d$ piles and s passes.

We see that $g(\mathbf p _t;s-1)=g(\mathbf p _0;s)=d+s-1+\delta$. Equation (12) means that $g(\mathbf p _t;s)=\min (\{d+s+\delta \}\cup \{g(\mathbf p _m;s)+1\mid 1\le m<t\})$. Similar to (i), by induction on $t\ge 1$ we have $g(\mathbf p _t;s)=d+s+\delta$, as required.

Theorem 3 gives $g(\mathbf p ;0)=d+\delta$, so $g(\mathbf p ;s)=d+s+\delta =g(\mathbf p ;0)+s$. $\square$

4.4 Game values of MLNim$^{(s)}(n+d,n)$ where $n=s+d+2$

In this subsection we consider MLNim$^{(s)}(n+d,n)$ where $n=s+d+2$. Theorem 11 gives the game values of MLNim$^{(s)}(n+d,n$) for $n=s+d+2\ge 3$. It turns out that the game values of MLNim$^{(s)}(n+d,n$) have three values, $s+d$, $s+d+1$ and $s+d+2$, which depend on $x_{n-1}$ and $x_{n+d}$.

Theorem 11

Consider MLNim$^{(s)}(n+d,n)$ and $\mathbf p =(x_{1},x_{2},\ldots ,x_{n+d})$. If $n=s+d+2$ then for any $s\ge 0$ and $d\ge 1$,

$$\begin{aligned} g(\mathbf p ;s)=\left\{ \begin{array}{ll} d+s(=n-2), &{} \quad \text{ if } x_{n-1}=1,\\ d+s+1(=n-1), &{}\quad \text{ if } x_{n-1}>1 \text{ and } x_{n+d}=1,\\ d+s+2(=0), &{}\quad \text{ if } x_{n-1}>1 \text{ and } x_{n+d}>1.\\ \end{array}\right. \end{aligned}$$

(21)

In particular, $g(\mathbf p ;s)=g(\mathbf p ;0)+s$. In other words, if $n=s+d+2$ then the game value of a position $(\mathbf p ;s)$ is equal to the sum of the game value of the position $(\mathbf p ;0)$ and the number s of passes.

Proof

Theorem 4 implies that Theorem 11 holds for $s=0$. For a fixed $s\ge 1$, $(\mathbf p _t;s)$ has the following options:

• $(\mathbf p _t;s-1)=(x_1,x_2,\ldots , x_{n+d-1},t;s-1)$ with $s'=s-1$ passes and $n=s+d+2=s'+d+3$. Theorem 10 implies that $g(\mathbf p _t;s-1)=g(\mathbf p _t;s')=s'+d+\delta =d+s-1+\delta$. In other words, $g(\mathbf p _t;s-1)=d+s-1$ if $x_{n-1}=1$, or $d+s$ if $x_{n-1}>1$.

• $(\mathbf p _0;s)=(x_1,x_{2},\ldots ,x_{n+d-1};s)$ with $N'=n+d'$ piles where $d'=d-1\ge 0$ and $n=s+d+2=s+d'+3$. Theorem 10 gives $g(\mathbf p _0;s)=s+d'+\delta =d+s-1+\delta$. In other words, $g(\mathbf p _0;s)=s+d-1$ if $x_{n-1}=1$, or $d+s$ if $x_{n-1}>1$.

• $(\mathbf p _m;s)=(x_1,x_{2},\ldots ,,x_{n+d-1},m;s)$, $1\le m<t$, with $n=s+d+2$.

  • (i) We consider $x_{n-1}=1$ and show that $g(\mathbf p _t;s)=d+s$ by induction on $t\ge 1$:

If $t=1$, $(\mathbf p _1;s)$ only has two options $(\mathbf p _1;s-1)$ and $(\mathbf p _0;s)$. Hence $g(\mathbf p _1;s)=\min \{g(\mathbf p _1;s-1)+1,g(\mathbf p _0;s)+1\}=\min \{d+s,d+s\}=d+s$. Assume that $g(\mathbf p _m;s)=d+s$ for all $1\le m<t$. It follows from Eq. (12) that $g(\mathbf p _t;s)=\min (\{g(\mathbf p _t;s-1)+1,g(\mathbf p _0;s)+1\}\cup \{g(\mathbf p _m;s)+1\mid 1\le m<t\})=\min \{d+s, d+s, d+s+1\}=d+s=n-2$.

• (ii) We consider $x_{n-1}>1$ and $x_{n+d}=1$. Let $t=x_{n+d}=1$. Now $(\mathbf p ;s)=(\mathbf p _1;s)$ only has two options $(\mathbf p _1;s-1)$ and $(\mathbf p _0;s)$. Hence $g(\mathbf p ;s)=\min \{g(\mathbf p _1;s-1)+1,g(\mathbf p _0;s)+1\}=\min \{d+s+1,d+s+1\}=d+s+1=n-1$.

• (iii) We consider $x_{n-1}>1$ and $x_{n+d}>1$. Let $t=x_{n+d}$. Now $(\mathbf p ;s)=(\mathbf p _t;s)$ has $(\mathbf p _1;s)$ as an option. By (ii) we have $g(\mathbf p _1;s)=d+s+1=n-1$. Observation 1 implies that $g(\mathbf p ;s)=0$, as required. $\square$

4.5 Game values of MLNim$^{(s)}(n+d,n)$ where $n=s+d+1$

In this subsection we consider MLNim$^{(s)}(n+d,n)$ where $n=s+d+1$. Theorem 12 gives the game values of MLNim$^{(s)}(n+d,n)$ for $n=s+d+1\ge 3$. The game values of MLNim$^{(s)}(n+d,n$) divide into two parts: $d=0$ or $d\ge 1$. This fact yields that $g(\mathbf p ;s)=g(\mathbf p ;0)+s$ does not hold for the case $n=s+d+1$.

Theorem 12

Consider MLNim$^{(s)}(n+d,n)$ and $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{n+d};s)$. If $n=s+d+1\ge 3$ then

• (A) for $d=0$ i.e. $s=n-1\ge 2$, we have

  $$\begin{aligned} g(\mathbf p ;s)=\left\{ \begin{array}{ll} s(=n-1), &{} \text{ if } x_{n-1}=1 \text{ and } x_{n}=1,\\ s+1(=0), &{} \text{ if } (x_{n-1}=1 \text{ and } x_{n}>1)\\ &{}\ \ \ \text{ or } (x_{n-1}>2 \text{ and } x_{n}=1)\\ &{}\ \ \ \text{ or } (x_{n-1}=2),\\ s+2(=1), &{} \text{ if } x_{n-1}>2 \text{ and } x_{n}>1.\\ \end{array}\right. \end{aligned}$$

  (22)

• (B) for $d\ge 1$ i.e. $s=n-d-1\in \{1,2,\ldots ,n-2\}$, we have

  $$\begin{aligned} g(\mathbf p ;s)=\left\{ \begin{array}{ll} d+s(=n-1), &{} \text{ if } x_{n-1}=1 \text{ and } x_{n+d}=1 ,\\ d+s+1(=0), &{} \text{ if } (x_{n-1}=1 \text{ and } x_{n+d}>1)\\ &{}\ \ \ \text{ or } (x_{n-1}>1 \text{ and } x_{n+d-1}=1)\\ &{}\ \ \ \text{ or } (x_{n-1}>1 \text{ and } x_{n+d-1}>1 \text{ and } x_{n+d}=1),\\ d+s+2(=1), &{} \text{ if } x_{n-1}>1 \text{ and } x_{n+d-1}>1 \text{ and } x_{n+d}>1.\\ \end{array}\right. \end{aligned}$$

  (23)

Proof

• (A) We consider $d=0$ and $(\mathbf p ;s)=(x_1,x_2,\ldots , x_{n-1},x_n;s)$.

• (A.1) If $x_{n-1}=1$ and $x_{n}=1$, the position $(\mathbf p ;s)=(\mathbf p _1;s)$ only has two options $(\mathbf p _1;s-1)$ and $(\mathbf p _0;s)$. Theorem 11 gives $g(\mathbf p _1;s-1)=s'+d=s-1$ as $n=s+d+1=s'+d+2$ (where $s'=s-1\ge 1$). Theorem 8 gives $g(\mathbf p _0;s)=s-1$ as $n=N'+1$ and $s=n-1$. Hence $g(\mathbf p ;s)=\min \{g(\mathbf p _1;s-1)+1,g(\mathbf p _0;s)+1\}=\min \{s,s\}=s=n-1$.

• (A.2) If $x_{n-1}=1$ and $x_{n}>1$, the position $(\mathbf p ;s)$ has $(\mathbf p _1;s)$ as an option. By (A.1) we have $g(\mathbf p _1;s)=n-1$. Observation 1 implies that $g(\mathbf p ;s)=0$.

• (A.3) If $x_{n-1}>2$ and $x_{n}=1$, $(\mathbf p ;s)$ has $(\mathbf p ;s-1)$ as an option. Theorem 11 gives $g(\mathbf p ;s-1)=s+d=s=n-1$. Observation 1 implies that $g(\mathbf p ;s)=0$.

• (A.4) If $x_{n-1}=2$, $(\mathbf p ;s)$ has $(\mathbf p _0;s)$ as an option. Theorem 8 gives $g(\mathbf p _0;s)=s=n-1$ as $n=N'+1$ and $s=n-1$. Observation 1 implies that $g(\mathbf p ;s)=0$.

• (A.5) We consider $x_{n-1}>2$ and $x_{n}>1$. Let $\mathbf p _t=(x_1,x_2,\ldots , x_{n-1},t)$ where $t=x_n>1$. Theorem 11 gives $g(\mathbf p _t;s-1)=s-1$, and Theorem 8 gives $g(\mathbf p _0;s)=s+1=0$ as $n=N'+1$ and $s=n-1$, and (A.3) gives $g(\mathbf p _1;s)=0$.

  We will show that $g(\mathbf p _t;s)=1$ by induction on $t=x_n\ge 2$: If $t=2$, $(\mathbf p _2;s)$ only has three options $(\mathbf p _2;s-1)$, $(\mathbf p _0;s)$ and $(\mathbf p _1;s)$. Hence $g(\mathbf p _2;s)=\min \{g(\mathbf p _2;s-1)+1,g(\mathbf p _0;s)+1,g(\mathbf p _1;s)+1\}=\min \{s,1,1\}=1$. Assume that $g(\mathbf p _m;s)=1$ for any $2\le m<t$. It follows from Eq. (12) that $g(\mathbf p _t;s)=\min (\{g(\mathbf p _t;s-1)+1,g(\mathbf p _0;s)+1,g(\mathbf p _1;s)+1\}\cup \{g(\mathbf p _m;s)+1\mid 2\le m<t\})=\min \{s, 1, 1,2\}=1$.

• (B) If $d\ge 1$ then $s=n-d-1\in \{1,2,\ldots ,n-2\}$ and $n=s+d+1\ge 3$. Let $(\mathbf p ;s)=(x_1,x_2,\ldots , x_{n+d-1}, x_{n+d};s)$.

• (B.1) $x_{n-1}=1$ and $x_{n+d}=1$. Now $\mathbf p =\mathbf p _1$. Theorem 11 gives $g(\mathbf p _1;s-1)=d+s'=d+s-1$ as $n=s+d+1=s'+d+2$ (where $s'=s-1\ge 0$). Theorem 11 means that $g(\mathbf p _0;s)=d'+s=d+s-1$ as $n=s+d+1=s+d'+2$ (where $d'=d-1\ge 0$). The position $(\mathbf p ;s)$ only has two options $(\mathbf p _1;s-1)$ and $(\mathbf p _0;s)$. Hence $g(\mathbf p ;s)=\min \{g(\mathbf p _1;s-1)+1,g(\mathbf p _0;s)+1\}=\min \{d+s,d+s\}=d+s$.

• (B.2) $x_{n-1}=1$ and $x_{n+d}>1$. The position $(\mathbf p ;s)$ has $(\mathbf p _1;s)$ as an option. By (B.1) we have $g(\mathbf p _1;s)=d+s=n-1$. Observation 1 implies that $g(\mathbf p ;s)=0$.

• (B.3) $x_{n-1}>1$ and $x_{n+d-1}=1$. Now $(\mathbf p ;s)$ has $(\mathbf p _0;s)$ as an option. Theorem 11 gives $g(\mathbf p _0;s)=d'+s+1=d+s=n-1$ as $n=s+d+1=s+d'+2$ (where $d'=d-1\ge 0$). Observation 1 implies that $g(\mathbf p ;s)=0$.

• (B.4) $x_{n-1}>1$ and $x_{n+d-1}>1$ and $x_{n+d}=1$. Now $\mathbf p =\mathbf p _1$ and $(\mathbf p _1;s)$ has $(\mathbf p _1;s-1)$ as an option. Theorem 11 gives $g(\mathbf p _1;s-1)=d+s'+1=d+s=n-1$ as $n=s+d+1=s'+d+2$ (where $s'=s-1$). Observation 1 implies that $g(\mathbf p ;s)=0$.

• (B.5) $x_{n-1}>1$ and $x_{n+d-1}>1$ and $x_{n+d}>1$. Let $\mathbf p _t=(x_1,\ldots , x_{n+d-1},t)$ where $t=x_{n+d}>1$. Theorem 11 gives $g(\mathbf p _t;s-1)=d+s+1(=0)$ as $n=s+d+1=s'+d+2$ (where $s'=s-1\ge 0$). Theorem 11 gives $g(\mathbf p _0;s)=0$ as $n=s+d+1=s+d'+2$ (where $d'=d-1\ge 0$). By (B.4) we have $g(\mathbf p _1;s)=0$. We show that $g(\mathbf p _t;s)=1$ by induction on $t=x_{n+d}\ge 2$:

  If $t=2$, $(\mathbf p _2;s)$ only has three options $(\mathbf p _2;s-1)$, $(\mathbf p _0;s)$ and $(\mathbf p _1;s)$. Hence $g(\mathbf p _2;s)=\min \{g(\mathbf p _2;s-1)+1,g(\mathbf p _0;s)+1,g(\mathbf p _1;s)+1\}=\min \{1,1,1\}=1$. Assume that $g(\mathbf p _m;s)=1$ for any $2\le m<t$. It follows from Eq. (12) that $g(\mathbf p _t;s)=\min (\{g(\mathbf p _t;s-1)+1,g(\mathbf p _0;s)+1,g(\mathbf p _1;s)+1\}\cup \{g(\mathbf p _m;s)+1\mid 2\le m<t\})=\min \{1, 1, 1, 2\}=1$. $\square$

5 Conclusions

We have investigated the games MLNim$^{(s)}(N,n)$ for all integers $N\ge 1$ and $n\ge 3$ and $s\ge 0$. Let $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{N};s)$ with $x_{i}\ge 1$ for all $i\in \{1,2,\ldots ,N\}$ be any position of MLNim$^{(s)}(N,n)$. The aim of the present paper is to determine the game values $g(\mathbf p ;s)$ for all integers $N\ge 1$ and $n\ge 3$ and $s\ge 0$. Here is a summary of our findings:

• (i) $n>N+1$. The game values $g(\mathbf p ;s)$ are completely determined for any $s\ge 0$ and $N\ge 1$. Theorems 1 and 7 show that the game value $g(\mathbf p ;s)=g(\mathbf p ;0)=N$ i.e. the game value of a position $(\mathbf p ;s)$ is equal to the number of the piles of $\mathbf p$. In other words, the game value $g(\mathbf p ;s)$ do not depend on the parameters $x_i$ and the total number s of passes.

• (ii) $n=N+1\ge 3$. Theorem 9 gives $g(\mathbf p ;s)=g(\mathbf p ;\bar{s})$ for all integers $s\ge 0$ and $N\ge 2$, where $\bar{s}=s \mod n$. Theorem 8 determines $g(\mathbf p ;\bar{s})$ by distinguishing $\bar{s}\in \{0,1,\ldots ,n-2\}$ or $\bar{s}=n-1$.

• (iii) $3\le n\le N$. Let $d=N-n\ge 0$ and $(\mathbf p ;s)=(x_{1},x_{2},\ldots ,x_{n+d};s)$ be any position of MLNim$^{(s)}(n+d,n)$. If $n\ge s+d+3$, Theorem 10 shows that $g(\mathbf p ;s)=g(\mathbf p ;0)+s\in \{s+d,s+d+1\}$ for all integers $d\ge 0$ and $s\ge 0$. If $n=s+d+2\ge 3$, Theorem 11 shows that $g(\mathbf p ;s)=g(\mathbf p ;0)+s\in \{n-2,n-1,0\}$ for all integers $d\ge 1$ and $s\ge 0$. The case $n=s+d+1$ is more complicated: Theorem 12 determines $g(\mathbf p ;s)\in \{n-1,0,1\}$, but we have to distinguish two subcases $d=0$ or $d\ge 1$. We see that $g(\mathbf p ;s)=g(\mathbf p ;0)+s$ does not hold for the case $n=s+d+1$.

6 Future work

Unfortunately, we cannot give the game values $g(\mathbf p ;0)$ for the case $3\le n\le d$ by explicit formulas. Theorem 6 gives the game values $g(\mathbf p ;0)$ where $n=d=3$. Remark 3 in Sect. 3.3 explains partly why determining the game values $g(\mathbf p ;0)$ for the case $3\le n\le d$ is more difficult. Can we give more results on the game values $g(\mathbf p ;s)$ of MLNim$^{(s)}(n+d,n)$ for the case $3\le n\le d$?

All results given by the present paper is based on the assumption that the standard alliance matrix is adopted. If another alliance matrix is adopted, what can be said about the game values of MLNim$^{(s)}(N,n)$ for the cases $n>N+1$, $n=N+1$ or $n\le N$?

This paper is devoted to Last Nim. In deed, there are many impartial combinatorial games: End-Nim, Wythoff’s game, (s, t)-Wythoff’s game, Wythoff-like games, Subtraction games, Small Nim, etc. Since multi-player games are not well understood or analyzed currently, can we extend some 2-person games to the corresponding N-person games ($N>2$)?