Relates an interesting legend of the origin of the puzzle called the Tower of Hanoi: Rouse Ball, in his book "Mathematical Recreations and Essays", 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. If, and when, all 100 disks were transfered to another pillar, the end of the world was said to be near. 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. Stacked on one of the pillars were 100 stone disks, decreasing in diameter from the bottom up. 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. 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. 5.4.2.30.1.31.2^5 - 1īy 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. Transfered How often Moves Btm Transfer Total Equals ![]() 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. When n = 3, we transfer 1 & 2, transfer 3, then transfer 1 & 2 again onto 3. 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. Process by moving the (n - 1) disks on tower B to tower C, one at a time, which also will require another X moves. Now, as before, reverse the initial transfer Now transfer the remaining disc on tower A to tower C. Lets assume this requires X distinct moves. Your first move is to transfer the upper (n - 1) disks from tower A to tower B, leaving tower C empty. Assume that we have n disks resting on peg A. Lets see if we can generalize the process. Is the pattern becoming more obvious to you? It ends up looking like this:Īs you can see, we end up with the 4 discs on another tower after 15 moves, 4 discs in 15 moves. 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. ![]() The 3 disk one looks like this.Ī B C A B C A B C A B C A B C A B C A B C A B Cġ - 1Ģ - 2 - 1 - 1 - 2 - 2ģ - 3 - 1 3 2 1 3 2 - 2 3 1 2 3 1 - 3 - 3 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. What do you know? We did it in 7 moves, 3 discs in 7 moves. 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. ![]() Must we devise a new approach? Lets see, remembering that at no time can there be a small disc below a larger disc. Lets try 3 discs, 1 upper, 2 middle, and 3 bottom. Whalllaaaa!!! What do you know? We did it in 3 moves, i.e., 2 discs in 3 moves. 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. 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. ![]() We have 2 discs on tower A, the smaller one on top. What if you had only 2 rings or discs? Lets define our towers by A, B, and C. Lets explore the simplest of the Tower of Hanoi problems to see what we can learn. There is a certain amount of moves it takes to reposition the discs and it changes with how many discs you have. 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. 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). There is a 100 year old Math question called The Tower of Hanoi.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |