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 20, 21, 22, 23, 24, ... 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.


Send any comments or questions to: David Pleacher