Tower of Hanoi - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

Tower of Hanoi

Main Concept

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  disks

 

1. 

Move the top  disks to another peg.

2. 

Move the last disk to the open peg.

3. 

Move the first  disks on top of the last disk.

 

So, if we let  be the number of steps for  disks, then recursively, . Since  (trivially), the first few terms generated by this formula are . This is identical to the sequence generated by the non-recursive function  for . 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  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.

 

More MathApps

MathApps/LogicAndPuzzles

 


Download Help Document