Go backward to Who Took The Last Coin?
Go up to Mathematically Interesting Games
Go down to first subsection Discovering the Mathematics Behind the Game
Go forward to The Car and the Goats (skipping over subsections)
Switch to graphical version (better pictures & formulas)

The Tower of Hanoi

The Legend. In an ancient city in India, so the legend goes, monks in a temple have to move a pile of 64 sacred disks from one location to another. The disks are fragile; only one can be carried at a time. A disk may not be placed on top of a smaller, less valuable disk. And, there is only one other location in the temple (besides the original and destination locations) sacred enough that a pile of disks can be placed there.

So, the monks start moving disks back and forth, between the original pile, the pile at the new location, and the intermediate location, always keeping the piles in order (largest on the bottom, smallest on the top). The legend is that, before the monks make the final move to complete the new pile in the new location, the temple will turn to dust and the world will end. Is there any truth to this legend?

The Game. There's a game based on this legend. You have a small collection of disks and three piles into which you can put them (in the physical version of this game, you have three posts onto which you can put the disks, which have holes in the centre). The disks all start on the leftmost pile, and you want to move them to the rightmost pile, never putting a disk on top of a smaller one. The middle pile for intermediate storage. Here's how the game looks with six disks:

```                  |                |                |
***               |                |
*****              |                |
*******             |                |
*********            |                |
***********           |                |
*************          |                |
===================================================
```

(if your computer can display graphics, you should access the graphical version of this game).

Use the buttons below to play the game, and see if you can move all the disks in the smallest number of moves possible. Then, see if you can figure out a mathematical pattern behind the number of moves required for different numbers of disks, and use this pattern to predict how long it will take the monks to move their 64 disks.

With 1 disk, it can be done in 1 turn. With 2 disks, it can be done in 3 turns. With 3 disks . . . well, that's for you to figure out, and see if you can find a pattern to the sequence. When you've found the pattern, you should be able to tell whether or not there's any truth to the chilling prophecy!

To help you out, the computer will give you a rating from 1 to 5 after you play the game, telling you how close you came to doing it in the minimum number of turns (a rating of 5 being the best).

using disks. (You can choose from 1 to 10 disks).

Once you've played for a while, you might want to look at some hints on how to discover the mathematical pattern behind the game.

You may also be interested to know that there is a connection between this game and the problem of finding a "Hamiltonian path" along the edges of a cube and its higher-dimensional analogues; for more information, see the SIMMER presentation on this topic.