Nim
Problem
Describe the strategy for winning the game of Nim. The rules are simple. Start with any number of counters in any number of piles. Two players take turns to remove any number of counters from a single pile. The loser is the player who takes the last counter.
Getting Started
Chance plays no part, and each game must end. The only advantage that either player can possibly have is to start or to play second. To work out how to win you need to start by analysing the 'end game', and the losing position to be avoided, and then work back to earlier moves.
Student Solutions
Chance plays no part, and each game must end. The only advantage that either player can possibly have is to start or to play second. To work out how to win you need to start by analysing the 'end game', and the losing position to be avoided, and then work back to earlier moves. What should you do if there are only two piles? If there are more piles, what happens if you reduce all the piles to one counter in each?
This is how you gain control of the game. Make a list of the binary numbers for the number of counters in each pile. Now to have control of the game you want to make the number of 1's in each column even. Whatever your opponent does, when you record the new binary number for the pile that has been changed, there will be an odd number of 1's in one or more of the columns. You will be able to make all the 'column sums' even again.
For example if the numbers of counters in the piles are 7, 6, 4 and 1 you get
| 1 | 1 | 1 |
| 1 | 1 | 0 |
| 1 | 0 | 0 |
| 1 |
A good move now is to take 4 counters from the pile of 7 which makes the number of 1's in each column even.