Tower of Hanoi

From ProofWiki
Jump to navigation Jump to search

Problem

There is a tower of $n$ disks, stacked in decreasing size on one of $3$ pegs.

Tower of Hanoi.jpeg

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

$(1): \quad$ Only one disk can be moved at a time
$(2): \quad$ 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?


Variant

$(1): \quad$ Only one disk can be moved at a time
$(2): \quad$ No disk may be placed on a peg with a smaller disk beneath it
$(3): \quad$ The disks must all be moved from the peg $1$ to peg $3$
$(4): \quad$ A move consists of transferring a disk from the peg $1$ to peg $2$, or back, or from peg $2$ to peg $3$, or back
$(5): \quad$ No disk can cross over peg $2$ if it contains a smaller disk.


Solution

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


Proof

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): \quad$ Move the tower of $n - 1$ disks from off the top of the $n$th disk onto another of the pegs
$(2): \quad$ Move the $n$th disk to the destination peg
$(3): \quad$ 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[1], 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:

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

Hence the result by induction.

$\blacksquare$


References

  1. ↑ In 1994: Ronald L. Graham, Donald E. Knuth and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science (2nd ed.) it is pointed out that: "We might move the largest disk more than once, if we're not too alert."


Historical Note

The Tower of Hanoi was invented by François Édouard Anatole Lucas in $1893$, under the name M. Claus.

He backed this up by inventing the romantic story about the Tower of Brahma, as follows:

In the great temple of Benares, beneath the dome which marks the centre of the world, rests a brass plate in which there are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed $64$ discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the $64$ discs have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.


It is seen from the solution of the problem that the Brahmin priests would need $2^{64} - 1$ moves:

$18 \, 446 \, 744 \, 073 \, 709 \, 551 \, 615$

to complete their task.

At $1$ move per second, that is nearly $600 \, 000 \, 000 \, 000$ years.

The world may well have (figuratively) crumbled to dust long before that time.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Tower_of_Hanoi&oldid=452828"