The Game of NIM

 Here are the rules for one 
 version of the game of NIM: 

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

If you are presented with the 
following board, consisting of 
four rows, what should your 
opening move be to ensure a win?

Row 1:  O O O 

Row 2:  O O O O O

Row 3:  O O O O O O O

Row 4:  O O O O O O O O O



Answer

The answer is to remove 8 objects
 in row 4.

Explanation:
Think of the powers of two:
1, 2, 4, 8, 16, ... , which 
correspond to 2⁰, 2¹, 2², 2³, 2⁴, 
... 

You need to take each row and 
divide it into groups in the 
following way:

(1) First, find the highest 
power of 2 that is contained 
in that row. 

In our example, two is the 
highest power of 2 contained 
in Row 1, four is the highest 
power contained in Row 2, four is 
also the highest power contained 
in Row 3, and eight is the highest 
power of 2 contained in row 4.

(2) Then find the next highest 
power of 2 that is contained in 
the remaining objects, and 
continue in this manner until 
all objects are in a group.

In our example, here are the 
groupings for each row:

Row 1:		2	1

Row 2:		4	1

Row 3:		4	2	1

Row 4:		8	1

In order to win the game of 
NIM, you need to present your 
opponent with an even number of 
each of the groups (1, 2, 4, 8, 
16, ...).  In the example above, 
there are four groups of 1, two 
groups of 2, two groups of 4, 
and one group of 8.  So, your 
move should be to eliminate the 
one group of 8 by removing eight 
of the nine objects in Row 4.

Now, your opponent will leave you 
with a board consisting of at 
least one odd numbered group, so 
you need to "even up" the groups 
again.  

For example, let's say that your 
opponent removes all of Row 3.  
Then the board would have the 
following groupings:

Row 1:		2	1

Row 2:		4	1

Row 3:		 

Row 4:		1

It appears that you need to remove 
a group of 4, a group of 2 and a 
group of 1 in order to present 
your opponent with an even number 
of the 1s group.  

But you can only remove objects 
from one row.  

So, actually, you will work on 
Row 2 because it has the group of
4, and there is only one of that 
group.  

So, in Row 2, you will need to 
remove the 4 and the 1 but you 
must leave a 2.  

Therefore your move should be to 
remove three (4 + 1 - 2) objects 
from Row 2.  
	
This leaves the following groups:


Row 1:		2	1

Row 2:		2

Row 3:		

Row 4:		1

Continue to play, leaving your 
opponent with an even number of 
each power of 2, and you will win.