Formula for Nim

Date: 02/22/2002 at 15:20:56
From: Kentaro Miura
Subject: NIM

Hi.

I have been attempting to figure out a formula for the game called 
the Chip Game. You can play with any number of chips. Each player 
takes turns to eliminate up to three coins at a time. The person to 
take the last chip loses the game. (For example, there are 5 chips. 
The first person takes 1 chip. His opponent takes 3 chips. The person 
that took the first one lost.) 

I have gained the ability to win some games. However, I would like to 
know a complete formula that applies for any number. 

Thank you.

Date: 02/22/2002 at 23:23:03
From: Doctor Twe
Subject: Re: NIM

Hi Kentaro - thanks for writing to Dr. Math.

This is one version of a popular mathematical game commonly called 
NIM. If you type "nim" (without the quotation marks) and select 
"complete words only" in our Ask Dr. Math archive searcher at:

   http://mathforum.org/mathgrepform.html   

You'll find a half dozen answers relating to the game of NIM and its 
variants.

Let's start with a simple game. Assume we play first, and that our 
opponent will play his best possible move each time.

Suppose we start with 4, 3, or 2 coins. What is our strategy? Simple; 
take all but 1 coin. Our opponent has to take the last coin and lose.

Now suppose that we start with 5 coins.
 * If we take 1 coin (leaving 4), our opponent will take 3 - we lose.
 * If we take 2 coins (leaving 3), our opponent will take 2 - we lose.
 * If we take 3 coins (leaving 2), our opponent will take 1 - we lose.
No matter what we do at 5 coins, we lose.

Next, suppose we start with 6 coins.
 * If we take 1 coin, we leave our opponent with 5 - which we showed 
   was a losing position for him.
 * If we take 2 coins (leaving 4), our opponent will take 3 - we lose.
 * If we take 3 coins (leaving 3), our opponent will take 2 - we lose.
So our winning strategy is to take 1 coin, leaving our opponent with 
the losing position of 5 coins.

Suppose we start with 7 coins.
 * If we take 1 coin (leaving 6), our opponent will take 1 - leaving 
   us with 5 - we lose.
 * If we take 2 coins, we leave our opponent with 5 - a losing 
   position.
 * If we take 3 coins (leaving 4), our opponent will take 3 - we lose.
So our winning strategy is to take 2 coins, leaving our opponent with 
the losing position of 5 coins.

Likewise if we start with 8 coins.
 * If we take 1 coin (leaving 7), our opponent will take 2 - leaving 
   us with 5 - we lose.
 * If we take 2 coins (leaving 6), our opponent will take 1 - leaving 
   us with 5 - we lose.
 * If we take 3 coins, we leave our opponent with 5 - a losing 
   position.
So our winning strategy is to take 3 coins, leaving our opponent with 
the losing position of 5 coins.

Now, suppose we start with 9 coins.
 * If we take 1 coin (leaving 8), our opponent will take 3 - we lose.
 * If we take 2 coins (leaving 7), our opponent will take 2 - we lose.
 * If we take 3 coins (leaving 6), our opponent will take 1 - we lose.
No matter what we do at 9 coins, we lose.

Suppose we start with 10 coins.
 * If we take 1 coin, we leave our opponent with 9 - which we showed 
   was a losing position.
 * If we take 2 coins (leaving 8), our opponent will take 3 - we lose.
 * If we take 3 coins (leaving 7), our opponent will take 2 - we lose.
So our winning strategy is to take 1 coin, leaving our opponent with 
the losing position of 9 coins.

We can continue this, but let's put it in chart form:

     # Coins   We take   Leaving
     -------   -------   -------
        1         1         0     We lose.
        2         1         1     Opponent must take it and lose.
        3         2         1
        4         3         1
        5         X         X     Whatever we take, we lose.
        6         1         5     Opponent will lose.
        7         2         5
        8         3         5
        9         X         X     Whatever we take, we lose.
       10         1         9     Opponent will lose.
       11         2         9
        :         :         :

Do you see the pattern? Every fourth number -- 1, 5, 9, 13, ... - is a
losing number. We want to leave our *opponent* with that many coins at 
the start of his turn. To do that, we must get to the nearest losing 
number, and then match his every move. If he takes N coins, we take 
4-N to get to the next losing number.

For example, suppose we start with 20 coins. The nearest losing number 
is 17, so we take 3. Suppose our opponent takes 2, leaving 15. We then 
take 4-2 = 2 to get to the next losing number, which is 13. Suppose he 
next takes 3, leaving 10. We then take 4-3 = 1 to get to the next 
losing number, which is 9. Suppose he next takes 1, leaving 8. We then 
take 4-1 = 3 to get to the next losing number, which is 5. At this 
point, he realizes that he can't win, but takes 1 as a formality, 
leaving us 4. We take 3, and he must take the last one - we win!

Try a few games, and then see if you can find the winning strategy for 
the following variants:

 * Each player may take between 1 and 4 coins. (Or between 1 and N 
   coins.)

 * The player who takes the last coin wins.

 * There are 2 (or more) piles of coins. Each player may only take 
   coins from one pile.

I hope this helps. If you have any more questions or comments, write 
back again.

- Doctor TWE, The Math Forum
  http://mathforum.com/dr.math/   

Date: 02/27/2002 at 16:07:59
From: Doctor Anthony
Subject: Re: NIM

The general approach to the game of NIM is described below.

The technique is to express the number of coins in each pile in binary 
scale and add the coefficients of the various powers of 2. You then 
remove as many coins from some pile or other as necessary to leave the 
sum of the coefficients of each power of 2 an even number. When the 
opponent draws he is bound to upset such an arrangement and you then 
repeat the process. The only exception is that you must not leave an 
even number of piles containing one coin each.

We can lay out the problem as follows, with three piles containing say 
3, 4, and 5 coins respectively

       Pile(1)      Pile(2)      Pile(3)       11  (pile(1) in binary)
       -------      -------     ---------     100  (pile(2) in binary)
        ***         ****         *****        101  (pile(3) in binary)
                                             -----
                                              212   = Sum of columns

We want the sum of each column to be even (or zero) and we can do this 
by making pile(1) = 1 instead of 11. So we reduce pile(1) to 1. This 
means we must take 2 coins from pile(1).  We then get:

       1
     100
     101
    -----
     202   This is now a winning position.

When the opponent takes any coins he is bound to leave some column 
odd, and you can repeat the above calculation to get back to each 
column having an even total. As mentioned before, you must not leave 
an even number of piles with one coin in each (this does give an even 
sum to the column 2^0), and in this case you must leave an ODD number 
of piles with one coin in each pile.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/