Solution

The tower of Hanoi was a popular puzzle of the late nineteenth century. The puzzle includes three pegs and some number of rings of different sizes placed in order of size, with the largest on the bottom, on one of the pegs. The goal of the puzzle is to move all the rings, one at a time without ever placing a larger ring on top of a smaller ring, from the first peg to the second, using the third peg as an auxiliary peg.

  1. Show that the minimum number of moves to transfer $n$ rings, with the rules described above, from one peg to another is $2^n-1$.

  2. An ancient legend tells of the monks in a tower with 64 gold rings and 3 diamond pegs. They started moving the rings, one move per second, when the world was created. When they finish transferring the rings to the second peg, the world ends. How long will the world last?


  1. We can argue by induction...

    First we resolve the basis step. Consider a tower of Hanoi puzzle with only a single ring to move. Of course this can be done in a minimum of one move. Since $2^1 - 1 = 1$, the basis step is established.

    Now, proceeding with the inductive step, we need to show that if the minimum number of moves needed to move $k$ rings in the manner prescribed above is $2^k-1$, then the minimum number of moves needed for $k+1$ rings is $2^{k+1}-1$. Suppose we denote the pegs by $A$, $B$, and $C$, and we seek to move our tower from $A$ to $C$. We will need to get the largest ring from $A$ to $C$, which first requires we move the $k$ rings above it to $B$. The inductive hypothesis tells us that we can do that in a minimum of $2^k - 1$ moves. Once we move the $k$ rings to $B$, we move the largest ring to $C$. Finally, we must move the $k$ rings on $B$ to $C$ as well. Again, the inductive hypothesis tells us we can do this in a minimum of $2^k - 1$ moves. So, the minimum total number of moves needed to move $k+1$ rings is

    $$\begin{array}{rcl} (2^k - 1) + 1 + (2^k - 1) &=& 2 \cdot 2^k - 1\\ &=& 2^{k+1} - 1 \end{array}$$

    Therefore, by the principle of mathematical induction, the minimum number of moves to transfer $n$ rings, with the rules described above, from one peg to another is $2^n-1$.

    QED.

  2. A really long time... approximately $584,942,417,355$ years