Tower of Hanoi/Variant
Problem
There is a tower of $n$ disks, stacked in decreasing size on one of $3$ pegs.
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
- $(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 $3^n - 1$ moves.
Proof
To move a tower of $n$ disks from the peg $1$ to peg $3$, the following must happen:
- $(1): \quad$ The tower of $n - 1$ disks above the $n$th disk is transferred from peg $1$ to peg $3$.
- $(2): \quad$ The $n$th disk is transferred from peg $1$ to peg $2$.
- $(3): \quad$ The tower of $n - 1$ disks above the $n$th disk is transferred from the peg $3$ to peg $1$.
- $(4): \quad$ The $n$th disk is transferred from the peg $2$ to peg $3$.
- $(5): \quad$ The tower of $n - 1$ disks above the $n$th disk is transferred from the peg $1$ to peg $3$.
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}' = 3 {T_{n - 1}}' + 2$
A simple proof by induction shows that:
- ${T_n}' = 3^n - 1$
$\blacksquare$
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.