Learn hardcore math and programming through games :-) The Game of Nim

Reference: Introductory Combinatorics, fourth edition, Richard A. Brualdi

Example : The Game of Nim:

It is a return to the roots of combinatorics —- which does lie in recreational mathematics and we investigate the ancient game of Nim. (Nim derives from the German word Nimml, meaning Take!) Its solution depends on parity, an important problem-solving concept in combinatorics. We can use parity argument in investigations of perfect covers of chessboards when we show that a board has to have an even number of squares in order that it have a perfect cover with dominoes.

Nim is a game played by two players with heaps of coins (or stones or beans or gems or diamonds !!! 🙂 🙂 …).. Suppose that there are k \geq 1 heaps of coins that contain, respectively, n_{1}, n_{2}, \ldots, n_{k} coins. The object of the game is to select the last coin. The rules of the game are the following:

i) The players alternate turns (let us call the player who makes the first move I and then call the other player II).

ii) Each player, when it is his or her turn, selects one of the heaps and removes at least one of the coins from the selected heap. (The player may take all of the coins from the selected heap, thereby leaving an empty heap, which is now “out of play.”)

The game ends when all the heaps are empty. The last player to make a move, that is, the player who takes the last coin(s), is the winner. 

The variables in this game are the number k of heaps and the numbers n_{1}, n_{2}, \ldots, n_{k} of coins in the heaps. The combinatorial problem is to determine whether the first or second player wins and how that player should move in order to guarantee a win — a winning strategy.

In order to develop some understanding of Nim, we consider some special cases. (This is an important principle to follow in general: Consider small or special cases in order to develop understanding and intuition. Then try to extend your ideas in order to solve the problem in general.) If there is initially only one heap, then player 1 wins by removing all its coins. Now, suppose that there are k=2 heaps, with n_{1}, and n_{2} coins, respectively. Whether or not player I can win depends not on the actual values of n_{1} and n_{2} but on whether or not they are equal. Suppose that n_{1} \neq n_{2}. Player I can remove enough coins from the larger heap in order to leave two heaps of equal size for player II. Now player I, when it is her turn, can mimic player II’s moves. Thus, if player II takes c coins from one of the heaps, then player I takes the same number c of coins from the other heap. Such a strategy guarantees a win for player I. If n_{1}=n_{2}, then player II can win by mimicking player I’s moves. Thus, we have completely solved 2-heap Nim. An example of play in the 2-heap game of Nim with heaps of sizes 8 and 5, respectively, is

8, 5 \stackrel{I}\rightarrow 5,5 \stackrel{II}\rightarrow 5,2 \stackrel{I}\rightarrow 2,2 \stackrel{II}\rightarrow 0,2 \stackrel{I}\rightarrow 0,0

The preceding idea in solving 2-heap Nim, namely, moving in such a way as to leave two equal heaps, can be generalized to any number k of heaps. The insight one needs is provided by the concept of the base 2 numeral of an integer. Recall that each positive integer n can be expressed as a base 2 numeral by repeatedly removing the largest power of 2 which does not exceed the number. For instance, to express the decimal number 57 in base 2, we observe that

2^{6} \leq 57 < 2^{6}, 57-2^{5}=25,

2^{4} \leq 25 < 2^{5}, 25-2^{4}=9,

2^{3} \leq 9 < 2^{4}, 9-2^{3}=1,

2^{0}\leq 1 <2^{1}, 1-2^{0}=0.

Thus, 57=2^{5}+2^{4}+2^{3}+2^{0},

and the base 2 numeral for 57 is 111001.

Each digit in a base 2 numeral is either 0 or 1. The digit in the ith position, the one corresponding to 2^{i}, is called the ith bit (i \geq 0). We can think of each heap of coins as consisting of subheaps of powers of 2, according to its base numeral. Thus, a heap of size 53 consists of subheaps of sizes 2^{5}, 2^{4}, 2^{2}, and 2^{0}. In the case of 2-heap Nim, the total number of subheaps of each size is either 0, 1, or 2. There is exactly one subheap of a particular size if and only if the two subheaps of each size is even if and only if the two heaps have the same size — that is, if and only if, player II can win the Nim game.

Now, consider a general Nim game with heaps of sizes n_{1}, n_{2}, \ldots, n_{k}. Express each of the numbers n_{i} as base 2 numerals:

n_{1}=a_{s}\ldots a_{1}a_{0}

n_{2}=b_{s}\ldots b_{1}b_{0}

\ldots

n_{k}=e_{s}\ldots e_{1}e_{0}

(By including leading 0’s we can assume that all of the heap sizes have base 2 numerals with the same number of digits.) We call a Nim game balanced, provided that the number of subheaps of each size is even. Thus, a Nim game is balanced if and only if:

a_{s}+b_{s}+\ldots + e_{s} is even,

\vdots

a_{i}+b_{i}+\ldots + e_{i} is even,

\vdots

a_{0}+b_{0}+\ldots + e_{0} is even,

A Nim game that is not balanced is called unbalanced. We say that the ith bit is balanced, provided that the sum a_{i}+b_{i}+\ldots + e_{i} is even, and is unbalanced otherwise. Thus, a balanced game is one in which all bits are balanced, while an unbalanced game is one in which there is at least one unbalanced bit.

We then have the following:

Player I can win in unbalanced Nim games, and player II can win in balanced Nim games.

To see this, we generalize the strategies used in 2-pile Nim. Suppose the Nim game is unbalanced. Let the largest unbalanced bit be the jth bit. Then, player I moves in such a way as to leave a balanced game for player II. She does this by selecting a heap whose jth bit is 1 and removing a number of coins from it so that the resulting game is balanced. No matter what player II does, she leaves for player I an unbalanced game again, and player I once again balances it. Continuing like this ensures player I a win. If the game starts out balanced, then player I’s first move unbalances it, and now player II adopts the strategy of balancing the game whenever it is her move.

For example, consider a 4-pile Nim game with heaps of sizes 7,9, 12 and 15. The base 2 numerals for these heap sizes are, respectively, 0111, 1001, 1100, and 1111. In terms of subheaps of powers of 2 we have:

\begin{array}{ccccc}    \emph{4-pile Nim game} & 2^{3}=8 & 2^{2}=4 & 2^{1}=2 & 2^{0}=1 \\    \emph{heap of size 7}       & 0              & 1                & 1              & 1                \\    \emph{heap of size 9}       & 1               & 0               & 0             & 1                 \\    \emph{heap of size 12}     & 1               & 1                & 0             & 0                 \\    \emph{heap of size 15}     & 1               & 1                & 1              & 1                   \\    \end{array}

This game is unbalanced with the 3rd, 2nd, and 0th bits unbalanced. Player I can remove 11 coins from the pile of size 12, leaving 1 coin. Since the base 2 numeral of 1 is 0001, the game is now balanced. Alternatively, player I can remove 5 coins from the pile of size 9, leaving 4 coins, or player I can remove 13 coins from the pile of size 15, leaving 2 coins.

A quiz:

  1. Consider 3-heap Nim with piles of sizes 1, 2 and 4. Show that this game is unbalanced and determine a first move for player I.
  2. Is 4-pile Nim with heaps of sizes 22, 19, 14, and 11 balanced or unbalanced? Player I’s first move is to remove 6 coins from the heap of size 19. What should player II’s first move be?
  3. Consider 5-pile Nim with heaps of sizes 10, 20, 30, 40, and 50. Is this game balanced? Determine a first move for player I.

Have fun with math games  !

Cheers,

Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s