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.
is a known perfect winning strategy to playing NIM. Let's use a simple
example to illustrate how to use this strategy.
say you have three piles with 1, 4 and 7 stones:
out the optimal move, we first express the count of each pile as a binary
number, using this table:
add up these binary numbers a special way:
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
0010 Special Sum
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!