What is the smallest number of moves by which the priests can successfully transfer all 64 rings from one nee?

Question

In the great temple at Banares, beneath the dome which marks the center of the world, rests a brass plate in which are fixed 3 diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God places 64 disks of pure gold, the largest disk resting on the brass plate. and the others getting smaller and smaller up th the top one. This is the tower of Brahma. Day and Nioght unceasingly the preasts transfer the disks from one needle to another according to the fixed and immutable laws of Brahma, which require that the priests on duty must not move more than one disk at a time and that he must place this disk on a needle so that no smalller disk is beneath it. Also the priest may not skip a needle when transferring the disks from the needle on one far side to the needle on the other far side. whe the 64 disks are fully trasferred the world will disapear with a thunderclap.

so the rules
1. cant put big disks on little disks
and
2. cant skip neddles.


to move _ ring(s) from needle A to neddle C it takes _ moves
1-2
2-6
3-26
4-80

ok people i know that the Tower of Hanoi or Tower of Benares is. and i know on all sites it gives you 2^(n)-1 but that is the formula for if you can skip neddles when you move them back and forth i need the formula were you can not skip needles.

it does take 8 moves for 2 rings not 6 sorry

Answer 1

This problem is known as the "Tower of Hanoi," and is usually presented with monks performing the labor and needles placed in a triangle. The solution for any given number of rings n is that it requires (2^n) - 1 moves to complete. But your problem is different and requires a new analysis.

As you wrote, moving a single ring from needle A to needle C requires that you move it from A to B and from B to C, 2 total moves. To move 2 rings, you must move the small one over twice, the second one over once, the small one back across it twice, the second one onto C, and the small one back over it twice a third time, for 8 moves total. I think for 3 rings it takes 26 moves; you need to take 8 moves to move the first two from A to C, one move to move the third ring to B, 8 moves to move the first two back to A, another move to get the big ring onto C, and finally 8 a third time to put the first two on top of the big on on C.

So f(n + 1) = 3*f(n) + 2. The result of this recurrence is that f(n) = (3^n) - 1. The final answer is that it requires (3^64) - 1 ~= 3.43 x 10^30 moves. Even if it took only a second to perform each move, this would take (3.43 x 10^30 s)(1 min / 60 s)(1 hr / 60 min)(1 day / 24 hr)(1 yr / 365 day) = 1.09 x 10^23 years, or about 7.95 x 10^12 times the age of the universe itself.

Answer 2

Also known as the Towers of Hanoi

See:

http://mathworld.wolfram.com/TowerofHanoi.html

f(n)=2^n-1

In your case n =64

so 2^64-1 is the solution (a really big number that my calculator won't display).