The "Towers of Hanoi" Puzzle, its Origin and Legend
This puzzle was published in 1883 by French mathematician Edouard Lucas (Apr/4/1842 - Oct/3/1891), who made contributions to the field of Number Theory in the areas of Mersenne primes, Diophantine equations, and the Fibonacci sequence.
This game sometimes is referred to as "Lucas Tower." The object of the game is to move the whole stack of different sized discs from the left pole to the right pole in the minimum possible number of moves.
The rules are simple:
(1) Only one disc can be moved at a time.
(2) No disc can be placed on top of a smaller one.
That’s all for the rules. They are really simple but achieving the minimum number of moves requires a strong mental focus when the number of discs increases.
Some math related to this puzzle
The minimum number of moves for n discs is the number 2n - 1, that is, one less than the nth power of two.
That means the minimum number of moves for 3 discs is 8-1 = 7, while the minimum number of moves for 4 discs is 16-1 = 15, and so on and so forth.
Adding one disc to the stack practically doubles the minimum number of moves required. Not exactly but almost, it's the double plus one: 15 = (2)(7) + 1.
By successively solving the Towers of Hanoi puzzle with an increasing number of discs one develops an experiential, hands-on understanding of the following mathematical fact:
The sum of the first n non-negative powers of two equals 2n - 1, or one unit less than the next power of two.
1 + 2 + 4 = 7 = 8 –1 = 23 - 1
1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 = 128 – 1 = 27 - 1
and so on and so forth.
Another benefit of playing with this puzzle is the increased mental stamina in keeping a sharp focus for longer and longer times while performing complex, detailed, monotonous abstract calculations, like those involved in integration by parts or finding the partial fraction decomposition of rational functions. Many standardized test takers can certainly improve their score by developing this kind of stamina in keeping their mental focus sharp for longer.
How to get the job done in the minimum number of moves
The following is an informal description of a general recipe for moving the whole stack from Tower One to Tower Three in the minimum number of moves:
Use the first 2n-1 - 1 moves to move all the n-1 smaller discs from Tower One to Tower Two, so leaving room to move the largest disc.
Move the largest disc from Tower One to Tower Three.
Finally use the remaining 2n-1 - 1 moves to move all the n-1 smaller discs from Tower Two to Tower Three.
At every intermediate step, you will be using an exponential number of moves to move some sub-stack of smaller discs out of the way just to make room so you can move the corresponding bigger disc below that sub-stack to a target tower.
Every time you determine the next target tower you will know what sub-stack you want to move where. The problem here is: where do you place the smallest disc at the beginning of that operation?
To find the right initial tower for the smallest disc, you work backwards, from the largest disc in the sub-stack you want to move, one by one up to the smallest disc, alternating back and forth between the target tower and the other tower (the tower that is not the current target and where none of the discs you want to move next are right now).
The description above may seem complicated at first but you will get a feel for it and it will become simple with some practice.
Start your practice with three discs and work your way up to eight discs.
The legend of the Tower of Brahma
There is a legend associated with this puzzle. There are a number of versions of this legend.
One version goes more or less like this:
"At the beginning of the world the god Brahma gave this puzzle to the priests in a temple in the Indian city of Benares.
The base was a brass plate holding three diamond needles, each as thick as the body of a bee.
Around one of the diamond needles, there were 64 discs made of gold, all of the same thickness but of different diameters, with each disc resting on top of the next bigger one.
Brahma instructed the priests to work on moving the discs one at a time, never placing a disc on top of a smaller one, and to work efficiently and diligently, until the whole stack of 64 discs was transferred from Tower One to Tower Three in the minimum possible number of moves.
When all the discs are finally in Tower Three, this will mark the end of the world, and the known universe will vanish into nothingness.
The priests have been working incessantly, day and night, since the beginning of time, following Brahma’s instructions."
Because of this legend, the puzzle is also known as “The Tower of Brahma.”
Some cosmological speculations
The minimum number of individual moves required to transfer all 64 discs mentioned in the legend is the number 264 - 1.
This number expressed in the decimal system is 18,446,744,073,709,551,615. That is close to about eighteen and a half quintillions!!!
Even if the discs were moved at the rate of one per second, it would take more than 580 billion years for the priests to finish the task.
Scientists currently (September, 2007) believe the universe is between 12 and 16 billion years old, so by these estimates, and according to the legend of the Tower of Brahma, the universe will still go on for at least 40 times its current age before vanishing into nothingness when the priests finish moving the whole stack of 64 discs.
There is a close relationship between the Tower of Hanoi and the Sierpinski Triangle, based on a representation of the game as an undirected graph.
Other web pages dedicated to the Tower of Hanoi topics
(Please email me at email@example.com to report any broken link or to suggest more interesting sites related to this topic. Thank you)
Ask Dr. Math: FAQ - Tower of Hanoi
Wikipedia - Tower of Hanoi
Wolfram MathWorld - Tower of Hanoi
There is a book by Marcel Danesi called "The Liar Paradox and the Towers of Hanoi: The Ten Greatest Math Puzzles of All Time."
In this book Danesi covers ten famous puzzles in the history of mankind, one of them being The Towers of Hanoi.