The Gray Monk

« A slight bump .... | Main | Theatre on the lawn »

July 29, 2006

The Secrets of NIM

Ever heard of NIM? It is a fascinating game for two players. It can be played anywhere and at any time because it requires very little preparation. All you need is a handful of small things like pennies, pebbles, sea shells, tooth picks - whatever you like. The beauty of the game is that there is a mathematical theory behind it and the player who understands the underlying principles will almost always win.

Let's choose pebbles to play with. First you arrange your pebbles in any number of piles wiht any number of pebbles in each pile. The the players start the game by alternately drawing any number of pebbles - but at least one - from any, but only one pile. That means, one player may take away a whole pile, a part of or only one pebble from that pile. The player who draws last wins.

Now, how do you know you are in a 'win' or 'lose' situation? For simplification let there only be one pebble in each pile. Apparently the player who succeeds in leaving an even number of pebbles for his opponent to draw from will win. For example, if 4 piles are left with 1 pebble each, the player who takes the first of the remaining 4 pebbles will lose. If 2 piles with 2 pebbles each are left, again the player who takes the first pebble or pebbles will lose. If he takes 1 pebble the other player will take one pebble from the other pile and win, and if he takes a whole pile his opponent will win even quicker.

The real game can be slightly more complicated. To find out if you are in a winning or losing position simply write down the number of pebbles in each pile in the binary system. Then add them up in the ordinary decimal way. If all digits of the resulting sum are even it is a winning otherwise a losing position.

4 pebbles in 2 piles: a winning position

2  1 0
2  1 0
    2 0

6 pebbles in 3 piles: a winning position

1    1
2  1 0
3  1 1
    2 2

8 pebbles in 3 piles: a losing position

1        1
3     1 1
4  2 0 0
    2 1 2

Taking away any number of pebbles from one pile will obviously change the parity (oddness or evenness) of at least one column of the sum. Thereby it is possible to change a 'lose' into a 'win' situation. 8 pebbles in 3 piles (1,2,4) is a lose situation but taking away 2 pebbles from pile three will turn it into a win situation (1,3,2). See?

Have fun trying this out on your unsuspecting opponent....

Posted by Mausi at July 29, 2006 07:27 AM

Trackback Pings

TrackBack URL for this entry:
http://mt3.mu.nu/mt/mt-tb.cgi/4532