Some Remarks on End-Nim

(1)

Volume 2011, Article ID 824742,9pages doi:10.1155/2011/824742

Research Article

Some Remarks on End-Nim

Grant Cairns and Nhan Bao Ho

Department of Mathematics, La Trobe University, Melbourne, VIC 3086, Australia

Correspondence should be addressed to Grant Cairns,[email protected] Received 26 September 2011; Accepted 14 November 2011

Academic Editor: Johannes Hattingh

Copyrightq2011 G. Cairns and N. B. Ho. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

We reexamine Albert and Nowakowski’s variation on the game of Nim, called End-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`ere 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`ere-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.

1. Introduction

Consider k 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 coin1. The well-known solution to Nim, using Sprague-Grundy values, is both elegant and complete1.

In2, 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 in3, 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`ere 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 positionsi.e.,P-positions, except for the positions where all the piles are of equal size. Thus, like the misère form of Nim,

(2)

the games mis`ere-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.

TheP-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`ere games4. 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, . . . , a_kif necessary, we may assume thata1 ≤a_k.

2. The Losing Positions

In Albert and Nowakowski’s entertaining paper2, 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 in5. For a positionA a1, a2, . . . , ak, we definelAto be the largest natural number ifor whicha1 · · · a_i−1 ≤ a_i. Similarly, for a position A a1, a2, . . . , a_k for which thea_iare not all equal, we definerAto be the largest natural numberj for which ak−j1 ≥ak−j2 · · · ak. Ifa1 · · · ak, we setrA 0. Then Albert and Nowakowski’s solution can be rephrased as follows.

Theorem 2.1. In End-Nim, a positionA a1, a2, . . . , akwitha1≤akis aP-position if and only if one of the following conditions holds:

aa1a_k, and furthermore,lA rAis even,

ba_ka11 and, furthermore,lAis odd andrAis even.

Conditionacorresponds to the following 8 hieroglyphs of Albert and Nowakowski.

∗ ∗

∗

∗ ∗

∗

Conditionbcorresponds to the following 4 pictures.

∗ ∗ ∗ ∗

In these pictures, ifa1 · · · a_i−1/a_i, then the ∗ symbol lies in the first resp. second column ifiis evenresp. odd, and it is adjacent to↑resp.↓ifai−1< airesp.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`ere-End-Nim, we modify slightly the definition ofr. We set rmA rAexcept whena1 · · ·ak 1, in which case we setrmA 1. Then we have the following.

(3)

Theorem 2.2. In mis`ere-End-Nim, a positionA a1, a2, . . . , akwitha1 ≤ akis aP-position if and only if one of the following holds:

aa1akand, furthermore,lA rmAis even,

ba_ka11 and, furthermore,lAis odd andr_mAis even.

We postpone the proof until the next section. Let us now describe the solution for Loop-End-Nim. Once again, we modify the r function. We set roA rA except when a1· · ·a_k, in which case we setr_oA 1. Then we have the following.

Theorem 2.3. In Loop-End-Nim, a positionA a1, a2, . . . , akwitha1≤akis aP-position if and only if one of the following holds:

aa1a_kand, furthermore,lA r_oAis even,

ba_ka11 and, furthermore,lAis odd andr_oAis even.

As an immediate consequence of the above three results, we have the following.

Corollary 2.4. The three games, End-Nim, mis`ere-End-Nim, and Loop-End-Nim have the sameP- positions of the formA a1, a2, . . . , a_k, where thea_iare not all equal. IfA a1, a2, . . . , a_kwhere a1· · ·a_k, then

aAis aP-position of End-Nim if and only ifkis even,

bAis aP-position of mis`ere-End-Nim if and only ifkis even anda1 > 1, orkis odd and a11,

cAis aP-position of Loop-End-Nim if and only ifkis odd.

3. Proof of Theorems 2.2 and 2.3

Proof ofTheorem 2.2. We say that a position verifying conditionaorbofTheorem 2.2is a 0-position. We must prove two facts:

1from every positionAthat is not a 0-position, there is a move to a 0-position, 2there is no move from a 0-position to a 0-position.

1LetA a1, a2, . . . , a_kbe a position that is not a 0-position. First suppose thatAis aP-position in End-Nim. ByTheorem 2.1,a1· · ·a_k 1 andkis even. Then we have the moveA → a1, a2, . . . , ak−1, which is a 0-position. Now suppose thatAis not aP-position in End-Nim. Then there is a moveA → B, whereB b1, . . . , bnis aP-position in End-Nim.

IfBis not a 0-position, then byTheorem 2.1,b1 · · · b_n 1 andnis even. Hence either k nanda1 · · ·ak−1 < ak, ork n1 anda1 · · ·ak−1 ≤ ak. In the former case, we have the moveA → a1, a2, . . . , ak−1, which is a 0-position. In the latter case, sinceAis not a 0-position,a_k−1< a_kand we have the moveA → a1, a2, . . . , a_k−1,1, which is a 0-position.

2LetA → Bbe a move between two 0-positions, whereA a1, a2, . . . , akwith a1 ≤ akand B b1, . . . , bn. First suppose thatAis not aP-position in End-Nim. Soa1

· · · a_k 1 andk is odd. But this is a contraction, since necessarilyB a1, a2, . . . , a_k−1, which is not a 0-position. So we may suppose thatAis aP-position in End-Nim. Therefore, Bis not aP-position in End-Nim. Henceb1· · ·bn1 andnis odd. Thus, eitherknand a1· · ·a_k−1< a_k, orkn1 anda1· · ·a_k−1 ≤a_k. In the former case,r_mA 1, which

(4)

is impossible asa1 < akandAis a 0-position. In the latter case,lAis even and so, asAis a 0-position,r_mAis also even. Hencea_k 1. But thena1 · · · a_k 1, which is impossible askis even andAis a 0-position. This completes the proof.

The following argument is modelled closely on the proof we have just given.

Proof ofTheorem 2.3. We say that a position verifying conditionaorbofTheorem 2.3is a 0-position. We must prove two facts:

1from every positionAthat is not a 0-position, there is a move to a 0-position, 2there is no move from a 0-position to a 0-position.

1LetA a1, a2, . . . , a_kbe a position that is not a 0-position. First suppose thatA is aP-position in End-Nim. ByTheorem 2.1,a1 · · · akandkis even. Then we have the moveA → a1, a2, . . . , ak−1, which is a 0-position. Now suppose thatAis not aP-position in End-Nim. Then there is a moveA → B, whereB b1, . . . , b_nis aP-position in End-Nim. If Bis not a 0-position, then byTheorem 2.1,b1 · · ·bnandnis even. Hence eitherknand a1· · ·ak−1< ak, orkn1. In the former case, we have the moveA → a1, a2, . . . , ak−1, which is a 0-position. In the latter case,kis odd and at first sight there are two possibilities:

aa1 < a2 a3 · · · a_k. Here we have the moveA → C a1, a2, . . . , a_k−1, a1, which is a 0-position sincelC roC 4.

ba1a2· · ·a_k−1 ≤a_k. Note that asAis not a 0-position,a_k−1< a_k. Here we have the moveA → a1, a2, . . . , ak−1, ak−1, which is a 0-position.

2LetA → Bbe a move between two 0-positions, whereA a1, a2, . . . , akwith a1 ≤ a_kand B b1, . . . , b_n. First suppose thatAis not aP-position in End-Nim. Soa1

· · · a_k andkis odd. Then eithernk, b1 < a1andb2 b3 · · · b_k a_k, in which case lB 2, ornk−1 andb1 b2 · · · bk−1. But in both cases,Bis not a 0-position, which gives a contradiction. So we may suppose thatAis aP-position in End-Nim. Therefore,B is not aP-position in End-Nim. Hence,b1 · · · b_n andnis odd. Thus, eitherk nand a1. . .ak−1< ak, orkn1. In the former case,roA 1, which is impossible asa1< ak

andAis a 0-position. In the latter case,kis even and at first sight there are two possibilities:

aa1 < a2 a3 · · · a_k. Here,r_oA k−1 n, which is odd, contrary to the assumption thatAis a 0-position.

ba1 a2 · · · a_k−1 ≤a_k. SinceAis a 0-position andkis even, we havea_k−1 < a_k. But thenroA 1, again contracting the assumption thatAis 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`ere-End-Nim, and Loop-End-Nim byG,G_m,G_o, respectively. First observe that End-Nim with two piles is the same as Nim with two piles. So we haveGa, b a⊕b, where⊕denotes Nim addition. The situation regarding Loop-End-Nim is also very simple.

Proposition 4.1. In Loop-End-Nim,G_oa, b a−1⊕b−1 1, for alla, b >0.

(5)

Proof. We will prove thatGoa, b Ga−1, b−1 1 by induction onab. ClearlyGo1,1 1G0,0 1. Supposea, b >0. Then by induction

G_oa, b Mex G_o

a, b

: 0≤a < a

∪ G_o

a, b

: 0≤b < b Mex

{0} ∪ G_o

a, b

: 1≤a < a

∪ G_o

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 Ga−1, b−1 1.

4.1

The situation concerning mis`ere-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`ere Nim, the Sprague-Grundy function has not yet been determined! We have only been able to obtain very partial information. FromTheorem 2.2, a positionA a, bhas Sprague-Grundy value 0 if and only ifab /1. We also have the following.

Proposition 4.2. In the mis`ere-End-Nim, a positionA a, bwith a ≤ bhas Sprague-Grundy value 1 if and only if eitherab1 ora≥3 is odd andba1.

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 inSection 2, in End-Nim with three piles, a positionA a1, a2, a3is aP-position if and only if it is symmetrical but not constant; that is,a3 a1anda2/a1. TheP-positions of mis`ere-End-Nim comprise those of End-Nim, as well as1,1,1. TheP-positions of Loop- End-Nim comprise those of End-Nim, as well as the constant positionsa, a, a, witha≥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, a3witha1≤a3has Sprague-Grundy value 1 if and only if one of the following three conditions holds

aA 1,1,1,

ba3a11 and either

ia1is even anda2< a1or

iia1is odd anda2> a1anda2/a12, ca3a12 anda1is odd anda2a3.

Theorem 5.2. In mis`ere-End-Nim, a positionA a1, a2, a3witha1 ≤ a3 has Sprague-Grundy value 1 if and only if one of the following three conditions holds

aA 1,2,2 ba1a2a3≥3,

(6)

ca3a11 and either ia1is even anda21 or

iia1is odd and either 2≤a2< a1ora2> a3.

Theorem 5.3. In Loop-End-Nim, a positionA a1, a2, a3with a1 ≤ a3 has Sprague-Grundy value 1 if and only if one of the following two conditions holds

aa3a11 and either

ia1is even anda2< a1or iia1is odd anda2> a3.

ba3a12 anda1is odd,a2a11.

We provide a proof ofTheorem 5.1in the next section. The proof is simple and straightforward, but rather long. We omit the proofs of Theorems5.2and5.3which 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, a3witha1≤a3has Sprague-Grundy value 2 if and only if one of the following conditions holds, where the congruences are all modulo 4:

aa1a2a3≥2, a1≡1,2, ba3a11 and either

iA 1,1,2 iia1≡2, a2a3or

iiia1is odd,a1≥7, 5≤a2≤a1−1, a2≡1,2, except fora1≡3 wherea2/a1−2.

ca3a12 and either

ia1≡0, a2≤a1−1 and ifa2≥5 thena2≡0,3, or iia1≡1 and either

IA 1,2,3, IIa2≥a13, or

IIIa2≤a1−1 and ifa2≥5 thena2 ≡0,3,

iiia1≡2 and eithera2a1−1≥5 ora2≥a12, a2/a14.

da3a13,a1≡2 anda2a14.

6. Proof of Theorem 5.1

We say that a position is a 1-position if it has the forma1, a2with Sprague-Grundy value 1, or the forma1, a2, a3verifying conditiona,b, orcofTheorem 5.1; in the latter case we sayAis of typea,b, orc, respectively. We must prove two properties:

1there is no move from a 1-position to a 1-position,

2from every position that is not a 0-position or a 1-position, there is a move to a 1-position.

(7)

To establish the first property, we suppose thatA a1, a2, a3is a 1-position. Ifx, yhas Sprague-Grundy value 1, andx < y, thenxis even andy x1. It follows that as A a1, a2, a3is a 1-position, neithera1, a2nora2, a3has Sprague-Grundy value 1. Indeed, if Ais a 1-position, then|a3−a2|/1, and if|a1−a2| 1, thenAis necessarily of typeb. But in this case, ifa1is even,a2 < a1, while ifa1is odd,a2 > a1, and both cases are impossible if a1, a2has Sprague-Grundy value 1. Hence it suﬃces to consider movesA → B b1, b2, b3. First suppose thatA is of type c, that is, Ahas the forma1, a12, a1 2, where a1 is odd. There is obviously no move fromAto1,1,1. So, since the 1-positionsb1, b2, b3have

|b3−b1| ≤2, we need only consider the following moves:

a1, a12, a12−→B1 a1, a12, a11, a1, a12, a12−→B2 a1, a12, a1−1, a1, a12, a12−→B3 a1, a12, a1−2.

6.1

Firstly,B1is not a 1-position, since hereb1a1is odd andb2b12.

Secondly,B2is not a 1-position. Indeed,b3a1−1 is even andb2> b3. Thirdly,B3is not a 1-position, as hereb1 b32 butb2/b1.

Now suppose thatAis of typeb, that isAhas the forma1, a2, a11. We need only to consider the following moves:

a1, a2, a11−→B4 a1−1, a2, a11, a1, a2, a11−→B5 a1, a2, a1−2, a1, a2, a11−→B6 a1, a2, a1−1, a1, a2, a11−→B7 a1, a2, a1.

6.2

IfB4is a 1-position, then it is of typecand soa1must be even anda2a11, contradicting the assumption thatAis a 1-position. Similarly, ifB5is a 1-position, then it is of typecand soa1 must be odd anda2 a1, again contradicting the assumption thatAis a 1-position. If B6is a 1-position, then it is of typeband eithera1is odd anda2 < a1−1 ora1is even and a2> a1−1, and both cases contradict the assumption thatAis a 1-position. IfB7is a 1-position, then it is of typeaand thusa11, but thenA 1,1,2, which is not a 1-position.

Finally, ifAis of typea, thenA 1,1,1and there is only one move, to1,1, which is a 0-position. This completes the proof of property 1.

To prove property 2, consider a positionB b1, b2, b3, withb1 ≤ b3, that is not a 0-position or a 1-position. There are 7 cases to consider;

ab3> b12,

bb3b12 andb1is even,

cb3b12 andb1is odd andb2/b3, db3b11 andb1is even andb2≥b1,

eb3b11 andb1is odd andb2≤b1,

(8)

fb3b11 andb1is odd andb2b12, gb3b2b1andb1/1.

In each case, we must exhibit moves to 1-positions.

Casea. We divide this further into subcases;

iIfb1is even andb2 < b1, consider the moveB → b1, b2, b11.

iiIfb1is even andb2 b1orb2 > b11, consider the moveB → b1, b2, b1−1.

iiiIfb1is even andb2 b11, consider the moveB → b1, b2.

ivIfb1is odd andb2 b11 orb2> b12, consider the moveB → b1, b2, b11.

vIfb1is odd andb2 b12, consider the moveB → b1, b2, b2.

viIfb1is odd andb1 >1 andb2< b1−1, consider the moveB → b1, b2, b1−1.

viiIfb1is odd andb1 >1 andb2b1, consider the moveB → b1, b1, b1−2.

viiiIfb1is odd andb1 >1 andb2b1−1, consider the moveB → b1, b1−1.

ixIfb1b2 1, consider the moveB → 1,1,1.

Caseb. We have subcases;

iIfb2< b1, consider the moveB → b1, b2, b11.

iiIfb2b1orb2 > b11, consider the moveB → b1, b2, b1−1.

iiiIfb2b11, consider the moveB → b1, b2. Casec. We have subcases;

iIfb2b11 orb2> b12, consider the moveB → b1, b2, b11.

iiIfb1>1 andb2< b1−1, consider the moveB → b1, b2, b1−1.

iiiIfb1>1 andb2b1, consider the moveB → b1, b1, b1−2.

ivIfb1>1 andb2b1−1, consider the moveB → b1, b1−1.

vIfb1b2 1, consider the moveB → 1,1,1.

Cased. We have subcases;

iIfb2b1orb2 > b11, consider the moveB → b1, b2, b1−1.

iiIfb2b11, consider the moveB → b1, b2. Casee. We have subcases;

iIfb1>1 andb2< b1−1, consider the moveB → b1, b2, b1−1.

iiIfb1>1 andb2b1, consider the moveB → b1, b1, b1−2.

iiiIfb1>1 andb2b1−1, consider the moveB → b1, b1−1.

ivIfb1b2 1, consider the moveB → 1,1,1.

Casef. Consider the moveB → b2, b3 b12, b11.

Caseg. We have subcases;

iIfb1is odd, consider the moveB → b1−2, b1, b1. iiIfb1is even, consider the moveB → b1, b1, b1−1.

(9)

References

1 E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays. Vol. 1, A K Peters Ltd., Natick, Mass, USA, 2nd edition, 2001.

2 M. H. Albert and R. J. Nowakowski, “The game of End-Nim,” Electronic Journal of Combinatorics, vol. 8, no. 2, p. 12, 2001, In honor of Aviezri Fraenkel on the occasion of his 70th birthday.

3 R. K. Guy, “Unsolved problems in combinatorial games,” in Games of No Chance (Berkeley, CA, 1994), vol.

29 of Publications of the Research Institute for Mathematical Sciences, pp. 475–491, Cambridge University Press, Cambridge, UK, 1996.

4 T. E. Plambeck and A. N. Siegel, “Mis`ere quotients for impartial games,” Journal of Combinatorial Theory Series A, vol. 115, no. 4, pp. 593–622, 2008.

5 G. Cairns, N. B. Ho, and T. Lengyel, “The Sprague-Gundy function of the real game Euclid,” Discrete Mathematics, vol. 311, no. 6, pp. 457–462, 2011.

(10)

Submit your manuscripts at http://www.hindawi.com

Hindawi Publishing Corporation

http://www.hindawi.com Volume 2014

Mathematics

^{Journal of}

Hindawi Publishing Corporation http://www.hindawi.com

Differential Equations

International Journal of

Volume 2014

Applied Mathematics^{Journal of}

Mathematical PhysicsAdvances in

Complex Analysis

^{Journal of}

Optimization

^{Journal of}

Combinatorics

Journal of

Function Spaces

Abstract and Applied Analysis

International Journal of Mathematics and Mathematical Sciences

The Scientific World Journal

Discrete Dynamics in Nature and Society

Discrete Mathematics

^{Journal of}

Some Remarks on End-Nim

Research Article