Five discs on the Tower of Hanoi

Question

Three pegs; on the first sit five discs of different sizes, largest at the bottom. You may move one disc at a time, taking the top disc of one peg and placing it on another peg, and you may never put a larger disc on top of a smaller one. 1. What is the smallest number of moves needed to transfer all five discs to another peg? 2. According to the legend, monks are moving 64 discs at one move per second. Roughly how long will they take?

Accepted Answer

31 moves for five discs. For 64 discs, about 585 billion years. The recursion. Let M(n) be the minimum number of moves for n discs. Before the largest disc can move, the other n minus 1 discs must all be on the spare peg, which takes at least M(n minus 1) moves. Then the largest disc moves once. Then the n minus 1 discs must move again onto it: another M(n minus 1). So M(n) = 2 × M(n minus 1) + 1, with M(1) = 1. This gives M(2) = 3, M(3) = 7, M(4) = 15, M(5) = 31, and in general M(n) = 2 to the power n, minus 1. The procedure that achieves it is exactly the recursive one described, and no pro…

Five discs on the Tower of Hanoi

Your answer

Discussion

Learn the concepts

Related questions