INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #G02

PARTIAL NIM

Chu-Wee Lim

Department of Mathematics, University of California Berkeley, Berkeley, CA 94720-3840, USA

                       limchuwe@math.berkeley.edu

Received: 10/19/04, Revised: 3/16/05, Accepted: 4/11/05, Published: 4/20/05

Abstract

In this paper, we offer a complete strategy for a variant of Nim which is partial. Such a strategy can be construed although its canonical form is exponentially complex. Variations of Nim are common in the literature (see [1], [3] and [4] for instance), but as far as we know, this variant of Partial Nim has not been explored before.

We shall assume that the reader is familiar with the basics of combinatorial game theory. See [2] for an excellent explanation of this theory.

1. Introduction

The game of Partial Nim is played as follows: we begin with several piles of stones; some piles of which are colored Red, some of which are colored bLue, while others are colored grEen. At each turn, players Left and Right select a pile and remove a certain number of stones from it, subjected to the following conditions.

1. In a bLue pile, Left may only remove an odd number of stones while Right may only remove an even number.

2. Conversely, in a Red pile, Right may only remove an odd number of stones while Left may only remove an even number.

3. In a grEen pile, there are no restrictions, just like conventional Nim.

The player who is unable to make a move loses. A simple mnemonic for the above cases is as follows: bLue piles are advantageous to Left, while Red piles are advantageous to Right.

In the following sections, we shall describe a complete strategy for this game. The crux lies in the Lexicographical Ordering Principle (Theorem 2).

2. Preliminaries

First, the grEen piles easily simplify to a nim value ∗n, and by symmetry we only need to look at the bLue piles.

Definition 1 : Let A_{n} be the game of partial Nim with a bLue pile of n stones.

The canonical form of A_{n} may be determined recursively. The first few values of A_{n} are:

A_{0} = 0
A_{1} = 1
A_{2} = {A_{1}|A_{0}} = 1|0
A_{3} = \{A_{2}, A_{0}|A_{1}\} = \frac{1}{2}

Theorem 1 : For n ≥ 1, we have:

(i) A_{2n−1} = \frac{1}{2^{n−1}} . (ii) A_{2n} = {1 | 0, A_{2n−2}}, which is canonical for n > 1. (iii) A_{2} > A_{4} > A_{6} > . . ..

Proof. The proof is by induction. Suppose the above holds for all n ≤ m, m ≥ 2. Then

A_{2m+1} = {A_{2m}, A_{2m−2}, …, A_{0} | A_{2m−1}, A_{2m−3}, …, A_{1}}.

By induction hypothesis, each A_{2i−1} on the right is \frac{1}{2^{i−1}} so Right’s best move is to A_{2m−1} = \frac{1}{2^{m−1}} . On the left, A_{2i} (i = 1, …, m) reverses back to 0 since A_{2m+1} is positive. Hence A_{2m+1} = \{0 | 2^{−(m−1)}\} = \frac{1}{2^{m}}.

For the even case, Left’s best move is to A_{1} = 1, while for Right’s moves, the induction hypothesis gives A_{2} > A_{4} > ⋯ > A_{2m} so her best move is to either A_{2m} or A_{0} = 0. Hence,

A_{2m+2} = {1 | 0, A_{2m}} ≤ {1 | 0, A_{2m−2}} = A_{2m}.

Note that equality cannot hold since Right has a winning strategy in A_{2m+2} − A_{2m} by taking A_{2m+2} → A_{2m} leaving 0.

Finally, A_{2m+2} is in canonical form since the Right option A_{2m} is confused with 0 and does not reverse to 1 (which is incomparable to A_{2m+2}).

Corollary 1 : For an integer n ≥ 1,

(i) A_{2n} has a confusion interval of (0, 1). (ii) At the end points, A_{2n} is confused with both 0 and 1. (iii) A_{2n} has a temperature of \frac{1}{2}.

Proof. (i) and (iii) follow from induction and the recursive formula in Theorem 1(ii), while (ii) follows from the fact that A_{2n} is a first-player win (hence confused with 0) and A_{2n} − 1 = {0 | − 1, A_{2n−2}} is a first-player win as well.

Let us centralize the game A_{2n} so that its mean is 0.

Definition 2 : For m ≥ 1, let [m] denote the game \frac{1}{2} − A_{2m} and [−m] denote the game −[m]. More generally, we define

[m_{1}, m_{2}, …, m_{r}] = [m_{1}] + [m_{2}] + ⋯ + [m_{r}]

for non-zero integers m_{1}, m_{2}, …, m_{r}.

Theorem 1 immediately gives a recursive definition of [m]:

[1] = ±\frac{1}{2}, [m + 1] = \{\frac{1}{2}, [m] | −\frac{1}{2} \} .

It is clear that the difficulty of handling [m] in sums of games increases exponentially as m gets larger. Expressing [m_{1}, …, m_{r}] in canonical form is probably out of the question. Furthermore, we shall see later in Section 4 that the differences between these sums are extremely small, typically about tiny +_{1}. Hence comparison between the games appears rather difficult.

3. Strategy

Immediately, Theorem 1 and Corollary 1 give the following.

Lemma 1 : Let m be a non-zero integer.

(i) The confusion interval of [m] is the closed interval −\frac{1}{2} ≤ x ≤ +\frac{1}{2}. (ii) The temperature of each [m] is \frac{1}{2}. (iii) … [−3] < [−2] < [−1] = [1] < [2] < [3] < . . ..

The next step is to analyze the pair [i, j].

Lemma 2 : Let i, j be non-zero integers. Then the game [i, j] is infinitesimal.

Proof. Suppose i, j > 0. Then Lemma 1(iii) gives [i, j] = [i] + [j] > [1] + [1] = 0. So it suffices to show [i, j] ≯ ϵ for any positive number ϵ. Indeed, in the game [i, j] − ϵ, Right has a winning strategy if she starts: take [i] → −\frac{1}{2} and leave [j] − (\frac{1}{2} + ϵ) which is negative since \frac{1}{2} + ϵ lies outside the confusion interval of [j].

On the other hand, suppose we have i > j > 0 and the game [i, −j] = [i] − [j]. Then [i] > [j] by Lemma 1(iii), while in the game [i] − [j] − ϵ, Right takes [i] → −\frac{1}{2} as before to secure a win.

Theorem 2 (Lexicographical Ordering Principle) : Suppose we have positive integers m_{1} ≤ m_{2} ≤ ⋯ ≤ m_{r} and n_{1} ≤ n_{2} ≤ ⋯ ≤ n_{r}. Then

[m_{1}, m_{2}, …, m_{r}] < [n_{1}, n_{2}, …, n_{r}]

if the r-tuples satisfy (m_{i})_{i=1}^{r} < (n_{i})_{i=1}^{r} in lexicographical ordering, i.e. if there exists 1 ≤ i ≤ r, such that m_{j} = n_{j} for all 1 ≤ j < i but m_{i} < n_{i}.

Proof. First, the theorem holds for r = 1 and for m_{1} = m_{2} = ⋯ = m_{r} = 1 (cf. Lemma 1(iii)). With these simple cases in mind, we now apply induction on the sum r + ∑_{i}(m_{i} + n_{i}).

Let r ≥ 2 and G = [n_{1}, …, n_{r}, −m_{1}, …, −m_{r}]. We first prove that G ≥ 0. If any m_{i} and n_{j} are equal, we may cancel both and apply the induction hypothesis for r − 1. So we assume that m_{i} ≠ n_{j} for any i, j. Now if Right has the first move in G, she has the following options:

Case 1 : Take [n_{i}] → −\frac{1}{2}, so the right incentive Δ^{R} = G − G^{R} = \frac{1}{2} + [n_{i}]. Then the best choice for Right is [n_{r}]. Left may counter this move by taking [m_{r}] → \frac{1}{2} to produce

[n_{1}, n_{2}, …, n_{r−1}, −m_{1}, −m_{2}, …, −m_{r−1}]

which is non-negative by induction hypothesis. So Left wins in this case.

Case 2 : Take −[m_{i}] → −[m_{i} − 1] for some m_{i} > 1. Now we still have

(m_{1}, …, m_{i−1}, m_{i} − 1, m_{i+1}, …, m_{r}) < (n_{1}, …, n_{r}),

so the resulting game from G is positive by induction hypothesis. Left still wins.

Case 3 : Take −[m_{i}] → −\frac{1}{2}, so Δ^{R} = \frac{1}{2} − [m_{i}]. Since the smallest [m_{i}] is [m_{1}], Right would do best by moving G to [n_{1}, …, n_{r}, −m_{2}, …, −m_{r}] − \frac{1}{2}. If m_{2} < n_{2} as well, then Left may counter with [n_{1}] → \frac{1}{2} and reduce G to

[n_{2}, n_{3}, …, n_{r}, −m_{2}, −m_{3}, …, −m_{r}],

which is ≥ 0 by induction hypothesis. Otherwise, m_{2} > n_{2} and Left responds with [−m_{2}] → \frac{1}{2} leaving

[n_{1}, n_{2}, …, n_{r}, −m_{3}, …, −m_{r}] = [n_{1}, n_{2}, …, n_{r}, −1, −1, −m_{3}, …, −m_{r}].

Since m_{1} ≥ 1 and m_{2} > n_{2} ≥ 1, we have reduced the sum ∑(m_{i} + n_{i}), and induction applies.

The above shows G ≥ 0. To complete the proof for G > 0, note that

[m_{1}, …, m_{r−1}, m_{r}] < [m_{1}, …, m_{r−1}, m_{r} + 1] ≤ [n_{1}, …, n_{r}].

It is natural now to ask for a comparison between [m_{1}, …, m_{r}] and [n_{1}, …, n_{s}] in general. Suppose r + s is even and r > s. Then we may add pairs of [1, 1] = 0 to the second game until both games have equal number of terms. The Lexicographical Ordering Principle gives us [m_{1}, …, m_{r}] > [n_{1}, …, n_{s}]. Hence, w have a more general result

Corollary 2 : Suppose m_{1} ≤ m_{2} ≤ ⋯ ≤ m_{r} and n_{1} ≤ n_{2} ≤ ⋯ ≤ n_{s} are positive integers, and r < s are of the same parity. Assume further that at most one m_{i} (resp. n_{j}) is equal to 1. Then

[m_{1}, m_{2}, …, m_{r}] < [n_{1}, n_{2}, …, n_{s}].

In summary, we get the following ordering:

0 = [1, 1] < [1, 2] < [1, 3] < [1, 4] < ⋯ < [1, m] < …
< [2, 2] < [2, 3] < [2, 4] < ⋯ < [2, m] < …
< [3, 3] < [3, 4] < ⋯ < [3, m] < …
⋮ ⋮
< [1, 2, 2, 2] < [1, 2, 2, 3] < [1, 2, 2, 4] < [1, 2, 2, 5] < …
< [1, 2, 3, 3] < [1, 2, 3, 4] < [1, 2, 3, 5] < …
⋮ ⋮
< [1, 2, 2, 2, 2, 2] < [1, 2, 2, 2, 2, 3] < [1, 2, 2, 2, 2, 4] < …
⋮ ⋮

Next, we shall compare the games [m_{1}, …, m_{r}] and [n_{1}, …, n_{s}] when r and s are of different parity. Again, assume m_{1} ≤ ⋯ ≤ m_{r} and n_{1} ≤ ⋯ ≤ n_{s}, and that at most one m_{i} (resp. n_{j}) is equal to 1. As before, let G = [m_{1}, …, m_{r}, −n_{1}, …, −n_{s}] be the difference. Since [m, n] is infinitesimal for all m, n ≠ 0, G has confusion interval (−\frac{1}{2}, +\frac{1}{2}). The only uncertainty lies in the endpoints −\frac{1}{2}, +\frac{1}{2}.

Theorem 3: Let G be as above, with r < s. Then

(i) the game G is confused with −\frac{1}{2}; and (ii) G < +\frac{1}{2}, unless we have the exceptional case of r = s − 1 and (m_{i})_{i=1}^{r} ≥ (n_{i})_{i=1}^{r} lexicographically.

Proof. (i) Look at G + \frac{1}{2}. If Left starts, he wins easily by taking −[n_{s}] → +\frac{1}{2} to produce [m_{1}, …, m_{r}, −n_{1}, …, −n_{s−1}] + 1. Since the bracketed part has an even number of terms, it is infinitesimal and hence G + \frac{1}{2} > 0.

If Right starts and r > 0, he takes [m_{r}] → −\frac{1}{2} and leaves the game [m_{1}, …, m_{r−1}, −n_{1}, …, −n_{s}] which is negative by Corollary 2. On the other hand, if r = 0, Right repeatedly takes any −[n_{j}] → −\frac{1}{2}. Left then has no choice but to take a −[n_{j′}] → +\frac{1}{2} or [m_{i}] → +\frac{1}{2}. Since r + s is odd, this exchange favours Right.

(ii) Consider G − \frac{1}{2}. If Right starts, she wins by turning any [m_{i}] or −[n_{j}] to −\frac{1}{2}. But if Left starts, he has the following options.

Case 1 : Take [m_{i}] → \frac{1}{2}, producing [m_{1}, …, m̂_{i}, …, m_{r}, −n_{1}, …, −n_{s}] which is negative by Corollary 2. This move is clearly bad.

Case 2 : Left takes [m_{i}] → [m_{i} − 1] for some m_{i} > 1, which Right counters by [m_{i} − 1] → −\frac{1}{2} and wins.

Case 3 : Left’s only chance is to take [−n_{j}] → \frac{1}{2}. This gives Δ^{L} = \frac{1}{2} + [n_{j}] so the best choice is in [−n_{s}]. The resulting game is

[m_{1}, m_{2}, …, m_{r}, −n_{1}, −n_{2}, …, −n_{s−1}].

By the Lexicographical Ordering Principle and its Corollary, this game is negative (Right wins) unless r = s − 1 and (m_{i})_{i=1}^{r} ≥ (n_{i})_{i=1}^{r} lexicographically; in which case it is ≥ 0 and Left wins. This proves the theorem.

Note that we have not taken into account the grEen part of partial Nim, i.e. we need to compare [m_{1}, …, m_{r}] and ∗N. This will be covered in the next section.

Examples : Let us analyze the following games, where the brackets () and (()) refer to bLue and Red piles respectively.

1. (3,3,9), ((2,1)). The odd piles sum up to \frac{1}{2} + \frac{1}{2} + \frac{1}{2^{4}} − 1. The confusion interval of ((2)) is (−1, 0), hence the first player wins.

2. (1,2,6), ((3,3,3,5)). The odd piles add up to −\frac{3}{4}, while (2, 6) = A_{2}+A_{4} = 1+[−1, −3] is 1-ish. So Left wins.

3. (1), ((8,4,6)). This game is 1 − A_{4} − A_{2} − A_{3} = −\frac{1}{2} + [4, 2, 3]. Since [4, 2, 3] is confused with \frac{1}{2}, the first player wins.

4. (1,2,6,10), ((3,5,5,4,4,8)). This game is [2, 2, 4, −1, −3, −5] > 0 since lexicographically (1, 3, 5) < (2, 2, 4). Left wins.

5. (1,3,12), ((5,5,8,4,2)). The resulting sum is [4, 2, 1, −6] > 0, so Left wins.

6. (3,3,4,8), ((6,10,6)). The sum is \frac{1}{2} + [3, 3, 5, −2, −4]. Since removing [5] gives [2, 4] < [3, 3], the game [3, 3, 5, −2, −4] > −\frac{1}{2} by Theorem 3, i.e. Left wins.

7. (3,3,8,8), ((6,10,6)). Similar to (5), but in [3, 3, 5, −4, −4], deleting the game [5] results in the exceptional case of [3, 5] < [4, 4]. So the first player wins.

In canonical form, the game in example (6) is:

1, {1|||0||0| − 1, {0| − 1}} || {1|||0||0| − 1, {0| − 1}} | {0| − 1, {0| − 1}}, {0||0| − 1, {0| − 1}}

according to David Wolfe’s Gamesman Toolkit, which also verified this game to be positive.

4. Comparing [m_{1}, …, m_{r}] With Infinitesimals

For an even r, let us compare the games [m_{1}, …, m_{r}] and +_{k} = {0||0| − k}. Throughout the rest of this article, for games A and B, we will write A ≫ B if A > n · B for any positive integer n.

Lemma 3 : Let D_{m} = [m + 1, −m]. Then we have

+_{1} = D_{1} ≫ D_{2} ≫ D_{3} ≫ ⋯ ≫ +_{1+ϵ}

for any number ϵ > 0.

Proof. The equality on the left is easy. The Lexicographical Ordering Principle gives D_{m} > i · D_{m+1} for any positive integer i. For the rightmost inequality, it suffices to show D_{m} ≥ +_{1+ϵ} for any m and number ϵ > 0.

Indeed, we wish to show that G = [m] − [m + 1] + +_{1+ϵ} ≤ 0. Suppose Left starts. If he moves [m] → [m − 1], Right can respond with −[m + 1] → −[m]. On the other hand, if he takes −[m + 1] → \frac{1}{2} or [m] → \frac{1}{2}, Right makes a move in the tiny component and wins.

Corollary 3 : The game G = [m_{1}, …, m_{r}], if positive, satisfies +_{1+ϵ} < G < +_{1−ϵ} for any number ϵ > 0.

Proof. If r is odd, then G is fuzzy. When r is even, the right inequality follows easily from the Lexicographic Ordering Principle :

[m_{1}, …, m_{r}] = (r + 2)[1, 1] + [m_{1}, …, m_{r}] < \overbrace{[1, 2, …, 1, 2]}^{r+1} = (r + 1)[1, 2] < +_{1−ϵ}.

To prove the left inequality, we may append copies of [1, 1] or [−1, −1] to G, such that in G = [m_{1}, …, m_{r}], there are as many positive m_{i}’s as negative m_{i}’s. In this way, we may rewrite G as [m_{1}, …, m_{s}] − [n_{1}, …, n_{s}] = ∑_{i=1}^{s}[m_{i}, −n_{i}], where n_{1} ≤ ⋯ ≤ n_{s}, m_{1} ≤ ⋯ ≤ m_{s}. Since G is positive, we may assume, with no loss of generality, that m_{1} > n_{1}. Thus, [m_{1}, −n_{1}] ≥ D_{n_{1}}. As for [m_{i}, −n_{i}] with i > 1, if m_{i} ≥ n_{i} then [m_{i}, −n_{i}] ≥ 0 and dropping the term [m_{i}, −n_{i}] gives a smaller G. We may therefore assume m_{i} < n_{i} for all i > 1, whence by lemma 3,

G = [m_{1}, −n_{1}] − ∑_{i=2}^{s}[n_{i}, −m_{i}] > D_{m_{1}} − k · D_{m_{1}+1} > +_{1+ϵ},

for some positive integer k.

Now we may complete our analysis, by comparing [m_{1}, …, m_{r}] and ∗N.

Theorem 4 : Consider the game [m_{1}, …, m_{r}], where the m_{i}’s are all non-zero integers.

(i) If r is even, then [m_{1}, …, m_{r}] + (∗N) is fuzzy when N > 0. (ii) If r is odd, then −\frac{1}{2} < [m_{1}, …, m_{r}] + (∗N) < +\frac{1}{2} when N > 0. In particular, we see that in partial Nim, ∗1 is already “remote”.

Proof. (i) Indeed, G = [m_{1}, …, m_{r}], if positive, lies strictly between +_{1+ϵ} and +_{1−ϵ}. Since both of these bounds are incomparable with ∗N, so is G.

(ii) Consider G = [m_{1}, …, m_{r}] + \frac{1}{2} + (∗N). If it were Left’s turn, he can easily secure a win by moving m_{r} → \frac{1}{2}. On the other hand, if it were Right’s turn, he cannot afford to move [m_{i}] → [m_{i} + 1] (for some m_{i} < −1) or Left can win as before. Hence his only chance is m_{i} → −\frac{1}{2}, which results in the game

[m_{1}, …, m̂_{i}, …, m_{r}] + (∗N)

which is a win for the next player by part (i). Hence, Right loses and G > 0. Replacing [m_{1}, …, m_{r}] by [−m_{1}, …, −m_{r}], we get the other inequality.

With this theorem, our analysis for partial Nim is complete.

Examples : Let us add ∗N (N > 0) to the games in the previous example.

1. (3,3,9), ((2,1)), *N. The outcome is still fuzzy, i.e. first player wins.

2. (1,2,6), ((3,3,3,5)), *N. As before, Left wins.

3. (1), ((8,4,6)), *N. The game is now −\frac{1}{2} ∗ N + [4, 2, 3] < 0. Right wins.

4. (1,2,6,10), ((3,5,5,4,4,8)), *N. The resulting game is [2, 2, 4, −1, −3, −5]+∗N which is fuzzy. First player wins.

5. (1,3,12), ((5,5,8,4,2)), *N. The game [4, 2, 1, −6] + (∗N) is fuzzy - first player wins.

6. (3,3,4,8), ((6,10,6)), *N. The sum is now \frac{1}{2} ∗ N + [3, 3, 5, −2, −4] which is positive. Left wins.

7. (3,3,8,8), ((6,10,6)), *N. The game \frac{1}{2} ∗ N + [3, 3, 5, −4, −4] is also positive - Left wins.

5. Other Variants of Partial Nim & Future Work

It is natural to consider exploring other variants of Partial Nim. For example, what if we had altered the rules for this version: in a bLue (resp. Red) pile, Left (resp. Right) can take any number of stones, while Right (resp. Left) can only take an odd number?

This variant turns out to be easy.

Theorem 5 : Let B_{n} be this game for a bLue pile of n stones.

(i) If n = 2m, then B_{n} = ↑ + ↑^{2} + ⋯ + ↑^{m}. (ii) If n = 2m + 1, then B_{n} = ↑ + ↑^{2} + ⋯ + ↑^{m} + ∗.

Proof. Omitted, left as an exercise to the reader.

It may also be fruitful to examine partial variants of well-known games such as Kayles, Dawson’s Chess or Treblecross. We hope that these can yield interesting new results.

Acknowledgements

The author would like to thank Professor Elwyn Berlekamp for his encouragement in getting the paper written, and for his excellent course in Combinatorial Game Theory back in Fall 2002.

References

[1] M. H. Albert and R. J. Nowakowski. Nim restrictions. Integers, 4:Paper G1, 10pp. (electronic). 2004.

[2] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. Winning ways for your mathematical plays, Volume 1. A.K. Peters Ltd., second edition, 2001.

[3] Achim Flammenkamp, Arthuer Holshouser, and Harold Reiter. Dynamic one-pile blocking Nim. Electron. J. Combin. 10(1): Note 4, 6 pp. (electronic), 2003.

[4] Furman Smith and Pantelimon Stǎnicǎ. Comply/restrain games or games with a Muller twist. Integers, 2:Paper G3, 10 pp. (electronic), 2002.