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.
The Game of NIM
