Question 18937: In the puzzle called the Tower of Hanoi, the object is to use a series of moves to take the rings from peg and stack them in order on another peg. A move consists of moving exactly one ring,and no ring may be placed on top of a smaller ring.the minimun numbers of moves required to move n rings is 1 for 1 ring, 3 for 2 rings, 7 for 3 rings, 15 for 4 rings, and 31 for 5 rings.Find a formula for the sequence.What is the minimun number of moves required to move 6 rings
Answer by venugopalramana(3286)   (Show Source):
You can put this solution on YOUR website! first let me show how to find the answer for the next case (6 rings)if we know the answer for the previous case (5 rings)
answer for 5 rings =31...ok ...now let us find the answer for 6 rings .
to start with assume the additional new ring (6th.in this case and the biggest) is fixed to the bottom.so we have to move only 5 smaller rings. let us say we move t to the intermediate stand(it should not matter to which stand we move them as long as we use 3 stands only)which requires 31 moves.now having finished this let us remove the new sixth ring which is freed now and put it on the required final stand.this requires only 1 move.now let us imagine it as fixed and being biggest it can remain there at the bottom without any problem.
now let us transfer the 5 smaller rings to this stand which requires 31 moves again.so total number of moves required to move 6 rigs=31 +1 +31=63 moves..if we put it in a formula with the notation that we need M(5) moves to move 5 rings and M(6)moves to move 6 rings... the formula we got is
M(6)=M(5)+1+M(5)=2M(5)+1=2*31+1=63....you can check the correctness of this
farmula with the other answers you got .
|
|
|
