Tower of Hanoi

Problem

There is a tower of eight disks, stacked in decreasing size on one of three pegs.

The object of the exercise is to move the disks onto a different peg, obeying the rules:

1. Only one disk can be moved at a time;
2. No disk may be placed on a peg with a smaller disk beneath it.

How many moves are needed to move all the disks onto a different peg?

General Statement

The general problem is to determine the number of moves needed for a tower of $n$ disks.

Variant

A popular variant of the problem specifies the additional constraints:

1. The disks must all be moved from the first to the third peg.
2. A move consists of transferring a disk from the first to middle peg, or back, or from middle to third peg, or back.
3. No disk can cross over the second peg if it contains a smaller disk.

Source of Problem

This problem was invented by Édouard Lucas, who also invented the romantic story about the Tower of Brahma, as follows.

This supposedly had 64 disks "of pure gold" resting on three "diamond" needles. At the beginning of time, God placed the 64 golden disks on the first needle. It was the collective task of a sect of monks to transfer the disks to another needle, according to the rules as detailed above. The monks would work day and night at the task. When they finish, the Tower will crumble to dust and the world will end.

Solution

For a tower of $n$ disks, it takes $2^n - 1$ moves.

Solution of Variant

For a tower of $n$ disks, it takes $3^n - 1$ moves.

Proof of Solution

Setting up a Recurrence Rule

Let $T_n$ be the number of moves needed to transfer $n$ disks from one peg to another.

Clearly we have:

• $T_0 = 0$
• $T_1 = 1$

Now, we note that in order to move a tower of $n$ disks, we need to do the following:

1. Move the tower of $n-1$ disks from off the top of the $n$th disk onto another of the pegs;
2. Move the $n$th disk to the destination peg;
3. Move the tower of $n-1$ disks from where it was put temporarily onto the top of the $n$th disk.

It is clear that steps $1$ and $3$ above each take $T_{n-1}$ moves, while step $2$ takes one move.

Hence we have:

$T_n \le 2 T_{n-1} + 1$

The inequality applies here because we have established that although we know we can always get the job done in no more than $2 T_{n-1} + 1$ moves, we are not at this stage certain that there is not a better strategy which needs fewer moves.

So: is there a way of moving the disks that uses fewer moves?

Consider that at some point we need to move disk $n$.

When we do this, we must have moved the $n-1$ disks above it onto a vacant peg. That must have taken $T_{n-1}$ moves to do, whatever $T_{n-1}$ happens to be.

Having moved that final disk for the first (and hopefully last) time, we then need to transfer the $n-1$ smaller disks (which all need to be on a single peg, otherwise there won't be a spare peg to move disk $n$ onto) back onto disk $n$. This also takes $T_{n-1}$ moves to do.

So now we see that there is not a better way to move the disks, i.e.:

$T_n \ge 2 T_{n-1} + 1$

Thus we arrive at our recurrence rule:

$T_n = 2 T_{n-1} + 1$

Solution of Recurrence

Using induction, we show that $T_n = 2^n - 1$.

The base case is straightforward:

• $T_0 = 0 = 2^0 - 1$
• $T_1 = 1 = 2^1 - 1$

Now assume the induction hypothesis:

$T_k = 2^k - 1$

and try to show:

$T_{k+1} = 2^{k+1} - 1$

Hence the induction step:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle T_{k+1}\)	\(=\)	\(\displaystyle 2 T_k + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2 \left({2^k - 1}\right) + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{k+1} - 2 + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{k+1} - 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Hence the result by induction.

$\blacksquare$

Proof of Solution of Variant

To move a tower of $n$ disks from the first to third peg, the following must happen:

1. The tower of $n-1$ disks above the $n$th disk is transferred from the first to the third disk.
2. The $n$th disk is transferred from the first to the second disk.
3. The tower of $n-1$ disks above the $n$th disk is transferred from the third to the first disk.
4. The $n$th disk is transferred from the second to the third disk.
5. The tower of $n-1$ disks above the $n$th disk is transferred from the first to the third disk.

Let $T'_n$ be the number of moves needed to transfer the $n$-disk tower from peg 1 to peg 3.

Then we see that $T'_n = 3T'_{n-1} + 2$.

A simple proof by induction shows that:

$T'_n = 3^n - 1$

$\blacksquare$

Sources

• Ronald L. Graham,  Donald E. Knuth and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science (1994): $\S 1.1$