INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #G01

NIM RESTRICTIONS

M. H. Albert

Department of Computer Science, University of Otago, Dunedin, New Zealand

                         malbert@cs.otago.ac.nz

R. J. Nowakowski^{1}

Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, Canada

                           rjn@mathstat.dal.ca

Received: 6/20/03, Revised: 10/3/03, Accepted: 2/22/04, Published: 2/23/04

Abstract

A number of Nim-like games in which moves are restricted somehow to occur from a single pile are analysed. In each case the complete description of type P and type N positions is obtained. A more detailed analysis of the Sprague-Grundy values of positions in two heap Nim where the move must be from the larger heap is also presented.

1. Introduction

The game of Nim is the progenitor of a large family of games called in [2] taking and breaking games. In most of these games the moves allowed in Nim are extended in some way. An alternative approach is to consider variations on Nim in which the allowable moves are restricted. For example in End-Nim [1] the heaps are arranged in a row, and only moves that affect one of the end heaps are permitted. Other variations on Nim are considered in [6] and [4]. Other work in this area includes investigation of the additive peridocity of the sequence of Sprague-Grundy values in games related to Nim [3].

In this paper we investigate a family of even stronger restrictions of Nim. In this family, there will be only a single heap in which it is permissible to make a move at any time. Because of this restriction, these games do not decompose naturally as sums, and so the standard methods of computing Sprague-Grundy values are of limited benefit in their analysis. It would of course be of interest to know the values of such games in order to be able to combine them with other games. In the final section we consider a specific instance of this problem. This simple example already illustrates the fact that the Sprague-Grundy values of this group of games exhibit a complex intermingling of regular and irregular behaviours. Although we do not give a detailed analysis here, most of the other games we consider also show similar features.

1This author wishes to thank the NSERC for partial financial support.

We consider two different ways in which the restriction to move in a single heap could arise. In one, the allowed heap is determined as a function of the present heap sizes (basically we consider only the case where the allowed move is in the heap of maximum size). Variations where the allowed moves are in the smallest heap tend to be even simpler than those considered here. Allowing moves in the second largest heap corresponds to the misère versions of the largest heap games. More baroque variations, such as allowing moves in the heap of median size (with a suitable definition of median when an even number of heaps are present) could also be considered. The second way in which to enforce the restriction is by an active choice of the player moving – a type of condition called a comply-constrain game in [6].

Our main goal then is to determine when the next, or previous, player is able to force a win. We recall the basic characterizing properties of such positions. Given a position, its options are the positions that can be reached in exactly one move. We are dealing with some impartial game 𝔊, a game in which the options available to each player from a given position are the same. We assume throughout that from any position G of 𝔊 no infinite sequences of moves are possible. Then there is a unique partition of the positions of 𝔊 into two classes, denoted N_{𝔊} and P_{𝔊} defined by the following properties:

• For any G ∈ N_{𝔊}, G has an option in P_{𝔊}.

• For any G ∈ P_{𝔊}, all the options of G are in N_{𝔊}.

This partition defines the collections of N ext player wins and Previous player wins. Namely, faced with a position in N, by the first condition you have a move to P. So you can make this move, and not lose immediately (we assume the normal play convention throughout, that is, the first player unable to make a legal move is the loser). However, faced with a position in P you may not have any move available at all (and so will lose immediately), or you may move to an N position, from which your opponent will, unless feeling charitable, return to you the dubious privilege of moving from a P position at your next turn.

2. Greedy Nims

In greedy Nim you are required to remove beans from the largest (or any equal largest) heap.

Proposition 1 The P positions for greedy Nim are precisely those in which the number of equal largest heaps is even.

Proof: We must show that the partition of positions defined in the statement satisfies the defining conditions discussed in the introduction.

First suppose that the number of largest heaps is odd. If this odd number is larger than 1, then we may remove any number of beans from a largest heap, leaving a position with an even number of largest heaps. If there is a unique largest heap, we consider how many second-largest heaps there are. If this number is odd, we reduce the size of the largest heap to match them; if it is even, we can remove the largest heap entirely. In either case we move to a position where the number of largest heaps is even.

Conversely, if the number of largest heaps is even, and if we have any move available (so it is not 0), then any move we make leaves an odd number of largest heaps.

Other variations of greedy Nim arise naturally if we consider coins on strips games. Namely, a position consists of a number of coins placed on a semi-infinite strip with cells labelled 1, 2, . . .. Generically a move consists of taking a coin from a cell and either removing it entirely from the strip, or placing it on a cell with a smaller label^{2}. Consider first of all the game greedy small-cells where we are required to move the coin with largest label, and where no cell can contain more than one coin (basically a restriction of Welter’s game [2], where we require a particular coin to be moved, except that we allow the complete removal of a coin).

Proposition 2 The P positions for greedy small-cells are the empty position and those in which the largest occupied cell has an even label, n, and the cell n − 1 is also occupied.

Proof: After a move from such a position (if any are available) the largest occupied cell will have an odd label, so the position will not be of this type.

Conversely, suppose that we are given a position which is not of this type. Consider the second largest label, call it k. If k is even, and k − 1 is occupied, then simply remove the coin with largest label. If k is even, but k − 1 is unoccupied, move the coin with largest label to cell k − 1. If k is odd, then k + 1 is unoccupied since the position was not of the given type, so we can move the coin with largest label to position k + 1.

As a final variation on this particular theme, consider the game greedy explosive-cells. As before, only the rightmost coin on the strip may be moved. It may be removed entirely, or moved leftwards, either to an empty square, or onto a square containing another coin, in which case the two coins annihilate one another. This game is related to a family of games discussed by A. Fraenkel in [5].

We first define a collection of positions, which we shall refer to (for obvious reasons) as “type P ” for this game as follows:

2Replacing “coin on cell i” with “heap of i beans” shows the correspondence between this viewpoint and the normal description of Nim-like games.

• The empty position is type P.

• A non empty position is type P if its two largest elements are consecutive, the largest is odd, and the result of deleting these two elements is not of type P.

Unravelling the recursive definition in the second part, we see another way of describing the type P positions is that, reading downwards from the largest coin, they consist of either an even number of consecutive pairs of the form {2k, 2k + 1} (and no other coins), or an odd number of such pairs, together with a non-empty position (whose maximal coin does not belong to such a pair).

Proposition 3 The P positions of greedy explosive-cells are precisely the type P positions.

Proof: Obviously all positions with one or two coins are N positions. Consider now positions having three or more coins. Reading from right to left let the coins be labeled c_{1}, c_{2} etc. By the rules of the game c_{1} must be moved.

Let a type P position containing three or more coins be given. Any move which does not destroy c_{2} leaves a position with the largest coin, i.e. c_{2}, on an even square, so a position not of type P. On the other hand the move destroying c_{2} leaves a non type P position by definition.

Now consider any position which is not of type P but which has three or more coins. We must establish that it has an option of type P. First take c_{1} in hand. If the remaining position is already of type P, simply remove c_{1} from play. If not, we must consider some cases.

First, the new largest coin, c_{2}, might be on an even square. Then we can play c_{1} onto the larger square next to c_{2}. If this does not result in a type P position, then by definition using the c_{1} to destroy c_{2} will. If it is not a legal move to place c_{1} on the larger square next to c_{2} (because it came from that square in the first place), then again by definition the position below c_{2} must have been of type P and so again using c_{1} to destroy c_{2} results in type P position.

Secondly, c_{2} might be on an odd square. If the square below it is vacant then either playing c_{1} into this square, or using c_{1} to destroy c_{2}, will yield a type P position.

Finally, the c_{2} might be on an odd square with the square below it already occupied by c_{3}. Now if the position without c_{1} as a whole is type P we simply remove c_{1} from the game. If not, then the remainder of the position below c_{2} and c_{3} is of type P. If it is empty, we can simply drop the old largest coin into it somewhere, and create an N position in that region, leaving a type P position overall. If it is non-empty then there must be an even number of pairs, starting with c_{2}, c_{3} of the form {2k + 1, 2k} therefore we can use c_{1} to destroy c_{4}. The remaining position as a whole has type P.

3. Pointed Nim

In Pointed Nim the usual heaps of beans are augmented with a pointer which points to a heap even at the begining of the game. This pointer designates in which heap the next move must be made. To make a move a player removes one or more beans from the designated heap, and then must move the pointer to a different, non-empty, heap (if possible). The player who takes the last bean wins. This, in the terminology of [6] is a “comply/constrain” game, and differs from one of the games considered in that paper only in that we forbid the placement of the pointer on an empty heap when there are still non-empty heaps available. The characterization of the P-positions for Pointed Nim is an amusing counterpart to that of greedy Nim.

Proposition 4 The P-positions in Pointed Nim are those positions with an even number of heaps, and where the pointer is directed at one of the smallest heaps.

Proof: Any move from such a position leaves a position in which either the number of heaps is odd (if an entire heap was removed), or the pointer is not directed at a smallest heap (otherwise). These positions are not of the specified type.

Conversely suppose that a position is not of this type. If the number of heaps is odd, remove the directed heap entirely and direct the pointer at (one of) the smallest remaining heaps. If the number of heaps is even, the pointer is not on a smallest heap. In particular, the size of the designated heap is at least 2. So, decrease the size of the designated heap by one, and redirect the pointer at a smallest heap.

4. Sprague-Grundy values for Greedy Nim

The importance of Sprague-Grundy values for Greedy Nim was only realised when two combinatorial game theorists met at a bar. On the counter in front of them were three bowls, two containing popcorn and one containing peanuts. Social convention dictated that if choosing some popcorn then it should be taken from the fuller bowl. Social convention further dictated that the first person unable to have a snack (because all the bowls were empty) would have to buy the next round of drinks. In order to determine who that would be (and how to ensure that he/she would be forced to live up to his/her obligations) it would suffice to determine the Sprague-Grundy value of the Greedy Nim position in the popcorn bowls.

On the readily accessible serviettes a table of such values was computed. Filling in the entries of this table was straightforward since, using p(a, b) to denote the Sprague-Grundy value of two heap greedy Nim with a beans in one heap and b in the other, then

19  19  18  18  18  17  16  16  16  15  16  15  14  9  8  8  6  3  1  0
18  18  17  17  17  16  15  15  15  14  15  14  13  8  7  5  4  2  0  1
17  17  16  16  16  15  14  14  14  13  14  13  8  7  5  4  1  0  2  3
16  16  15  15  15  14  13  13  13  12  13  12  7  5  3  2  0  1  4  6
15  15  14  14  14  13  12  12  12  11  12  7  6  3  1  0  2  4  5  8
14  14  13  13  13  12  11  11  11  10  11  6  4  2  0  1  3  5  7  8
13  13  12  12  12  11  10  10  10  6  6  4  1  0  2  3  5  7  8  9
12  12  11  11  11  10  9  9  9  5  3  2  0  1  4  6  7  8  13  14
11  11  10  10  10  9  8  8  5  3  1  0  2  4  6  7  12  13  14  15
10  10  9  9  9  8  7  5  4  2  0  1  3  6  11  12  13  14  15  16
9  9  8  8  8  7  4  4  1  0  2  3  5  6  10  11  12  13  14  15
8  8  7  7  7  6  3  2  0  1  4  5  9  10  11  12  13  14  15  16
7  7  6  6  6  3  1  0  2  4  5  8  9  10  11  12  13  14  15  16
6  6  5  5  5  2  0  1  3  4  7  8  9  10  11  12  13  14  15  16
5  5  4  4  1  0  2  3  6  7  8  9  10  11  12  13  14  15  16  17
4  4  3  2  0  1  5  6  7  8  9  10  11  12  13  14  15  16  17  18
3  3  1  0  2  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18
2  2  0  1  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18
1  0  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19

Figure 1: The Sprague-Grundy values for two heap Greedy Nim (heap sizes increasing from left to right and bottom to top).

if a ≥ b

p(a, b) = mex {p(a′, b) : 0 ≤ a′ < a}.

In other words, to fill in an entry on or to the right of the main diagonal in the table, you take the minimum excluded value, or mex, of the elements in the row to its left. Entries above the diagonal are filled in symmetrically by considering the column below them. By contrast, in ordinary Nim the value would be the mex of the elements in both the adjacent row and column. A portion of this table (a = b = 0 in the lower left) is reproduced in Figure 1.

Note that the value p(b + 1, b) is the least value not occurring among p(c, b) with c ≤ b. The value p(b + 2, b) is the second smallest value not in that set, and so on. At some point all the values below the maximum of the set {p(c, b) : c ≤ b} will have been added, and from that point onwards the values in a row increase by 1 each time. So, the values to the right of the main diagonal in a row consist of a filling in segment, followed by a regularly increasing segment, and so can be specified by the filled values, together with the first entry of the regularly increasing segment.

To focus attention on this observation, Figure 2 shows these segments of each row. This figure also illustrates an apparent regularity in the eventual values of the sequences p(a + k, a) for fixed k, which appear as columns. Namely it seems that after an initial period of noise, these values become periodic consisting of 2k − 1 repeated k times, followed by 2k repeated k times. Most of this regularity is real, but a critical part of it, the form of the repeated blocks, is not, as documented in Figure 3.

We have no idea how to find the form of the period in the kth subdiagonal, but we can prove that it exists. Namely:

Theorem 5 For every positive integer k, the sequence of values (p(a, a + k))_{a=0}^{∞} is eventually periodic with period 2k. The values occurring in the periodic part are 2k and 2k −1 and within the periodic regime, the values p(a + k, a) and p(a + 2k, a + k) always differ.

1  2
2  1  3
3  2  4
4  1  5
5  2  3  6
6  1  3  4  7
7  2  4  5  8
8  1  4  5  9
9  2  3  5  6  10
10  1  3  6  11
11  2  4  6  7  12
12  1  4  6  7  8  13
13  2  3  5  7  8  9  14
14  1  3  5  7  8  9  15
15  2  4  5  8  9  10  16
16  1  4  6  8  9  10  11  17
17  2  3  6  9  10  11  12  18
18  1  3  6  9  10  11  12  19
19  2  4  5  7  10  11  12  13  20
20  1  4  5  7  10  11  12  13  21
21  2  3  5  7  8  11  12  13  14  22
22  1  3  6  7  8  11  12  13  14  15  23
23  2  4  6  8  9  12  13  14  15  16  24
24  1  4  6  8  9  13  14  15  16  25
25  2  3  5  8  9  13  14  15  16  17  26
26  1  3  5  9  10  13  14  15  16  17  18  27
27  2  4  5  7  9  10  14  15  16  17  18  19  28
28  1  4  6  7  10  14  15  16  17  18  19  29
29  2  3  6  7  10  11  14  15  16  17  18  19  20  30

Figure 2: The Sprague-Grundy values for segments in row a, from p(a + 1, a) until the beginning of regular increase.

k  Onset  Values
1  0  1  2
2  5  3  3  4  4
3  7  5  5  5  6  6  6
4  27  7  7  7  7  8  8  8  8
5  37  9  10  10  10  9  10  9  9  9  10
6  78  11  11  11  11  11  11  12  12  12  12  12  12
7  92  13  14  13  14  13  14  13  14  13  14  13  14  13  14
8  100  15  16  16  15  16  15  15  15  16  15  15  16  15  16  16  16
9  108  17  17  18  17  18  18  17  17  17  18  18  17  18  17  17  18  18  18

Figure 3: The periodic behaviour of the kth subdiagonal, k = 1, 2, . . ..

Proof: The proof is by induction on k. The base case k = 0 is both degenerate and trivial – we use as the base of our induction that the diagonal is populated exclusively by 0’s.

Suppose that k > 0 and the result holds for all smaller k. Then we may choose A_{0} sufficiently large so that for all a ≥ A_{0}:

{p(a + j, a) : −k < j < k} = {0, 1, …, 2k − 2}

It suffices to establish that for some B, and all a ≥ B,

p(a + k, a) ∈ {2k − 1, 2k}.

For, if this holds, then also p(a + k, a + 2k) ∈ {2k − 1, 2k}, and so:

{p(a + k, a), p(a + k, a + 2k)} = {2k − 1, 2k}

since the second element of this set is obtained by filling in missing values from the part of its column below the diagonal, and the value of p(a+k, a) is not missing! As the value table is symmetric, extending this observation shows that the values:

p(a + k, a), p (a + 2k, a + k), p(a + 3k, a + 2k), ⋯

alternate between 2k − 1 and 2k which establishes both the 2k-periodicity, and the final part of the claim.

Choose A_{1} ≥ A_{0} such that for all a ≤ A_{0}, the regime of regular increase in the values p(·, a) begins at some point c_{a} < A_{1}, and such that for such a the values p(A_{1}, a) > 2k. We now claim that if a > A_{1} + k and b > a + k + 1 then

p(a, b) ∉ {2k, 2k − 1}

that is, the values 2k − 1 and 2k in row a occur in either the kth or (k + 1)st super or subdiagonal (the claim above refers only to subdiagonals, but the alternative follows by symmetry). For suppose that b − a > k + 1. Then, the values from 0 through 2k − 2 occurred before the kth subdiagonal and, since having passed the k − 1st subdiagonal in row a, there have been at least two opportunities to fill in the values 2k − 1 and 2k (if they did not already occur), so there is no chance of them occurring at (b, a). In fact, this also establishes that the value 2k − 1 must occur in the kth sub or superdiagonal of each row beyond a certain point.

We wish to show that beyond some point there are no entries in the kth subdiagonal which are not either 2k − 1 or 2k. For convenience let us refer to the values 2k − 1 and 2k as small, and other possible values as large (they must be larger, for the values which are smaller still occur within the region enclosed by the kth sub and superdiagonals.)

Claim 1 If p(a + k, a) is small, then so is p(a + 3k + 1, a + 2k + 1).

Since p(a + k, a) is small, in the (a + k)th column both the small values will occur on or below the kth superdiagonal. So the value p(a + k, a + 2k + 1) is large. But this means that in the (a + 2k + 1)st row, there is only one place above the diagonal where a small value can occur, and so the value in the kth subdiagonal here, i.e. p(a+3k +1, a+2k +1) is small. So, once we have a small element in the kth subdiagonal, we get further small elements at intervals of 2k + 1.

Claim 2 If p(a + k, a) = 2k − 1 then p(a + 3k, a + 2k) = 2k − 1.

For, granted the assumption, p(a + k, a + 2k) ≠ 2k − 1, so 2k − 1 must occur in the kth subdiagonal of row a + 2k. Thus the occurrences of 2k − 1 in the kth subdiagonal are 2k-periodic.

These two claims suffice to show that eventually the kth subdiagonal consists entirely of small elements. For, by claim 2, the set of those a such that p(a + k, a) = 2k − 1 is closed under addition of 2k, while by claim 1, the set of a such that p(a + k, a) is small is closed under addition of 2k + 1. Since 2k and 2k + 1 are relatively prime, these two things can occur only if eventually all the elements are small.

The argument of the third paragraph of this proof then shows that the complete proposition holds.

We note that the proof in fact establishes a slightly stronger result, namely that the periodic behaviour of the kth subdiagonal begins immediately after the last occurrence of a large element. Furthermore, though presented for clarity as a proof by contradiction, the proof can be changed into a constructive proof as follows. Let A_{0} be as in the proof. If we take A_{1} = A_{0} + 2k + 1 then the value of all cells (c, d) with c < A_{0} and d > A_{1} will exceed 2k (since more than 2k values above the diagonal have been filled in). The proof then establishes that if p(d + k, d) is large, then p(d − k, d) = 2k − 1. Now the two claims establish that the 2k-periodicity of the kth sub-diagonal begins not after 2k(2k +1)+A_{1}. This provides a cubic (in k) bound for the onset of periodicity.

Obviously the table of Sprague-Grundy values for this game has a number of other interesting features and patterns. For example consider the behaviour of the values in a row to the left of the diagonal, beginning from the leftmost column. The cell to cell changes form a sequence:

0, −1, 0, 0, −1, −1, 0, 0, −1, +1, −1 ⋯

and since these cells lie (eventually) in the regions of regular increase for the corresponding columns, these differences remain fixed. What is the rule governing the terms of this sequence? As another example, we might well ask at what point in each row does the regime of regular increase begin?

The observations about regularity etc., which we have made mean that the process of calculating the complete table of values p(a, b) for a and b less than some pre-set bound can be carried out considerably more quickly than by tabulating the values of the options of a given position, and computing the mex. However, they do not provide an algorithm for computing an individual value of p(a, b) which is significantly faster than computing the relevant portion of the table. So we have:

Problem: Find, if possible, an algorithm for computin p(a, b) whose running time is polynomial in log a + log b.

For three or more heaps, the Sprague-Grundy values of greedy Nim become extremely complicated. The ideas of the proof above can be used to show that there are regions of regularity, and to provide some indication of patterns within the irregular regions, but any overall pattern seems difficult to find. All the variations of greedy Nim which we have discussed illustrate the same sort of features, which is why we have chosen to concentrate our exposition of Sprague-Grundy values to this one particular case.

Another game in which the values p(a, b) are important. This game is played on a quarter infinite chess board, initially populated by a number of pieces. These pieces may be moved like rooks, but only towards the edge of the board from which they are most distant. Then the value p(a, b) is precisely the Sprague-Grundy value of a piece on square (a, b).

Acknowledgments

We would like to thank an anonymous referee for very thorough and constructive comments which improved the presentation of the paper significantly.

References

[1] Michael H. Albert and Richard J. Nowakowski. The game of End-Nim. Electron. J. Combin., 8(2):Research Paper 1, 12 pp. (electronic), 2001.

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

[3] Andreas Dress, Achim Flammenkamp, and Norbert Pink. Additive periodicity of the Sprague-Grundy function of certain Nim games. Adv. in Appl. Math., 22(2):249–270, 1999.

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

[5] A.S. Fraenkel. Two-player games on cellular automata. in More Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, July 10–28, 2000, Berkeley, CA(R. J. Nowakowski, ed.), Cambridge University Press, Cambridge, 2002, pp. 279–306.

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