Chapter 3: Sequences

Investigate!

There is a monastery in Hanoi, as the legend goes, with a great hall containing three tall pillars. Resting on the first pillar are 64 giant disks (or washers), all different sizes, stacked from largest to smallest. The monks are charged with the following task: they must move the entire stack of disks to the third pillar. However, due to the size of the disks, the monks cannot move more than one at a time. Each disk must be placed on one of the pillars before the next disk is moved. And because the disks are so heavy and fragile, the monks may never place a larger disk on top of a smaller disk. When the monks finally complete their task, the world shall come to an end. Your task: figure out how long before we need to start worrying about the end of the world.

First, let's find the minimum number of moves required for a smaller number of disks. Collect some data. Make a table.
Conjecture a formula for the minimum number of moves required to move $n$ disks. Test your conjecture. How do you know your formula is correct?
If the monks were able to move one disk every second without ever stopping, how long before the world ends?

This puzzle is called the Tower of Hanoi. You are tasked with finding the minimum number of moves to complete the puzzle. This certainly sounds like a counting problem. Perhaps you have an answer? If not, what else could we try?

Discrete Mathematics: An Open Introduction, 3rd edition, by Oscar Levin (discrete.openmathbooks.org), licensed under CC BY-SA 4.0; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.