Puzzles are very good at making you think flexibly and enabling you to find patterns (skills great for science and pretty much everything else), but they’re also just fun. One classic logic puzzle is the Tower of Hanoi, invented by Edouard Lucas in 1883.  This puzzle has been one of my favorites since I first saw it about twenty years ago.  As with many problems, there are multiple ways to achieve the basic goal, but after exploring you may figure out the most elegant or efficient way to get there.

One seven-disk version of the Tower of Hanoi looks like this (many more can be seen here):

The goal is to get the stack from the left pin to the right pin, finishing with the stack in the same order (largest disk on the bottom, smallest on top, and all the other disks in order). 

The rules:

1) You may only move one disk at a time. This means you may only move the topmost disk in a stack.

2) You may move the disk to any of the three pins, HOWEVER:

3) You may never stack a larger disk on top of a smaller one.

It’s easy to get the idea with just a few disks:

Here is the starting position:

Then we move the small disk to the middle pin:

Which allows the big disk to go to the last pin:

Then the small disk stacks on top of the big one and the stack is complete:

Try making and moving a three disk stack (just remember you can’t stack the larger ones on the smaller ones!):      

You can also use a dime, nickel and quarter, or three other coins of differing sizes, and just mark ‘tower slots’ on an index card in place of the pins.

 .

Once you get the three disk stack moved successfully, see if you can do it in only seven moves (two disks took three moves).  Four disk towers can be moved in a minimum of 15 moves.  You can also try this online. This version lets you choose up to eight disks and will keep track of how many moves you make.

Here are some things to think about as you play:

Do you start to see patterns in the way you move the disks?

Is there a rule about where you should put the first disk when moving a stack of three, four, five, etc.? Does it matter if the number of disks is even or odd? Does the pattern continue no matter how many disks you have in the tower?

What is the minimum number of moves for five disks?  Does this fit into any kind of pattern with the previous ‘minimum move’ numbers?   The minimum number of moves for a seven-disk stack is 127; does this fit the pattern?

One apocryphal story tells of a tower of 64 golden disks, which when completely moved, signal the end of the world.  Assuming one move every second, this stack would take over 500 billion years to move.

Check out this site for more discussion of the Tower of Hanoi puzzle.