Nim (Part 2) - harder

So, how can you figure out the solution to the more complex 'nim' game? (See my previous post for info on the game).

It's actually amazingly simple (well - somewhat simple) but needs a bit of background in binary numbers to appreciate.

First, a reminder that a binary number is composed of a 'ones' column (the right-most digit in the number), then a 'twos' column, then a 'fours' column, etc, like below:

So this is 1 'four' plus 0 'two' plus 1 'one' = 5 (in decimal)

In decimal of course, we have the 'ones' column, 'tens' column, etc, like below:

And this would be 1 'hundred' plus 1 'one' = 101 (in decimal)

Now for the solution. All you do is write out the number of toothpicks in each pile in binary, one below the other. Then add up the columns to see whether each column is even (0, 2, 4, etc) or odd. Finally, if all column sums are even then we call the overall sum 'even'. Everything else will be 'odd'.

Two things that I will note (but not prove):
1. If the overall sum is 'even', then if you take 1 or more toothpicks from any pile you will make the overall sum 'odd'.
2. If the overall sum is 'odd', then there is always a way to take away from one pile so that you make the overall sum 'even'.

So if you can make the sum 'even' on your turn, you can also always do that on your next turn since your opponent will always make it 'odd' on their turn.

a) If you follow this strategy you will win the game where the last person to take a toothpick wins.

Here's an example with three piles of 3, 5 and 8 toothpicks respectively:

Pile 1 (3)	0	1	1
Pile 2 (5)	1	0	1
Pile 3 (8)	1	0	0
	Even	Odd	Even

If you take away 2 from pile 1 you change it from binary 011 to binary 001 and now the sum of all the columns is even. If you keep this up, you will always leave toothpicks in at least 2 piles until you force your opponent to take the second-last pile and you then take the last one.

b) If you are playing the more common version of nim where the person to take the last toothpick loses, then play as above until only one heap has a size of 2 or more. Then remove all toothpicks from the larger heap and you win.

Finally, if you are playing a version of the game where you can only take away up to 'k' toothpicks at a time, then first (in your mind) reduce the size of each heap modulo k + 1 (that is, remove all multiples of k + 1 until you just have a remainder that is between 1 and k). Assuming that you are playing the 'last person to take a toothpick loses' version, then:
- If this makes all the heaps of size zero just take k objects from one of the heaps.
-Otherwise, follow the above strategy 'a'.

This is just an intro to nim, but should be enough that the explanations you read elsewhere make sense (e.g. the wikipedia nim entry)