Update Research Note Form
Research Note Topic:
Research Note Description:
The Tower of Hanoi is sometimes referred to as the "Tower of Brahma" or the "End of the World Puzzle " . This puzzle was invented by the French mathematician Edouard Lucas in 1883 after he got inspired by a legend that tells of a Hindu temple where the pyramid puzzle might have been used for the 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 large disk could never be placed on top of a smaller one. The priests worked very efficiently, day and night. When they finished their work, the myth said, the temple would crumble into dust and the world would vanish.
So he came with a solution to solve this problem and invented this puzzle by applying mathematical logics.
In mathematics he applied Recursive Functions, Stacks and Fecurrence relations. In "Recursion" the formula derived in general for n discs is 2^n-1 .
How to apply Recursive Pattern ?
Simple! follow these steps.
Bascially There are three pegs and the discs have to be moved from the first A i.e (Source) to the last one C i.e (Destination) keeping in mind the two rules that are:
1. not to keep the larger disc on the smaller one and
2.move a disc at a time.
Now in Recursive Pattern:-
1)First, transfer n-1 disks from post A to post B. The number of moves will be the same as those needed to transfer n-1 disks from post A to post C. Call this number M moves.
2)Next, transfer disk 1 to post C [1 move] .
3)Finally, transfer the remaining n-1 disks from post B to post C. [Again, the number of moves will be the same as those needed to transfer n-1 disks from post A to post C, or M moves.]
Therefore the number of moves needed to transfer n disks from post A to post C is 2M+1, where M is the number of moves needed to transfer n-1 disks from post A to post C.
But, if we want to know how many moves it will take to transfer 100 disks from post A to post B, we will first have to find the moves it takes to transfer 99 disks, 98 disks, and so on. Therefore the recursive pattern will not be much help in finding the time it would take to transfer all the disks.
No problem !
the recursive pattern
help us generate more numbers to find an explicit (non-recursive) pattern. Here's how to find the number of moves needed to transfer larger numbers of disks from post A to post C, remembering that M = the number of moves needed to transfer n-1 disks from post A to post C:
for 1 disk it takes 1 move to transfer 1 disk from post A to post C;
for 2 disks, it will take 3 moves: 2M + 1 = 2(1) + 1 = 3
for 3 disks, it will take 7 moves: 2M + 1 = 2(3) + 1 = 7 and so on...
So the formula for finding the number of steps it takes to transfer n disks from post A to post B is: 2^n - 1 where "n" is the number of discs.
for 1 disk 2^1 - 1 = 2 - 1 = 1
for 2 disks 2^2 - 1 = 4 - 1 = 3
for 3 disks 2^3 - 1 = 8 - 1 = 7 and so on...
From this formula you can see that even if it only takes the monks one second to make each move, it will be 2^64 - 1 seconds before the world will end. This is 590,000,000,000 years (that's 590 billion years) - far, far longer than some scientists estimate the solar system will last. That's a really long time!
Little help from my hostel and classmates Superna and Atika .
Prof. Ashay Dharwadker