The Tower of Hanoi, math that surprises you lesson

Three pegs stand in a row, and a stack of disks of different sizes sits on the left peg with the largest at the bottom. You may move one top disk at a time and never put a disk on a smaller one. How few moves can carry the whole stack to the right peg? This page builds a solution by recursion, proves with a recurrence relation that no solution for $n$ disks is shorter than $2^n - 1$ moves, and shows how quickly that number grows.

Key terms

Tower of Hanoi

Definition The Tower of Hanoi is a puzzle with exactly three pegs and $n$ disks of different sizes, where $n \ge 1$ . At the start all the disks are stacked on one peg in order of size, with the largest at the bottom. A move takes the top disk of one peg and puts it on another peg, which must be empty or have a larger disk on top. So only one disk moves at a time, and a disk never rests on a smaller disk. The goal is to move the whole stack to a chosen other peg in as few moves as possible. With three pegs the fewest moves for $n$ disks is $2^n - 1$ , and exactly one sequence of that length solves the puzzle. The count belongs to the three-peg puzzle. With a fourth peg some towers can be moved in fewer moves, and the formula no longer applies. The puzzle was published by the French mathematician Édouard Lucas in 1883.

In plain words Before the largest disk can move, every smaller disk has to be out of its way on the spare peg, and after the largest disk reaches the goal they all have to come back on top of it. That is two transfers of a smaller tower plus one move, and it is the whole reason for the count.

Example Name the pegs A, B and C, from left to right, and the three disks small, medium and large. The shortest solution for three disks has seven moves.

Move	Disk	From	To
1	small	A	C
2	medium	A	B
3	small	C	B
4	large	A	C
5	small	B	A
6	medium	B	C
7	small	A	C

Every move takes a top disk, and no disk ever lands on a smaller one. After move 7 all three disks are on C with the large disk at the bottom. With one disk the puzzle takes one move, and with two disks it takes three, small to the spare peg, large to the goal and small on top of it.

Recursion

Definition Recursion is a way of solving a problem, or of defining a quantity, through smaller cases of the same problem, together with a base case that is handled directly. A recursive method is complete when every chain of smaller and smaller cases ends at a base case. The recursive method for the Tower of Hanoi moves a tower of $n \ge 1$ disks from a starting peg to a goal peg in three stages. It moves the top $n - 1$ disks to the third peg by the same method, then moves the largest disk to the goal peg, and then moves the $n - 1$ disks from the third peg onto the largest disk by the same method. The base case is a tower of $0$ disks, which needs no moves. The largest disk never blocks a smaller one, since any disk may be put on it, so the two smaller transfers are legal.

In plain words You do not plan all the moves at once. To move a big tower you only need to know how to move a tower one disk smaller, and that in turn needs a tower one disk smaller still, until nothing is left to move.

Example For three disks the method moves the two-disk tower from A to B, which takes moves 1 to 3 of the table above, then moves the large disk from A to C in move 4, then moves the two-disk tower from B to C in moves 5 to 7. Both smaller transfers use the two-disk solution of three moves, with the roles of the pegs exchanged. The first goes from A to B with C as the spare peg, and the second goes from B to C with A as the spare peg.

Recurrence relation

Definition A recurrence relation is an equation that gives each term of a sequence in terms of earlier terms. Together with starting values it fixes every term of the sequence. For the three-peg Tower of Hanoi, let $T(n)$ be the fewest moves that carry a tower of $n$ disks from one peg to another. By symmetry this number is the same for every pair of pegs. It satisfies

\begin{gathered} T(0) = 0, \\[0.4em] T(n) = 2T(n - 1) + 1 \\[0.4em] \text{for } n \ge 1, \end{gathered}

and the only sequence with these properties is $T(n) = 2^n - 1$ .

In plain words A recurrence relation tells you how to get the next number from the ones before it. Here each new disk doubles the work of the smaller tower and adds one move for the new largest disk.

Example The recursive method shows that $2T(n - 1) + 1$ moves are enough. To see that no solution is shorter, take any solution for $n \ge 1$ disks from A to C. Just before the first move of the largest disk, no smaller disk is on top of it and none is on the peg it moves to, so all $n - 1$ smaller disks sit together on the third peg. Getting them there took at least $T(n - 1)$ moves, because the largest disk never blocks a smaller one, so the moves of the smaller disks form a solution of the puzzle with $n - 1$ disks. Just before the last move of the largest disk, which puts it on C for good, the smaller disks again sit together on the peg that is neither its source nor C, and they still need at least $T(n - 1)$ moves to reach C. These two stretches of moves do not overlap, and the largest disk moves at least once, so every solution takes at least $2T(n - 1) + 1$ moves. A solution of exactly that length moves the largest disk only once, and an induction on the number of disks then shows that the recursive solution is the only shortest one. Starting from $T(0) = 0$ , the recurrence gives these values.

Disks $n$	0	1	2	3	4	5
Fewest moves $T(n)$	0	1	3	7	15	31
$T(n) + 1$	1	2	4	8	16	32

The last row is the powers of two, which suggests $T(n) = 2^n - 1$ . The formula holds for $n = 0$ , and if it holds for $n - 1$ then

\begin{aligned} T(n) &= 2\bigl(2^{n-1} - 1\bigr) + 1 \\[0.4em] &= 2^n - 1, \end{aligned}

so it holds for every $n$ .

Exponential growth

Definition A quantity that depends on a whole number $n$ grows exponentially when it equals $C \cdot r^n$ for fixed numbers $C > 0$ and $r > 1$ , so that each increase of $n$ by $1$ multiplies it by the same factor $r$ . Such a quantity eventually exceeds any quantity of the form $kn$ , which grows by adding the same amount $k$ at each step, and in fact any fixed power of $n$ . The fewest moves $T(n) = 2^n - 1$ is one less than the exponential quantity $2^n$ , and each extra disk more than doubles it, since $T(n + 1) = 2T(n) + 1$ .

In plain words Linear growth adds the same amount at each step, while exponential growth multiplies by the same factor. The tower gets only one disk taller, but the work more than doubles.

Example Ten disks need $2^{10} - 1 = 1023$ moves, and twenty disks need $2^{20} - 1 = 1{,}048{,}575$ moves. Doubling the number of disks from 10 to 20 multiplies the moves by exactly $1025$ , because

\begin{aligned} 2^{20} - 1 &= \bigl(2^{10} - 1\bigr) \\[0.4em] &\quad \cdot \bigl(2^{10} + 1\bigr). \end{aligned}

At one move per second, twenty disks take just over 12 days, and thirty disks take $2^{30} - 1 = 1{,}073{,}741{,}823$ seconds, about 34 years. Sixty-four disks take $2^{64} - 1$ seconds, which is 18,446,744,073,709,551,615 seconds or about 585 billion years.

Check yourself

Find the fewest moves for six disks. In the recursive solution, how many times does each disk move?

Show the answer

The formula gives $2^6 - 1 = 63$ moves, and the recurrence agrees, since $T(6) = 2 \cdot 31 + 1 = 63$ . Number the disks 1 to 6 from the smallest to the largest. The recursive solution moves disk 6 once, and it moves the five smaller disks with two copies of the five-disk solution. So each smaller disk moves twice as often as it does in the five-disk solution. Repeating this, disk 6 moves once, disk 5 twice, disk 4 four times, disk 3 eight times, disk 2 sixteen times and disk 1 thirty-two times. The check

1 + 2 + 4 + 8 + 16 + 32 = 63

matches the total. Since the recursive solution is the only shortest one, every shortest solution has these counts.

Change the rules by adding a fourth peg D, and move three disks from A to D. Find a solution with fewer than seven moves. Which step of the argument for $2^n - 1$ no longer works?

Show the answer

Five moves are enough. Move the small disk from A to B, the medium disk from A to C, the large disk from A to D, the medium disk from C to D and the small disk from B to D. Every move puts a disk on an empty peg or on a larger disk. Five is also the fewest. Before the large disk first moves, the small and medium disks must both have left A, and after it lands on D for good, both must still move onto it, so each of them moves at least twice and the large disk at least once. The argument for three pegs used the fact that, before the largest disk moves, all the smaller disks must sit together on the one remaining peg, which forces a full transfer of the smaller tower. With two spare pegs the smaller disks can wait on different pegs, so that step fails, and for three or more disks the count $2^n - 1$ is no longer the minimum.

Change the rules another way. Keep three pegs A, B and C in a row, but allow moves only between neighboring pegs, so a disk can never go directly between A and C. Find a recurrence relation and a formula for the fewest moves $S(n)$ that carry $n$ disks from A to C, and find $S(2)$ .

Show the answer

One disk needs two moves, A to B and B to C, so $S(1) = 2$ , and $S(0) = 0$ . For $n \ge 1$ the largest disk has to go from A to B and later from B to C. Just before its first move, A to B, all smaller disks sit on C, and getting them there from A takes at least $S(n - 1)$ moves. Just before its last move, B to C, all smaller disks sit on A. Since they sat on C before, they need at least $S(n - 1)$ moves between these two moments. After the last move they need at least $S(n - 1)$ moves to get from A to C. These three stretches do not overlap, and the largest disk moves at least twice, so every solution takes at least $3S(n - 1) + 2$ moves. The method that moves the smaller tower from A to C, the largest disk from A to B, the smaller tower from C to A, the largest disk from B to C and the smaller tower from A to C uses exactly that many. So

\begin{gathered} S(n) = 3S(n - 1) + 2 \\[0.4em] \text{for } n \ge 1. \end{gathered}

Adding one gives $S(n) + 1 = 3\bigl(S(n - 1) + 1\bigr)$ , and with $S(0) + 1 = 1$ this gives $S(n) = 3^n - 1$ . For two disks $S(2) = 3 \cdot 2 + 2 = 8$ , which matches $3^2 - 1 = 8$ . Forbidding one kind of move changes the growth factor from $2$ to $3$ .