Associated Topics || Dr. Math Home || Search Dr. Math

### Nim

```
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:

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 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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search