Things You'll Need:
- 25-35 small objects (coins, pebbles, etc.)
-
Step 1
A number of small objects (can be anything, like coins or pebbles) are separated into groups (or rows). There can be any number of groups and any number of objects per group. However, beginning a game with 25 to 35 objects separated into 3 groups will make a good game. You can let your opponent set up the starting configuration and choose who makes the first move. This will show that you aren’t manipulating the start of the game in your favor.
-
Step 2
The players take turns removing any number of objects from one group only. A different group can be selected for each turn, but only one group per turn. At least one object must be removed; a player cannot pass on a turn or take zero objects. Play continues until there are no more objects.
-
Step 3
There are two possible objectives to win the game: Make your opponent take the last turn (remove the last object(s)) or take the last turn yourself. The former is more difficult to determine a winning strategy, so we’ll look at how to win by being the player who takes the last turn.
-
Step 4
You will need to know how to convert decimal numbers (our standard method of counting using digits 0 - 9) into binary numbers (using digits 0 and 1), and vice versa. Without going into a thorough explanation how to do these conversions, we’ll learn conversions for playing a game of Nim with 3 groups and from 1 to 15 objects per group. This will simplify the conversions to a relatively small range of numbers (2-digit decimal numbers 0 - 15 and 4-digit binary numbers 0000 - 1111).
-
Step 5
Step-by-step conversion of decimal number 0 - 15 to 4-digit binary number…
Is the decimal number equal to or greater than 8?
- Yes: The 1st digit of the binary number is 1. Subtract 8 from the decimal number.
- No: The 1st digit of the binary number is 0.
Is the remaining decimal number equal to or greater than 4?
- Yes: The 2nd digit of the binary number is 1. Subtract 4 from the decimal number.
- No: The 2nd digit of the binary number is 0.
Is the remaining decimal number equal to or greater than 2?
- Yes: The 3rd digit of the binary number is 1. Subtract 2 from the decimal number.
- No: The 3rd digit of the binary number is 0.
The 4th digit is whatever is left, 0 or 1. -
Step 6
Example: Convert decimal 10 to a 4-digit binary number…
10 is greater than 8, so the 1st digit of the binary number is 1 and you subtract 8 from 10 to get 2.
2 is less than 4, so the 2nd digit of the binary number is 0.
2 is equal to 2, so the 3rd digit of the binary number is 1 and you subtract 2 from 2 to get 0.
0 is left over. This is the 4th digit of the binary number, which is 1010. -
Step 7
Step-by-step reverse conversion of a 4-digit binary number to a decimal number…
Multiply 1st binary digit by 8.
Multiply 2nd binary digit by 4 and add to above.
Multiply 3rd binary digit by 2 and add to above.
Add 4th binary digit to above. -
Step 8
Example: Convert binary 1010 to a decimal number: 1 x 8 + 0 x 4 + 1 x 2 + 0 x 1 = 10
-
Step 9
To calculate your winning moves, convert the number of objects in each group to binary. Add them together like this example with 3 groups of objects below…
-
Step 10
group 1: decimal count =11, binary count = 1 0 1 1
group 2: decimal count = 7, binary count = 0 1 1 1
group 3: decimal count = 5, binary count = 0 1 0 1
total (add columns) . . . . . . . . . . . . . . . = 1 2 2 3 -
Step 11
Note that two of the digits in the total are odd (1 and 3) and two are even (2 and 2). This is very important… The correct move is to take away objects from one group to make all 4 digits in the total even numbers. If one or more digits are odd, there is ONE AND ONLY ONE possible move that will make all the digits even. If all digits in the total are even, ANY move will make one or more digits odd.
-
Step 12
If you get your turn with at least 1 odd digit in the total, you must find the one move that will make them all even. Then your opponent’s next move will surely make one or more digits odd. Now think about this for a second… If you always make all the digits even, eventually the last move (and game-winner) will be when you make the total equal 0000. The only way your opponent will win is if he/she always makes the correct move from knowing this winning strategy or from dumb luck (highly unlikely).
-
Step 13
Reconsider the example above. The first digit of the group 1 binary count must be changed from 1 to 0 so that the column 1 total is 0 (even). Now you know that group 1 must be changed, but what should it be? Think of what digits in the group 1 binary number will add up with groups 2 and 3 so that the total has all even digits. The answer is 0010. Convert that to decimal (0 x 8 + 0 x 4 + 1 x 2 + 1 = 2), and your move is to take 9 objects from group 1 leaving 2. Now the example looks like this…
-
Step 14
group 1: decimal count = 2, binary count = 0 0 1 0
group 2: decimal count = 7, binary count = 0 1 1 1
group 3: decimal count = 5, binary count = 0 1 0 1
total (add columns) . . . . . . . . . . . . . . . = 0 2 2 2 -
Step 15
Note that all the digits of the total are even. No matter what move your opponent makes, one or more of those digits will be odd. Let’s pretend that your opponent’s move is to take 3 from group 2. Our sample game now looks like this…
-
Step 16
group 1: decimal count = 2, binary count = 0 0 1 0
group 2: decimal count = 4, binary count = 0 1 0 0
group 3: decimal count = 5, binary count = 0 1 0 1
total (add columns) . . . . . . . . . . . . . . . = 0 2 1 1 -
Step 17
Now what is your move? You should take 1 object from group 1…
-
Step 18
group 1: decimal count = 1, binary count = 0 0 0 1
group 2: decimal count = 4, binary count = 0 1 0 0
group 3: decimal count = 5, binary count = 0 1 0 1
total (add columns) . . . . . . . . . . . . . . . = 0 2 0 2 -
Step 19
Whatever your opponent does, the total will have at least one odd digit. Just keep making the right move to make all the digits even and you’ll win the game.
-
Step 20
If you start a game with more than 3 groups, the same principles apply as for 3 groups. You will just have more binary numbers to add up. If you start a game with more than 15 objects in a group, you can either…
- learn about converting larger numbers from decimal to binary (and vice-versa), or
- make any moves without calculating the winning moves until all the groups have 15 or less objects. Then make the strategic move to take control of the game and eventually win.
