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)

Nim (Part 1) - easy

Nim is "a game in which two players alternately take one or more objects from one of a number of heaps, each trying to take, or to compel the other to take, the last remaining object".

(This post looks at an 'easy' version of Nim and how to solve it. My next post looks at the solution to the harder variants.)

My first experience with Nim was the simple version ('easy') where you start with a pile of (say) 15 toothpicks. You are allowed to take away 1, 2 or 3 toothpicks in your turn and then it is the other player's turn. You continue taking turns until someone has to take the last toothpick (and they lose).

This type of game is pretty easy to analyze. You can see that if you leave your opponent 1 toothpick you win. And if you leave them 1+4 = 5 toothpicks you also win (since if there are 5 toothpicks and they take 'x', you just take '4-x' on your turn and that leaves 1...giving you the win). So the winning strategy is to leave your opponent with 1 + (some multiple of 4) in the pile. If the pile starts with 15 and you get to go first, take 2 (leaving 13 = 1 + 4(3)) and you are already in a winning position.

Finally, if you are allowed to take 'k' toothpicks on each turn, then just leave 1 + some multiple of (k+1) toothpicks and you win. (And if the rules are that you need to take the last toothpick yourself to win, then just leave 1 + some multiple of k.)

The next variant I had heard of (call it 'hard') extended this game to 3 piles. The version I played had piles of 3, 5 and 8. During your turn you can take 1, 2, or 3 toothpicks from any one pile. Again, the objective of the game was to leave your opponent with the last toothpick.

I'll leave the analysis of this to be a simple case of the 'hardest' case:

• you have any number of piles
• each pile has some number of toothpicks
• during your turn you can take any number of toothpicks from any one pile

What is the winning strategy?

I'll leave this to my next post...but it's actually a fairly easy(!) solution - if you're good at converting numbers to binary and then adding up columns to see if they are even or odd.

Attack (or escape) of the soft plastic bait

Take a look at the picture below:

That's my fishing tackle box, with something strange 'escaping' from the bottom. Taking a closer look:

One of the soft plastic worms that was loose on the bottom of my tackle box has eaten through the plastic base!

At first I thought it was melted by heat - maybe I had left some matches in there and they caught fire, or it had rested against something hot - but there is also damage to a different plastic container that contained some soft bait.

You can see in this picture that the worm on the right, and some of the bait on the left have started to dissolve through the clear plastic container. The picture below shows the right side a little better.

Seems a little bizarre to say the least...and I have to admit that these have been in my tackle box for probably close to 30 years(!) so they have had time to plan and execute their escape.

(Update: OK - closer to 40 years but don't tell anyone)

Checking the internet, this discussion makes sense...the compound that keeps the bait soft can also eat away at other plastic (like your tackle box).

Tough Terrans

It seems that in most Science Fiction stories the aliens are much tougher than we poor earthlings and we're forever being terrorized by them.

However, I remembered a couple of stories from many years ago where we were the tough ones.

One was "With Friends Like These" (Alan Dean Foster) which was about aliens coming to Earth to ask for our help (after previous generations had finally beaten back we expansionist earthlings to our home planet and surrounded it with a force field that could only be broken from the outside). Pretty lightweight but humorous. Available online but the free places seemed like they may not have the author's permission so I can mention iTunes as a possibility (or find an old second-hand copy of the book of short stories with the same title).

Another one was "Danger - Human" (Gordon Dickson...the first short story he had published I think) where aliens who are worried about earthlings (because they found out that every 'n' hundred thousand years humans would suddenly expand into the universe and wreak havoc) figure out how to stop the next wave of us taking over the galaxy. Or not. It's available at the following link: http://www.baenebooks.com/chapters/0743471741/0743471741___1.htm

Terrans rule!

Super Smell

As I slowly worked my way into the 21st Century - technology-wise that is - I started listening to podcasts on my cool, new technology ipod nano.

OK, I was using the cast-off from one of my boys, but it seemed to be an improvement over my previous music player.

(Though I have to admit this is still pretty cool looking...just doesn't have the functions)

Getting back to the 'super smell' part of this post, I've been listening to Quirks and Quarks podcasts on the aforementioned nano, and there was an interesting one earlier this year about the sense of smell. I had heard (and it seemed to be a common estimate) that we can only distinguish somewhere around 10,000 smells, but is seems that newer research might push that up to trillions!

And smells certainly seem to be able to trigger memories. You don't particularly remember them, but when you smell something specific the memory comes back.

One example I had involving smell occurred about 25 years ago when my older brother and I visited England and did a bit of a tour of 'the relatives'. We were visiting the house where my grandfather's youngest brother and his wife were supposed to be living (we weren't 100% sure that we were at the correct address) but when Albert answered the door he was smoking a pipe, and I instantly recognized it as being the same tobacco blend that my grandfather had smoked! I hadn't smelled it for many years (my grandfather had died many years before this) and would have not been able to describe it (either before or since) but when I smelled it, it instantly brought back a memory of recognition - and sure enough, it was the same blend.