Tower of Hanoi
Exponential functions can grow really fast.
There is a legend, often attributed to Eduard Lucas, a French mathematician in the late 1800s, concerning a puzzle being played by a temple of monks near Hanoi in Vietnam. The puzzle consists of three pegs and 64 golden disks. All of the disks begin stacked on one peg in order of size with the largest at the base and the smallest at the top. The monks must move all of the disks from the starting peg to another peg by moving one disk at a time, while never placing a larger disk on top of a smaller disk. The legend predicts that when the monks have finished this task, the world will end.
The End of the World?
Even if the legend were true, there would be very little to worry about. Consider this: to move one disk is trivial. To move two disks simply requires moving one disk, and then moving the base disk to the unoccupied peg, and moving the first disk on top. Three disks requires performing the previous task (two disks) then moving the base disk and moving the two disks back on top. In this way we can prove that any number of disks can be moved. There are three main steps required to move n disks
Move the top n−1 disks to another peg.
Move the last disk to the open peg.
Move the first n−1 disks on top of the last disk.
So, if we let Sn be the number of steps for n disks, then recursively, Sn=Sn−1+1+Sn−1=2⋅Sn−1+1. Since S0=0 (trivially), the first few terms generated by this formula are S1=1,S2=3,S4=7,S5=15. This is identical to the sequence generated by the non-recursive function Sn=2n−1 for n≥0. Thus, with three pegs, any number of disks can be moved from a starting peg to another peg. Why, then, is there nothing to worry about? If the monks made one move every second, it will take them 264−1 seconds, or about 585 billion years, to finish their appointed task.
In the demonstration below, select a number of disks using the drop-down box below the game. Move the disks by pressing the button for the source peg followed by the button for the destination peg. For example, to move the first disk on peg 1 to peg 2 press Peg 1 and then press Peg 2. To start over press Reset.
To see the optimal number of moves for the selected number of disks, check Show optimal # of moves.
Download Help Document