NIM

I often used the game of NIM in my computer programming classes and even in my math classes (when we studied number bases).   I would play against the whole class (and offer to cancel homework if they could beat me in two out of three games).

Rules:
The game board consists of rows of objects.
The players take turns removing any number of objects from a single row.
You must select at least one object.
The last player to move wins the game.
(Some versions of NIM have the last player to move lose the game)

I often use the following configuration for the board:

		/ / /
		/ / / / /
		/ / / / / / /
		/ / / / / / / / /


What is the strategy for playing?

1. You must first represent each row of objects as a binary number.
2. Then, when it is your turn, you must make your move so as to leave your opponent with
      an even number in each column (in binary notation).
3. Once you leave your opponent with an even number in each column, your opponent must give
      you a board with at least one odd column.
4. You can then convert it back to all even columns to assure your victory.


Example:
Let's use the configuration above for the opening board (4 rows -- 3, 5, 7, and 9 objects).
Here are the base two representations of the four rows at the start of the game:

Number in Row     8        4        2        1    
3 = 0 0 1 1
5 = 0 1 0 1
7 = 0 1 1 1
9 = 1 0 0 1

Note that the 8s column has an odd number of ones;
the 4s column has an even number of ones (there are 2);
the 2s column has an even number of ones (there are 2);
the 1s column has an even number of ones (there are 4).
So, if you are moving first, you can assure yourself of victory by removing 8 objects from row 4.
This leaves your opponent with an even number of ones in each column. (see the table below)

Number in Row     8        4        2        1    
3 = 0 0 1 1
5 = 0 1 0 1
7 = 0 1 1 1
1 = 0 0 0 1

Let's assume that your opponent removes 6 objects from row three.
Then the board looks like this (in base 2):

Number in Row     8        4        2        1    
3 = 0 0 1 1
5 = 0 1 0 1
1 = 0 0 0 1
1 = 0 0 0 1

Note that your opponent has left you with a board containing odd columns in the 4s column and the 2s column.   You must get the board back to an even number of ones in each column.   Since the odd ones are in different rows, you can't remove them both.   Your move should be to work on row two (the row that contains a one in the column with the larger heading (the 4s column)).
You want to remove the one in the 4s column and put it back in the 2s column.
Hence, you want to subtract 4 but add back 2 for a net removal of 2, leaving 3 objects in row 2.
Then the board looks like this (in base 2):

Number in Row     8        4        2        1    
3 = 0 0 1 1
3 = 0 0 1 1
1 = 0 0 0 1
1 = 0 0 0 1

Note that you have again left your opponent with an even number of ones in each column!
Continue to play in this manner, always leaving your opponent with an even number of ones in each column, and you will win the game.

Links:

Click here for a non mathematical explanantion of NIM

Math Games

Mr. P's Puzzles and Games Page