Return to my Puzzle pages
Go to my home page
© Copyright 1999, Jim Loy
Nim is a game in which you have two or more piles (or containers) of objects (marbles, beans, whatever). The two players alternate moves, taking any amount of objects from only one pile, in any one move. The object of the game is to be the last player to take any objects. Here is a sample game, with 18, 11, 9 objects in three piles:
#1 #2 #3 18 11 9 1. player #1 takes 16 away from pile #1 2 11 9 2. player #2 takes 2 away from pile #3 2 11 7 3. player #1 takes 6 away from pile #2 2 5 7 4. player #2 takes 1 away from pile #1 1 5 7 5. player #1 takes 3 away from pile #3 1 5 4 6. player #2 takes 2 away from pile #3 1 5 2 7. player #1 takes 2 away from pile #2 1 3 2 8. player #2 takes 1 away from pile #2 1 2 2 9. player #1 takes 1 away from pile #1 0 2 2 10. player #2 takes 1 away from pile #3 0 2 1 11. player #1 takes 1 away from pile #2 0 1 1 12. player #2 takes 1 away from pile #2 0 0 1 13. player #1 takes 1 away from pile #3, and wins.
Where did player #2 go wrong? Actually, his mistake was letting his/her opponent go first. Player #1 had a win from the first move. Can you figure out player #1's winning strategy?
You may notice that after player #1 has moved, one pile is equal to the sum of the other two piles. This is not the solution to the puzzle. But it is a clue. At the first move, player #1 could have taken two objects from either pile #2 or pile #3, and made these two piles total up to pile #1. Either of those moves would have lost the game.
The winning strategy is to imagine the three piles in binary:
#1 #2 #3 10010 01011 01001
Here there are 2 ones, 2 twos, 0 fours, 2 eights, and 1 sixteen. You would like to have an even number of each of these. So, 1 sixteen must go. That is why player #1 took 16 from pile #1. On player #1's next move, this is the situation"
#1 #2 #3 00010 01011 00111
Here there are 2 ones, 3 twos, 1 four, and 1 eight. We cannot get rid of an eight, a four, and a two. None of the piles has that many objects. Instead we take 6 from pile two. That changed the eight into a four, and got rid of a two. Do you see that? We wanted to change the parity (odd or even) of an eight, a four, and a two. One way to do that is to change the eight into a four, and get rid of a two.
It is easy to think of variations of this game. We can limit the number of objects taken, we can play with three or more players. We can make it so that the last player to take an object loses.
A much simpler game is to have one pile of objects, and restrict the number that you can take. Let's say we start with 40 objects, and we can take from 1 to 6 objects in one move. Again, we win by taking the last objects. This one works well by working backward. On our last move, we would like to have 1 to 6 objects, so we can take all of the objects. The only way we can guarantee that is if we had left our opponent 7 objects to choose from. That means that on our next to last move, we left him/her with 14 objects, and 21 the previous move, and 28, and 35. So we take five objects on our first move. We then base our move on his/her move, each time.
If we modify the rules slightly, so that the object is to make the opponent take the last pieces, then we want to leave one piece for the opponent to take at the end. So we start by taking four pieces on our first move. The game proceeds much as before (our opponent is left with 36, 29, 22, 15, 8, and 1 object.