## Thursday, October 6, 2011

### Tower of Hanoi variant

The Tower of Hanoi is a classic puzzle that looks like this:

Image borrowed from Wikipedia

The idea is to get all the disks from the left rod onto the right rod.  This might seem easy (just dump them out and put them back on the other one), but there are a few rules you have to follow.  First, you can only move one disk at a time, and only from one rod onto another.  Second, no larger disk is allowed to be on top of a smaller disk.

The solution to the Towers of Hanoi is not too difficult, though the number of moves required increases exponentially as the number of disks.

Let's play a variant of the Towers of Hanoi.  Instead of three rods, there are five.  And there's an additional rule: a disk can only lay on top of another disk only if the one below is exactly one size bigger.

My question is: What's the tallest tower that you can move from one rod to another?

Afterwards, you can try the same variation with six rods.

(This is an original puzzle, inspired by too many games of Freecell, which obeys the same rules.  However, I would be surprised if I'm the only one who has ever thought of this variant.)

See the solution

SlightlyMetaphysical said...

Had come to this post a minute or so after playing Freecell and got really freaked out by the similarities, so I can definately see where the inspiration for this is coming from.

I think the answer is something vaguely similar to factorals. Because when you have 5 free spaces, you can make a tower of 5, then you have 4 free spaces left, you can make a tower of 4, then you have 3 free spaces left, tower of 3, etc. Then you can move the biggest block to the final space (the one you want to move everything to) and start dismantling your other towers in reverse order. So n=x+(x-1)+(x-2)+(x-3)+... (where n is how many blocks you can move and x is how many free rods there are)?

I play far too much Freecell...

miller said...

That should get you n*(n-1)/2 disks, where n is the number of rods. But it is possible to do better than that!

Jasmine Smith said...

This is a smart blog. I mean it. You have so much knowledge about this issue, and so much passion. You also know how to make people rally behind it, obviously from the responses. Youve got a design here thats not too flashy, but makes a statement as big as what youre saying. Great job, indeed.