NIM STRATEGY

NIM is a simple game involving piles of objects (we will call them "stones"). The objective of the game is to be the person who takes the last stone. In any move, you must take away one or more stones from any single pile.

There is a known perfect winning strategy to playing NIM. Let's use a simple example to illustrate how to use this strategy.

Lets say you have three piles with 1, 4 and 7 stones:

```X

XXXX

XXXXXXX
```
To find out the optimal move, we first express the count of each pile as a binary number, using this table:

 Decimal Binary 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111
Next we add up these binary numbers a special way:
```0001 X

0100 XXXX

0111 XXXXXXX

----------------

0010  Special Sum
```
For any column with an even number of 1's, we put down a zero. For an odd number, we put down a one. In mathematics, this is called the "Exclusive Or". To win, we want to get this sum to total 0000. Looking over the numbers above, it looks like if we took this sum away from the third pile -- changing a 7 (0111 in binary) to a 5 (0101 in binary) -- then the special sum would become 0000.

You continue this operation until you win the game. Of course, if your opponent has left you with a special sum of 0000, then you will lose, assuming perfect play on his part. And you thought math in school was boring!