# Some Remarks on End-Nim

Authors: Grant Cairns; Nhan Bao Ho
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

We reexamine Albert and Nowakowski's variation on
the game of Nim, calledEnd-Nim, in which the players may only
remove coins from the leftmost or rightmost piles. We reformulate
Albert and Nowakowski's solution to this game. We examine its
misère version and a further variant where the winner is the player
who reduces the game to a single pile; we call this Loop-End-Nim.
We show that the three games, End-Nim, misère-End-Nim, and
Loop-End-Nim, all have the same losing positions, except for the
positions where all the piles are of equal size. We also give some
partial results concerning the higher Sprague-Grundy values of the
three games.


---

## Body

## 1. Introduction

Considerk piles of coins, in a row. In the classic game of Nim, the two players move alternately, each removing a nonzero number of coins from a single pile; the winner is the player to remove the last coin [1]. The well-known solution to Nim, using Sprague-Grundy values, is both elegant and complete [1].In [2], Albert and Nowakowski analysed a variation of Nim; they called End-Nim in which the players may only remove coins from either of the end piles. This game had been posed as problem  23 in [3], where it was called Burning the Candle at Both Ends. Albert and Nowakowski gave a solution to this game, which we recall below, but the Sprague-Grundy values seem particularly complicated and have not yet been determined. In this paper, we examine the misère version of End-Nim, and a further variant where the winner is the player who reduces the game to a single pile; we call this Loop-End-Nim, where “Loop" stands for “leave only one pile’’. While Loop-End-Nim is not strictly speaking a misère game, it has something of the nature of a misère game. We show that the three games, End-Nim, misère-End-Nim and Loop-End-Nim, all have the same losing positions (i.e., 𝒫-positions), except for the positions where all the piles are of equal size. Thus, like the misère form of Nim, the games misère-End-Nim and Loop-End-Nim can be played with the same strategy as End-Nim except that consideration has to be given to the exceptional positions.The𝒫-positions are the positions with Sprague-Grundy value 0. We also give some partial results concerning the positions of higher Sprague-Grundy values of the three games. It should be mentioned here that the Sprague-Grundy function plays no role in the strategy of playing End-Nim, and it is well known that, in their usual form, they are inappropriate for studying misère games [4]. Our interest here is simply to provide further indications as to the complexity of the Sprague-Grundy function for End-Nim.The positions in these games will be denoted by the corresponding sequences of coin sizes:(a1,…,ak). The assumption is that the pile sizes ai are all nonempty. By reversing A=(a1,…,ak) if necessary, we may assume that a1≤ak.


## 2. The Losing Positions

In Albert and Nowakowski’s entertaining paper [2], their solution to End-Nim is given in pictorial form, involving a matrix of arrows with asterisks and bullets. We will present it in an alternate form. First, we introduce some notation, employing an idea similar to the one used in [5]. For a position A=(a1,a2,…,ak), we define l(A) to be the largest natural number i for which a1=⋯=ai-1≤ai. Similarly, for a position A=(a1,a2,…,ak) for which the ai are not all equal, we define r(A) to be the largest natural number j for which ak-j+1≥ak-j+2=⋯=ak. If a1=⋯=ak, we set r(A)=0. Then Albert and Nowakowski’s solution can be rephrased as follows.Theorem 2.1.
In End-Nim, a positionA=(a1,a2,…,ak) with a1≤ak is a 𝒫-position if and only if one of the following conditions holds:(a)
a1=ak, and furthermore, l(A)+r(A) is even,(b)
ak=a1+1 and, furthermore, l(A) is odd and r(A) is even.Condition (a) corresponds to the following 8 hieroglyphs of Albert and Nowakowski.Condition (b) corresponds to the following 4 pictures.In these pictures, ifa1=⋯=ai-1≠ai, then the * symbol lies in the first (resp. second) column if i is even (resp. odd), and it is adjacent to ↑ (resp. ↓) if ai-1<ai (resp. ai-1>ai). The conventions for • are defined analogously, for the right hand end. Clearly, our formulation of the result is more succinct, while Albert and Nowakowski’s presentation is more graphic.To give the solution to misère-End-Nim, we modify slightly the definition ofr. We set rm(A)=r(A) except when a1=⋯=ak=1, in which case we set rm(A)=1. Then we have the following.Theorem 2.2.
In misère-End-Nim, a positionA=(a1,a2,…,ak) with a1≤ak is a 𝒫-position if and only if one of the following holds:(a)
a1=ak and, furthermore, l(A)+rm(A) is even,(b)
ak=a1+1 and, furthermore, l(A) is odd and rm(A) is even.We postpone the proof until the next section. Let us now describe the solution for Loop-End-Nim. Once again, we modify ther function. We set ro(A)=r(A) except when a1=⋯=ak, in which case we set ro(A)=1. Then we have the following.Theorem 2.3.
In Loop-End-Nim, a positionA=(a1,a2,…,ak) with a1≤ak is a 𝒫-position if and only if one of the following holds:(a)
a1=ak and, furthermore, l(A)+ro(A) is even,(b)
ak=a1+1 and, furthermore, l(A) is odd and ro(A) is even.As an immediate consequence of the above three results, we have the following.Corollary 2.4.
The three games, End-Nim, misère-End-Nim, and Loop-End-Nim have the same𝒫-positions of the form A=(a1,a2,…,ak), where the ai are not all equal. If A=(a1,a2,…,ak) where a1=⋯=ak, then(a)
A is a 𝒫-position of End-Nim if and only if k is even,(b)
A is a 𝒫-position of misère-End-Nim if and only if k is even and a1>1, or k is odd and a1=1,(c)
A is a 𝒫-position of Loop-End-Nim if and only if k is odd.


## 3. Proof of Theorems2.2 and 2.3

Proof of Theorem2.2.
We say that a position verifying condition (a) or (b) of Theorem2.2 is a 0-position. We must prove two facts:(1)
from every positionA that is not a 0-position, there is a move to a 0-position,(2)
there is no move from a 0-position to a 0-position.
(1) LetA=(a1,a2,…,ak) be a position that is not a 0-position. First suppose that A is a 𝒫-position in End-Nim. By Theorem 2.1, a1=⋯=ak=1 and k is even. Then we have the move A→(a1,a2,…,ak-1), which is a 0-position. Now suppose that A is not a 𝒫-position in End-Nim. Then there is a move A→B, where B=(b1,…,bn) is a 𝒫-position in End-Nim. If B is not a 0-position, then by Theorem 2.1, b1=⋯=bn=1 and n is even. Hence either k=n and a1=⋯=ak-1<ak, or k=n+1 and a1=⋯=ak-1≤ak. In the former case, we have the move A→(a1,a2,…,ak-1), which is a 0-position. In the latter case, since A is not a 0-position, ak-1<ak and we have the move A→(a1,a2,…,ak-1,1), which is a 0-position.
(2) LetA→B be a move between two 0-positions, where A=(a1,a2,…,ak) with a1≤ak and B=(b1,…,bn). First suppose that A is not a 𝒫-position in End-Nim. So a1=⋯=ak=1 and k is odd. But this is a contraction, since necessarily B=(a1,a2,…,ak-1), which is not a 0-position. So we may suppose that A is a 𝒫-position in End-Nim. Therefore, B is not a 𝒫-position in End-Nim. Hence b1=⋯=bn=1 and n is odd. Thus, either k=n and a1=⋯=ak-1<ak, or k=n+1 and a1=⋯=ak-1≤ak. In the former case, rm(A)=1, which is impossible as a1<ak and A is a 0-position. In the latter case, l(A) is even and so, as A is a 0-position, rm(A) is also even. Hence ak=1. But then a1=⋯=ak=1, which is impossible as k is even and A is a 0-position. This completes the proof.The following argument is modelled closely on the proof we have just given.Proof of Theorem2.3.
We say that a position verifying condition (a) or (b) of Theorem2.3 is a 0-position. We must prove two facts:(1)
from every positionA that is not a 0-position, there is a move to a 0-position,(2)
there is no move from a 0-position to a 0-position.
(1) LetA=(a1,a2,…,ak) be a position that is not a 0-position. First suppose that A is a 𝒫-position in End-Nim. By Theorem 2.1, a1=⋯=ak and k is even. Then we have the move A→(a1,a2,…,ak-1), which is a 0-position. Now suppose that A is not a 𝒫-position in End-Nim. Then there is a move A→B, where B=(b1,…,bn) is a 𝒫-position in End-Nim. If B is not a 0-position, then by Theorem 2.1, b1=⋯=bn and n is even. Hence either k=n and a1=⋯=ak-1<ak, or k=n+1. In the former case, we have the move A→(a1,a2,…,ak-1), which is a 0-position. In the latter case, k is odd and at first sight there are two possibilities:
(a)
a1<a2=a3=⋯=ak. Here we have the move A→C=(a1,a2,…,ak-1,a1), which is a 0-position since l(C)+ro(C)=4.(b)
a1=a2=⋯=ak-1≤ak. Note that as A is not a 0-position, ak-1<ak. Here we have the move A→(a1,a2,…,ak-1,ak-1), which is a 0-position.
(2) LetA→B be a move between two 0-positions, where A=(a1,a2,…,ak) with a1≤ak and B=(b1,…,bn). First suppose that A is not a 𝒫-position in End-Nim. So a1=⋯=ak and k is odd. Then either n=k,b1<a1 and b2=b3=⋯=bk=ak, in which case l(B)=2, or n=k-1 and b1=b2=⋯=bk-1. But in both cases, B is not a 0-position, which gives a contradiction. So we may suppose that A is a 𝒫-position in End-Nim. Therefore, B is not a 𝒫-position in End-Nim. Hence, b1=⋯=bn and n is odd. Thus, either k=n and a1=…=ak-1<ak, or k=n+1. In the former case, ro(A)=1, which is impossible as a1<ak and A is a 0-position. In the latter case, k is even and at first sight there are two possibilities:
(a)
a1<a2=a3=⋯=ak. Here, ro(A)=k-1=n, which is odd, contrary to the assumption that A is a 0-position.(b)
a1=a2=⋯=ak-1≤ak. Since A is a 0-position and k is even, we have ak-1<ak. But then ro(A)=1, again contracting the assumption that A is a 0-position.


## 4. Sprague-Grundy Values for Games with Two Piles

Let us denote the Sprague-Grundy function for the games End-Nim, misère-End-Nim, and Loop-End-Nim by𝒢,𝒢m,𝒢o, respectively. First observe that End-Nim with two piles is the same as Nim with two piles. So we have 𝒢(a,b)=a⊕b, where ⊕ denotes Nim addition. The situation regarding Loop-End-Nim is also very simple.Proposition 4.1.
In Loop-End-Nim,𝒢o(a,b)=((a-1)⊕(b-1))+1, for all a,b>0.Proof.
We will prove that𝒢o(a,b)=𝒢(a-1,b-1)+1 by induction on a+b. Clearly 𝒢o(1,1)=1=𝒢(0,0)+1. Suppose a,b>0. Then by induction
(4.1)Go(a,b)=Mex({Go(a′,b):0≤a′<a}∪{Go(a,b′):0≤b′<b})=Mex({0}∪{Go(a′,b):1≤a′<a}∪{Go(a,b′):1≤b′<b})=Mex({0}∪{G(a′-1,b-1)+1:1≤a′<a}∪{G(a-1,b′-1)+1:1≤b′<b})=Mex({G(a′-1,b-1):1≤a′<a}∪{G(a-1,b′-1):1≤b′<b})+1=G(a-1,b-1)+1.The situation concerning misère-End-Nim seems to be considerably more complicated. Indeed, as far as we are aware, even for two piles, where the game is just misère Nim, the Sprague-Grundy function has not yet been determined! We have only been able to obtain very partial information. From Theorem2.2, a position A=(a,b) has Sprague-Grundy value 0 if and only if a=b≠1. We also have the following.Proposition 4.2.
In the misère-End-Nim, a positionA=(a,b) with a≤b has Sprague-Grundy value 1 if and only if either a=b=1 or a≥3 is odd and b=a+1.We omit the proof of the above proposition; it is simple and straightforward.


## 5. Sprague-Grundy Values for Games with Three Piles

As we saw in Section2, in End-Nim with three piles, a position A=(a1,a2,a3) is a 𝒫-position if and only if it is symmetrical but not constant; that is, a3=a1 and a2≠a1. The 𝒫-positions of misère-End-Nim comprise those of End-Nim, as well as (1,1,1). The 𝒫-positions of Loop-End-Nim comprise those of End-Nim, as well as the constant positions (a,a,a), with a≥1. For the positions of Sprague-Grundy value 1, we have the following three results.Theorem 5.1.
In End-Nim, a positionA=(a1,a2,a3) with a1≤a3 has Sprague-Grundy value 1 if and only if one of the following three conditions holds(a)
A=(1,1,1),(b)
a3=a1+1 and either
(i)
a1 is even and a2<a1 or(ii)
a1 is odd and a2>a1 and a2≠a1+2,(c)
a3=a1+2 and a1 is odd and a2=a3.Theorem 5.2.
In misère-End-Nim, a positionA=(a1,a2,a3) with a1≤a3 has Sprague-Grundy value 1 if and only if one of the following three conditions holds(a)
A=(1,2,2)(b)
a1=a2=a3≥3,(c)
a3=a1+1 and either
(i)
a1 is even and a2=1 or(ii)
a1 is odd and either 2≤a2<a1 or a2>a3.Theorem 5.3.
In Loop-End-Nim, a positionA=(a1,a2,a3) with a1≤a3 has Sprague-Grundy value 1 if and only if one of the following two conditions holds(a)
a3=a1+1 and either
(i)
a1 is even and a2<a1 or(ii)
a1 is odd and a2>a3.(b)
a3=a1+2 and a1 is odd, a2=a1+1.We provide a proof of Theorem5.1 in the next section. The proof is simple and straightforward, but rather long. We omit the proofs of Theorems 5.2 and 5.3 which can be established in the same manner. We also provide the following result without proof. It shows that it is unlikely that there is a simple formula for the Sprague-Grundy function for End-Nim.Theorem 5.4.
In End-Nim, a positionA=(a1,a2,a3) with a1≤a3 has Sprague-Grundy value 2 if and only if one of the following conditions holds, where the congruences are all modulo 4:(a)
a1=a2=a3≥2,a1≡1,2,(b)
a3=a1+1 and either
(i)
A=(1,1,2)(ii)
a1≡2,a2=a3 or(iii)
a1 is odd, a1≥7,5≤a2≤a1-1,a2≡1,2, except for a1≡3 where a2≠a1-2.(c)
a3=a1+2 and either
(i)
a1≡0,a2≤a1-1 and if a2≥5 then a2≡0,3, or(ii)
a1≡1 and either
(I)
A=(1,2,3),(II)
a2≥a1+3, or(III)
a2≤a1-1 and if a2≥5 then a2≡0,3,(iii)
a1≡2 and either a2=a1-1≥5 or a2≥a1+2,a2≠a1+4.(d)
a3=a1+3, a1≡2 and a2=a1+4.


## 6. Proof of Theorem5.1

We say that a position is a1-position if it has the form (a1,a2) with Sprague-Grundy value 1, or the form (a1,a2,a3) verifying condition (a), (b), or (c) of Theorem 5.1; in the latter case we say A is of type (a), (b), or (c), respectively. We must prove two properties:(1)
there is no move from a 1-position to a 1-position,(2)
from every position that is not a 0-position or a 1-position, there is a move to a 1-position.To establish the first property, we suppose thatA=(a1,a2,a3) is a 1-position. If (x,y) has Sprague-Grundy value 1, and x<y, then x is even and y=x+1. It follows that as A=(a1,a2,a3) is a 1-position, neither (a1,a2) nor (a2,a3) has Sprague-Grundy value 1. Indeed, if A is a 1-position, then |a3-a2|≠1, and if |a1-a2|=1, then A is necessarily of type (b). But in this case, if a1 is even, a2<a1, while if a1 is odd, a2>a1, and both cases are impossible if (a1,a2) has Sprague-Grundy value 1. Hence it suffices to consider moves A→B=(b1,b2,b3). First suppose that A is of type (c), that is, A has the form (a1,a1+2,a1+2), where a1 is odd. There is obviously no move from A to (1,1,1). So, since the 1-positions (b1,b2,b3) have |b3-b1|≤2, we need only consider the following moves:(6.1)(a1,a1+2,a1+2)⟶B1=(a1,a1+2,a1+1),(a1,a1+2,a1+2)⟶B2=(a1,a1+2,a1-1),(a1,a1+2,a1+2)⟶B3=(a1,a1+2,a1-2).Firstly,B1 is not a 1-position, since here b1=a1 is odd and b2=b1+2.Secondly,B2 is not a 1-position. Indeed, b3=a1-1 is even and b2>b3.Thirdly,B3 is not a 1-position, as here b1=b3+2 but b2≠b1.Now suppose thatA is of type (b), that is A has the form (a1,a2,a1+1). We need only to consider the following moves:(6.2)(a1,a2,a1+1)⟶B4=(a1-1,a2,a1+1),(a1,a2,a1+1)⟶B5=(a1,a2,a1-2),(a1,a2,a1+1)⟶B6=(a1,a2,a1-1),(a1,a2,a1+1)⟶B7=(a1,a2,a1).
If B4 is a 1-position, then it is of type (c) and so a1 must be even and a2=a1+1, contradicting the assumption that A is a 1-position. Similarly, if B5 is a 1-position, then it is of type (c) and so a1 must be odd and a2=a1, again contradicting the assumption that A is a 1-position. If B6 is a 1-position, then it is of type (b) and either a1 is odd and a2<a1-1 or a1 is even and a2>a1-1, and both cases contradict the assumption that A is a 1-position. If B7 is a 1-position, then it is of type (a) and thus a1=1, but then A=(1,1,2), which is not a 1-position.Finally, ifA is of type (a), then A=(1,1,1) and there is only one move, to (1,1), which is a 0-position. This completes the proof of property 1.To prove property 2, consider a positionB=(b1,b2,b3), with b1≤b3, that is not a 0-position or a 1-position. There are 7 cases to consider;(a)
b3>b1+2,(b)
b3=b1+2 and b1 is even,(c)
b3=b1+2 and b1 is odd and b2≠b3,(d)
b3=b1+1 and b1 is even and b2≥b1,(e)
b3=b1+1 and b1 is odd and b2≤b1,(f)
b3=b1+1 and b1 is odd and b2=b1+2,(g)
b3=b2=b1 and b1≠1.In each case, we must exhibit moves to 1-positions.Case  (a).
We divide this further into subcases;(i)
Ifb1 is even and b2<b1, consider the move B→(b1,b2,b1+1).(ii)
Ifb1 is even and b2=b1 or b2>b1+1, consider the move B→(b1,b2,b1-1).(iii)
Ifb1 is even and b2=b1+1, consider the move B→(b1,b2).(iv)
Ifb1 is odd and b2=b1+1 or b2>b1+2, consider the move B→(b1,b2,b1+1).(v)
Ifb1 is odd and b2=b1+2, consider the move B→(b1,b2,b2).(vi)
Ifb1 is odd and b1>1 and b2<b1-1, consider the move B→(b1,b2,b1-1).(vii)
Ifb1 is odd and b1>1 and b2=b1, consider the move B→(b1,b1,b1-2).(viii)
Ifb1 is odd and b1>1 and b2=b1-1, consider the move B→(b1,b1-1).(ix)
Ifb1=b2=1, consider the move B→(1,1,1).Case  (b).
We have subcases;(i)
Ifb2<b1, consider the move B→(b1,b2,b1+1).(ii)
Ifb2=b1 or b2>b1+1, consider the move B→(b1,b2,b1-1).(iii)
Ifb2=b1+1, consider the move B→(b1,b2).Case  (c).
We have subcases;(i)
Ifb2=b1+1 or b2>b1+2, consider the move B→(b1,b2,b1+1).(ii)
Ifb1>1 and b2<b1-1, consider the move B→(b1,b2,b1-1).(iii)
Ifb1>1 and b2=b1, consider the move B→(b1,b1,b1-2).(iv)
Ifb1>1 and b2=b1-1, consider the move B→(b1,b1-1).(v)
Ifb1=b2=1, consider the move B→(1,1,1).Case  (d).
We have subcases;(i)
Ifb2=b1 or b2>b1+1, consider the move B→(b1,b2,b1-1).(ii)
Ifb2=b1+1, consider the move B→(b1,b2).Case  (e).
We have subcases;(i)
Ifb1>1 and b2<b1-1, consider the move B→(b1,b2,b1-1).(ii)
Ifb1>1 and b2=b1, consider the move B→(b1,b1,b1-2).(iii)
Ifb1>1 and b2=b1-1, consider the move B→(b1,b1-1).(iv)
Ifb1=b2=1, consider the move B→(1,1,1).Case  (f).
Consider the moveB→(b2,b3)=(b1+2,b1+1).Case  (g).
We have subcases;(i)
Ifb1 is odd, consider the move B→(b1-2,b1,b1).(ii)
Ifb1 is even, consider the move B→(b1,b1,b1-1).



---

*Source: 824742-2011-12-29.xml*