Problem of the Month (November 2000)

The game of NIM is well known. The game is played with piles of counters. The two players take turns removing any number of counters from any one pile. The player who last takes a counter wins.

The strategy of NIM is not as well known. Express each pile in base 2, and add these piles without carrying. You can win if you can leave a position whose nim sum is 0. For example, if it is your turn to play from piles of 5, 6, and 7, you can take 4 from any pile and win since:

   1     101     101
 110      10     110
+111    +111    + 11
 ---     ---     ---
 000     000     000

This month we explore some variants of NIM. For each game, what are some winning positions? Can you classify all winning positions? Can you give a winning strategy?

End NIM: The piles of counters are in a line, and players must take counters from one of the two piles on the ends.

Adjacent NIM: The piles of counters are in a line, and players must take counters from a pile adjacent to the pile just taken from.

Veto NIM: Each turn, your opponent can veto one of your proposed moves.

Double NIM: Each turn, you must take counters from two different piles.

Large NIM: Each turn, you must take counters from the largest pile.

Small NIM: Each turn, you must take counters from the smallest pile.

What are some other interesting NIM variants?

ANSWERS

We will follow Winning Ways (Berlekamp, Conway, Guy) and call winning positions P positions (since the Previous player wins), and call losing positions N positions (since the Next player wins). To classify P and N positions, note that every move from each P position must be to an N position, and there must exist some move from each N position to a P position.

End NIM:

Trevor Green and Philippe Fondanaiche found these P positions:

a, a
a, b, a (with a≠b)
a, b, b, a
a, b, c, a (with a<b<c or b<c<a)
a, b, c, a+1 (with b≤a<c)

Trevor Green claims that it is easy to determine whether a position is P or N inductively. Almost all the cases are handled by these rules:

If L, . . . , R is a P position, then so is a, L, . . . , R, a.

If L, . . . , R is an N position and L≤R, then a, L, . . . , R, a is a P position if a<L or a>R, and a, L, . . . , R, a+1 is a P position if L<a<R–1.

Claudio Baiocchi proved that in any P position, the piles on the ends differ by at most one counter. His proof: Let L be the left pile and R<L–1 be the right pile, with [L,X,R] being a P position. Then, for any 1≤L'<L, the position [L',X,R] is an N position. Thus, for any L' there exists a unique R'<R such that [L',X,R'] is a P position. since the same R' can not be effective for two L', the assumption R<L–1 brings to a contradiction.

Adjacent NIM:

Philippe Fondanaiche found these P positions:

a, a
a, a+b, b

He suggests that a good strategy for a more general position is to choose your first move in the odd numbered or even numbered piles, whichever are more numerous, therefore giving you more options later on.

Veto NIM:

These are some P positions I have found:

a (with a≤1)
a, a+1
a, a, a
a, b, a+b+1

Claudio Baiocchi points out and proves that given any position, there are exactly two values of another pile which we can add to it to make a P position.

Double NIM:

Trevor Green found the following winning positions:

a
a, a, a, b (with b≥a≥1)
1, a, a, a, a (with a≥1)
1, a, a+1, a+1, b (with a even and b≥a+1)
2, a, a, a, a (with a even)
2, a, a+1, a+1, a+1 (with a = 0 or 1 (mod 4), and b≥a+2)
2, a, a+2, a+2, b (with a = 0 or 1 (mod 4), and b≥a+2)

Philippe Fondanaiche found the P positions with 4 or fewer piles.

Large NIM:

Trevor Green and Claudio Baiocchi found that the P positions in this game are those that have an even number of largest piles. The proof is simple: First note that from each P position, every legal move results in an N position, since you are decreasing the number of largest piles by 1. Secondly, note that from every N position has a move to a P position. Every such move works when there is more than 1 largest pile. When there is only 1 largest pile, say the second largest pile is n piles of k. You can either make the largest pile k (when n is odd), or remove the largest pile altogether (when n is even), and either move results in an even number of new largest piles.

Philippe Fondanaiche found the P positions with 3 or fewer piles.

Small NIM:

Trevor Green, Claudio Baiocchi, and Philippe Fondanaiche found that the P positions in this game are those containing an odd number of piles containing 1 counter. The proof is again simple: From each P position, you can only take a pile of 1, resulting in an N position. From each N position there is some move to a P position. Those with 2 or more piles of 1 can move to one less pile of 1 counter. Those with no piles if 1 can reduce the smallest pile to a pile of 1.

Cyclic NIM:

This NIM variant was suggested by Trevor Green. This is the NIM game where the piles are linearly ordered, you can only take counters from the first pile, and the remains of that first pile are placed at the end. The P positions found so far are:

a, b (with a≤b)
1, a, b (with a>b)
a, b, 1 (with b>1)
1, 1, a, b (with a≤b)
a, 1, 1, b (with a≤b)
a, b, 1, 1 (with a≤b)
1, a, b, c (with a>1 and c>1)
2, a, b, c (with a>1 and c>1)

Last NIM:

This NIM variant was suggested by Claudio Baiocchi. This is the NIM game where you must take counters from the last pile of counters if that pile still exists. The P positions are exactly those in Small Nim, those containing an odd number of piles containing 1 counter.

Non-Last NIM:

This NIM variant was also suggested by Claudio Baiocchi. This is the NIM game where you cannot take counters from the previous pile touched. In 2023, Xutong Ding proved the P positions are the same as those in Nim, plus any position in which the last pile is the largest pile and removing some counters from that pile is the only winning move in Nim. Misere NIM:

This NIM variant was suggested by Philippe Fondanaiche. This is the NIM game where the player who takes the last counter LOSES. The P positions are exactly those in Nim, except that an odd number of piles of 1 counter is a P position, and an even number of piles of 1 counter is an N position.

Bounded NIM:

This NIM variant was also suggested by Philippe Fondanaiche. This is the NIM game where the players cannot take more than N counters from a pile. To determine whether a position is P or N, find the remainder of each pile upon division by N+1, and add these in base 2 without carrying. If the result is 0, it is a P position.

Fibonacci NIM:

This NIM variant was also suggested by Philippe Fondanaiche. This is the NIM game played with one pile where the players cannot take more than twice the amount of counters taken by the previous player. The first player must take either 1 or 2 counters.

Claudio Baiocchi told me how to classify a pile of n counters as P or N. Start with n, and subtract off the biggest Fibonacci number possible. repeat this until you get zero. The position is N if the last number subtracted is 1 or 2, and P otherwise.

Specker's NIM:

This NIM variant was suggested by Panayiotis. This is the NIM game in which you must pick two piles of sizes A≤B, remove some counters from A, and add some counters to B.

He proves that the game always ends, but can last arbitrarily long if the players don't care about winning. He finds the P positions with 5 or fewer piles are those containing an odd number of piles, where all but the largest pile are in pairs.

Sorted NIM:

This Nim variant was suggested by Krzysztof Solyga. The piles are arranged from left to right, and each pile must contain at least as many counters as the pile to its left.

Zsbán Ambrus mentioned the book by "Diszkrét Matematikai Játékok", Polygon, Szeged, 1998 by Csákány Béla, which covers Nim and some variants.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 11/17/08.