The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math


Date: 09/26/2000 at 03:26:40
From: Winarto
Subject: Nim

What is the principle of Nim, and what is its application?

Date: 09/26/2000 at 09:53:39
From: Doctor Anthony
Subject: Re: Nim

1) You have three piles of coins, say 3 in the first pile, 4 in the 
   second pile, and 5 in the third pile.

2) You alternate turns withdrawing one or as many coins found in any 
   given pile. You may withdraw from only one pile at a time. For 
   example: In the first pile, you or your opponent can withdraw 1, 2, 
   or 3 coins... and the same with the other two piles.

3) The person who is left to draw the last coin loses.

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:

     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 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   
Associated Topics:
High School Discrete Mathematics
High School Puzzles

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.