# The Legend of the Towers of Hanoi

In an ancient city, so the legend goes, monks in a temple had to move a pile of 64 sacred disks from one location to another. The disks were fragile; only one could be carried at a time. A disk could not be placed on top of a smaller, less valuable disk. In addition, there was only one other location in the temple (besides the original and destination locations) sacred enough for a pile of disks to be placed there.

Using the intermediate location, the monks began to move disks back and forth from the original pile to the pile at the new location, always keeping the piles in order (largest on the bottom, smallest on the top). According to the legend, before the monks could make the final move to complete the new pile in the new location, the temple would turn to dust and the world would end.

Is there any truth to this legend?

To answer, you will need some idea how long it will take the monks to finish their task, so you play a game using a small collection of disks and three piles into which you can put them. Play the game to find the smallest number of moves necessary to move all the disks. Then see if you can figure out the mathematical pattern behind the number of moves required for different numbers of disks, and use this to predict how long it will take the monks to move their 64 disks.

Good luck!