Hanoi Tower

Puzzle Board

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower) was invented by the French mathematician Édouard Lucas in 1883.

Here are the rules of this puzzle:

1. Only one disk may be moved at a time.
2. Only the uppermost disk can be moved from one of the stacks and to the top of another stack or on an empty rod.
3. No disk may be placed on top of a disk that is smaller than it.

There is a story about an Indian temple which contains a large room with three old posts and 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks for countless years. According to the legend, the world will end when the last move is completed.

Hints

Complete the first five levels of this puzzle and keep your results in a table. Explore how the minimum number of moves is related to the number of discs.

Solution

When there are three disks, the number of minimum moves is 7, when there are four disks, it is 15, and so on. If there are n disks, the minimum number of moves to transfer all disks from one rod to another is $2^n-1$.

Therefore in this version of Hanoi Puzzle, it takes 127 ($2^7-1$) moves to transfer disks to one rod to another.

More on Hanoi Tower

If the legend were true, and if the priests were able to move disks at a rate of one per second, using the smallest number of moves, determine when will the prophecy come true?

Next

If you like this puzzle, try river crossing puzzle.