The Tower of Hanoi
disks of different sizes are stacked on one of three pegs, largest at the bottom. A move takes the top disk from one peg and places it on another peg, never on top of a smaller disk. What is the minimum number of moves needed to transfer the whole stack to another peg? Prove your answer.
History and references
Solved in 1883 by Édouard Lucas.
Édouard Lucas published the puzzle in 1883 under the anagram N. Claus de Siam, together with a legend about priests moving 64 golden disks. Before the largest disk can move, the other disks must all be stacked on the third peg, and afterwards they must be moved back on top of it, which gives the lower bound with . The recursive algorithm achieves this bound, so the answer is . For 64 disks at one move per second this takes about 585 billion years. With four pegs, the Frame–Stewart algorithm from 1941 was conjectured to be optimal for decades and was only proved optimal by Thierry Bousch in 2014.
References
Solutions 0
Sign in or create an account to publish a solution