| home | games | about | mpjournal | school | links |
The object of this game is to move all of the rings to the right most peg. You may only move one ring at a time, you must never allow a large ring to rest on a smaller ring.
To solve such problems ask yourself: "if I had solved the n -1 case, could I solve the n case?"
If the answer to this question is positive you proceed under the outrageous assumption that the n-1 case has been solved. Oddly enough this works, so long as there is some base case (often when n is zero or one) which can be treated as a special case.
If you know how to move n-1 rings from one pole to another then simply move n-1 rings to the spare pole – there is only one ring left on the source pole now, simply move it to the destination. Then pile the rest of them from the spare pole onto the destination pole.
You are not allowed to move the biggest ring on the other. You must move other n-1 rings to the central peg, so that the sum of the movements becomes (n-1). After moving the biggest one to the right most peg (by one movement) you must move other n-1 disks by (n-1) movements. So that recording to the explanations given before, to move n rings to the right most peg you have to do an=a(n-1)+1+a.(n-1)=2.a(n-1)+1 movements.
To move n rings from A to C using B as spare:
* If n is 1 just do it.
* Otherwise
#move n-1 rings from A to B using C as spare
#move one ring from A to C.
#move n-1 rings from B to C using A as spare.
As
with most recursive solutions we have to treat some base case specially –
here the base case occurs where we have only one right to move.
<go to top>
There are several legends associated with this puzzle, in particular concerning its origin. One such legend goes as follows: In the temple of Benares, at the center of the world, there were three diamond poles on a copper plate. During the Creation God placed 64 golden disks on one of these poles, stacked from large to small. This is the Tower of Brahma. In accordance with the laws of Brahma, the priests moved one disk at a time, putting it on one of the other poles. However, the disk on which a priest places his disk may never be smaller than the disk which comes on top of it. Also, it is only permitted to move one disk at a time. When the tower has been transferred from one pole to the other, everything will turn to dust and the world will disappear in a thunderbolt. But don't panic! In order to transfer the 64 disks from one pole to another, a total of 18,446,744,073,709,551,615 moves are necessary. If you work very quickly, say one move in a second, it will still take billions of years. So I by the Frenchman Edouard Lucas, and the puzzle was sold as a toy in France wouldn't worry myself too much. Actually, the puzzle and the legend were invented.
The Tower of Hanoi (sometimes referred to as the Tower of Brahma or the End of the World Puzzle) was invented by the French mathematician, Edouard Lucas, in 1883. Inspired by a legend that tells of a Hindu temple where the He was a pyramid puzzle might have been used for mental discipline of young priests. Legend says that at the beginning of time the priests in the temple were given a stack of 64 gold disks, each one a little smaller than the one beneath it. Their assignment was to transfer the 64 disks from one of the three poles to another, with one important proviso- a large disk could never be placed on top of a smaller one. The priests worked very efficiently, the temple would crumble into dust and the world would vanish.
The number of separate transfers of single
disks the priests must make to transfer
the tower is 2 to the 64th minus 1, or 18,446,744,073,709,551,615 moves! If the
priests worked day and night, making one
move every second it would take slightly more than
580 billion years to accomplish the job! You have
a great deal fewer disks than 64. Can you calculate
number of moves it will take you to move
disks from one of the three poles to another?
<go to top>
Let TN be the number of moves needed to solve the puzzle with N disks. We can find that T3=7 and T4=15. One can easily convince oneself that T2=3 and T1=1. A trained mathematician would also note that T0=0. Now let us try to derive a general formula.
The recursive solution above involves moving twice (N-1) disks from one peg to another and making one additional move in between. It then follows that
TN ≤ TN-1+1+TN-1 = 2TN-1+1
The inequality suggests that it's possible to move N disks with fewer than 2TN-1+1 moves. Which is actually not the case. Indeed, when the time comes to move the bottom disk (N-1) disks will have been moved from source peg (initial peg) to auxiliary peg (middle peg) in TN-1 moves. Unless one moves the largest disk back and forth, it takes just one move to move it from source peg to destination peg (target peg). One then needs at most TN-1 more steps to finish the task. Therefore
TN ≥ TN-1+1+TN-1 = 2TN-1+1
or, finally,
TN = TN-1+1+TN-1 = 2TN-1+1
Thus we can define the quantity TN as
T0=0
TN=2TN-1+1 for N>0
Thus we may compute T1=2T0+1=1, T2=2T1+1=3, T3=2T2+1=7 and so on sequentially.
The above expression is known as a recurrence relation which, as you might have noticed, is but a recursive function. TN is defined in terms of only one of its preceding values. Other recurrence relations may be more complicated, for example, f(N)=2f(N-1)+3f(N-2). Recurrence relations appear under various guises in numerous branches of Mathematics and applications.
Returning to the definition of TN, define SN=TN+1. Then S0=1 and SN=TN+1=(2TN-1+1)+1=2TN-1+2=2(TN-1+1)=2SN-1. Which is to say that SN could be defined as
S0=1
SN=2SN-1 for N>0
The latter is solved easily in the closed (non-recurrent) form SN=2N. Wherefrom
TN = 2N-1 for N ≥ 0.