To sum it up, I was assigned a problem in which there are 3 pegs. There are 64 rings on one peg (largest on the bottom, gradually getting smaller to the top). The question is how many moves does it take to move all 64 rings from one peg to another according to the rules.
Note: There can never be a bigger ring on top of a smaller ring at any time.
We are supposed to find a formula for the n'th term. Here is what I have in the chart so far:
Rings: 0, 1, 2, 3, 4, 5, 6, ... n, ... 64
Necessary Moves: 0, 1, 3, 7, 15, 31, 63, ?, ?
<< what mathematical components have to do with the Tower of Hanoi? >>
There is a 100 year old Math question called The Tower of Hanoi. It has to do with a 3 pegged board and a number of discs(of various sizes) that can be put through the pegs(starting off with all of them on one peg going down smallest to largest). You have to reposition the discs on one of the other pegs together but without moving more than one at once and without putting a larger disc on top of a smaller disc. There is a certain amount of moves it takes to reposition the discs and it changes with how many discs you have. >>
Lets explore the simplest of the Tower of Hanoi problems to see what we can learn. What if you had only 2 rings or discs? Lets define our towers by A, B, and C. We have 2 discs on tower A, the smaller one on top. What do we have to do to transfer them to tower C? Does anything jump out at you? Lets first move the top smaller disc to peg B. What do you see now? Okay, lets move the remaining disc on tower A to tower C and move the disc on B to C. Whalllaaaa!!! What do you know? We did it in 3 moves, i.e., 2 discs in 3 moves. It looks like this.
A B C A B C A B C A B C
1 - - - - - - - - - - 1
2 - - 2 1 - - 1 2 - - 2
Lets try 3 discs, 1 upper, 2 middle, and 3 bottom. Must we devise a new approach? Lets see, remembering that at no time can there be a small disc below a larger disc. First move 1 to C, followed by 2 to B, followed by 1 to B, followed by 3 to C, followed by 1 to A, followed by 2 to C, followed by 1 to C. What do you know? We did it in 7 moves, 3 discs in 7 moves. Do you see the pattern as yet? You have to transfer the discs in stages of smaller towers until all are transfered to one tower. The 3 disk one looks like this.
A B C A B C A B C A B C A B C A B C A B C A B C
1 - - - - - - - - - - - - - - - - - - - - - - 1
2 - - 2 - - - - - - 1 - - 1 - - - - - - 2 - - 2
3 - - 3 - 1 3 2 1 3 2 - - 2 3 1 2 3 1 - 3 - - 3
Lets try 4 discs. Remember now, the clue is to transfer the top 2 to another tower, move the 3rd, transfer the top 2 onto the 3rd, move the 4th, and tranfer the top 3 to the 4th. It ends up looking like this:
A B C A B C A B C A B C A B C A B C
1 - - - - - - - - - - - - - - - - -
2 - - 2 - - - - - - - - - - - - - -
3 - - 3 - - 3 - - 3 - 1 - - 1 1 - -
4 - - 4 1 - 4 1 2 4 - 2 4 3 2 4 3 2
A B C A B C A B C A B C A B C A B C
- - - - - - - - - - - - - - - - - -
- - - - 1 - - 1 - - - - - - - - - -
1 2 - - 2 - - 2 - - 2 1 - - 1 1 - -
4 3 - 4 3 - - 3 4 - 3 4 2 3 4 2 3 4
A B C A B C A B C A B C
- - - - - - - - - - - 1
- - - - - - - - 2 - - 2
1 - 3 - - 3 - - 3 - - 3
2 - 4 2 1 4 - 1 4 - - 4
As you can see, we end up with the 4 discs on another tower after 15 moves, 4 discs in 15 moves. Is the pattern becoming more obvious to you?
Lets see if we can generalize the process. Assume that we have n disks resting on peg A. Your first move is to transfer the upper (n - 1) disks from tower A to tower B, leaving tower C empty. Lets assume this requires X distinct moves. Now transfer the remaining disc on tower A to tower C. Now, as before, reverse the initial transfer
process by moving the (n - 1) disks on tower B to tower C, one at a time, which also will require another X moves. Therefore, if it takes you X moves of single disks to transfer a tower of (n - 1) disks from A to B, it will take you 2X + 1 moves of single disks to completely transfer a tower of n disks from tower A to C.
Note what is actually done in each case. When n = 3, we transfer 1 & 2, transfer 3, then transfer 1 & 2 again onto 3. When n = 4, we transfer 1 & 2, transfer 3, tranfer 1 & 2 on top of 3, transfer 4, and transfer 1, 2 & 3 on top of 4. In summary:
Disks No. Transfered How often Moves Btm Transfer Total Equals
...2...............1.................2..............2............1...............3 2^2 - 1
...3...............2.................2..............6............1...............7 2^3 - 1
...4...............3.................2............14............1.............15 2^4 - 1
...5...............4.................2............30............1.............31....2^5 - 1
By now it should be obvious to you that the number of moves is related to the number of disks by N = 2^n - 1 where N is the number of moves required and n is the number of disks involved. Try the 5 disk one for practice. Obviously after confirming the relationship between the disks and the moves, you can now determine the number of moves required for a tower of any number of disks.
One of the popular legends in the literature has it that, a long time ago, there were 3 pillars erected in an ancient Oriental Temple. Stacked on one of the pillars were 100 stone disks, decreasing in diameter from the bottom up. As the story goes, every visitor to the temple was allowed to transfer a disk from one pillar to another as long as a larger disk was never allowed to be placed on top of a smaller one. If, and when, all 100 disks were transfered to another pillar, the end of the world was said to be near. The temple had a steady stream of worshippers and assuming a disk was transfered every second throughout the day, every day, every year, etc., it would take 2^100 - 1 seconds or over 400 x 10^18 centuries to complete the transfer.
W.W. Rouse Ball, in his book "Mathematical Recreations and Essays",
relates an interesting legend of the origin of the puzzle called the Tower of Hanoi:
In the great temple at Benares, beneath the dome that marks the center of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. During creation, God placed 64 gold discs of diminishing size on one of these needles, the largest disc at the base resting on the brass plate. This is the tower of Bramah.
According to the legend the priests work night and day transferring the discs from one needle to another according to the fixed laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place each disc on a needle so that there is no smaller disc beneath it. When the 64 discs have been transferred from the needle on which God placed them at creation to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap, the world will vanish.
Based on this information, predict the end of time.
After reading the above material, or if you have the book, then you have the derivation of the solution to the number of steps required. The number of moves required is related to the number of disks by N = 2^d - 1 where N is the number of moves required and d is the number of disks involved. Also stated is the fact that 64 disks will require
18,446,744,073,709,551,615 moves
with which you can assign any time period you wish for each move and come up with a length of time required.
THE TOWER OF BRAHMA HAS 64 RINGS IN ONE BIG METAL POLE ON THE LEFT AND RIGHT HAND SIDE ARE THE SAME SIZE POLE >>
<< Ancient Legend has it that Brahma stacked 64 gold disks in order from largest to smallest. According to legend, the world will end when his priests have transferred all disks from 1 tower to another. They are guided by 2 rules: Only one disk can be moved at a time, and larger disks cannot be placed on top of smaller disks. What is the least number of moves required for 64 disks?
How can you determine the number of moves required for n disks.
Is there a formula when given n, the number of disks, one can determine the least number of moves?
If it takes 1 second to move a disk, how long will it take to move the 64 disks?
If the priests started in 3000BC and worked 24-hr day shifts, in what year will the world end, according to this legend? >>
Lets explore the simplest of the Brahma Towers (also known as the Tower of Hanoi) problems to see what we can learn. What if you had only 2 rings or discs? Lets define our towers by A, B, and C. We have 2 discs on tower A, the smaller one on top. What do we have to do to transfer them to tower C? Does anything jump out at you? Lets first move the top smaller disc to peg B. What do you see now? Okay, lets move the remaining disc on tower A to tower C and move the disc on B to C. Whalllaaaa!!! What do you know? We did it in 3 moves, i.e., 2 discs in 3 moves. It looks like this.
A B C A B C A B C A B C
1 - - - - - - - - - - 1
2 - - 2 1 - - 1 2 - - 2
Lets try 3 discs, 1 upper, 2 middle, and 3 bottom. Must we devise a new approach? Lets see, remembering that at no time can there be a small disc below a larger disc. First move 1 to C, followed by 2 to B, followed by 1 to B, followed by 3 to C, followed by 1 to A, followed by 2 to C, followed by 1 to C. What do you know? We did it in 7 moves, 3 discs in 7 moves. Do you see the pattern as yet? You have to transfer the discs in stages of smaller towers until all are transfered to one tower. The 3 disk one looks like this.
A B C A B C A B C A B C A B C A B C A B C A B C
1 - - - - - - - - - - - - - - - - - - - - - - 1
2 - - 2 - - - - - - 1 - - 1 - - - - - - 2 - - 2
3 - - 3 - 1 3 2 1 3 2 - - 2 3 1 2 3 1 - 3 - - 3
Lets try 4 discs. Remember now, the clue is to transfer the top 2 to another tower, move the 3rd, transfer the top 2 onto the 3rd, move the 4th, and tranfer the top 3 to the 4th. It ends up looking like this:
A B C A B C A B C A B C A B C A B C
1 - - - - - - - - - - - - - - - - -
2 - - 2 - - - - - - - - - - - - - -
3 - - 3 - - 3 - - 3 - 1 - - 1 1 - -
4 - - 4 1 - 4 1 2 4 - 2 4 3 2 4 3 2
A B C A B C A B C A B C A B C A B C
- - - - - - - - - - - - - - - - - -
- - - - 1 - - 1 - - - - - - - - - -
1 2 - - 2 - - 2 - - 2 1 - - 1 1 - -
4 3 - 4 3 - - 3 4 - 3 4 2 3 4 2 3 4
A B C A B C A B C A B C
- - - - - - - - - - - 1
- - - - - - - - 2 - - 2
1 - 3 - - 3 - - 3 - - 3
2 - 4 2 1 4 - 1 4 - - 4
As you can see, we end up with the 4 discs on another tower after 15 moves, 4 discs in 15 moves. Is the pattern becoming more obvious to you?
Lets see if we can generalize the process. Assume that we have n disks resting on peg A. Your first move is to transfer the upper (n - 1) disks from tower A to tower B, leaving tower C empty. Lets assume this requires X distinct moves. Now transfer the remaining disc on tower A to tower C. Now, as before, reverse the initial transfer
process by moving the (n - 1) disks on tower B to tower C, one at a time, which also will require another X moves. Therefore, if it takes you X moves of single disks to transfer a tower of (n - 1) disks from A to B, it will take you 2X + 1 moves of single disks to completely transfer a tower of n disks from tower A to C.
Note what is actually done in each case. When n = 3, we transfer 1 & 2, transfer 3, then transfer 1 & 2 again onto 3. When n = 4, we transfer 1 & 2, transfer 3, tranfer 1 & 2 on top of 3, transfer 4, and transfer 1, 2 & 3 on top of 4. In summary:
Disks No. Transfered How often Moves Btm Transfer Total Equals
...2...............1.................2..............2............1...............3 2^2 - 1
...3...............2.................2..............6............1...............7 2^3 - 1
...4...............3.................2............14............1.............15 2^4 - 1
...5...............4.................2............30............1.............31....2^5 - 1
By now it should be obvious to you that the number of moves is related to the number of disks by N = 2^n - 1 where N is the number of moves required and n is the number of disks involved. Try the 5 disk one for practice. Obviously after confirming the relationship between the disks and the moves, you can now determine the number of moves required for a tower of any number of disks.
One of the popular legends in the literature has it that, a long time ago, there were 3 pillars erected in an ancient Oriental Temple. Stacked on one of the pillars were 100 stone disks, decreasing in diameter from the bottom up. As the story goes, every visitor to the temple was allowed to transfer a disk from one pillar to another as long as a larger disk was never allowed to be placed on top of a smaller one. If, and when, all 100 disks were transfered to another pillar, the end of the world was said to be near. The temple had a steady stream of worshippers and assuming a disk was transfered every second throughout the day, every day, every year, etc., it would take 2^100 - 1 seconds or over 400 x 10^18 centuries to complete the transfer.
W.W. Rouse Ball, in his book "Mathematical Recreations and Essays",
relates an interesting legend of the origin of the puzzle called the Tower of Hanoi:
In the great temple at Benares, beneath the dome that marks the center of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. During creation, God placed 64 gold discs of diminishing size on one of these needles, the largest disc at the base resting on the brass plate. This is the tower of Bramah.
According to the legend the priests work night and day transferring the discs from one needle to another according to the fixed laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place each disc on a needle so that there is no smaller disc beneath it. When the 64 discs have been transferred from the needle on which God placed them at creation to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap, the world will vanish.
Based on this information, predict the end of time.
After reading the above material, or if you have the book, then you have the derivation of the solution to the number of steps required. The number of moves required is related to the number of disks by N = 2^d - 1 where N is the number of moves required and d is the number of disks involved. Also stated is the fact that 64 disks will require
18,446,744,073,709,551,615 moves
with which you can assign any time period you wish for each move and come up with a length of time required.
I hope this was of some interest to you.
