|  |

a) The "Tower of Hanoi" puzzle consists of eight disks of decreasing size placed on one of three pegs. The goal is to move the entire tower to another peg, moving only one disk at a time and never placing a larger disk on a smaller one. Prove that the puzzle has a solution.

What method would be optimal (in terms of the number of moves)?

b) Let's number the pegs 1, 2, and 3. The task is to move the disks from peg 1 to peg 3. How many moves will be required if direct moves from peg 1 to peg 3 and from peg 3 to peg 1 are prohibited (each move must be made via the 2nd peg)?

c) How many moves will be required if, in addition to the conditions in part a), there is an additional requirement that the first (smallest) disk cannot be placed on the 2nd peg?
a) Let the minimum number of steps to move a tower of $n$ disks be $K_{n}$. Express $K_{n+1}$ in terms of $K_{n}$. Consider a tower of $n+1$ disks. We can divide the entire procedure into three stages.

Stage 1 - from the beginning to the first move of the bottom disk. By the end of this stage, the tower of $n$ disks standing on the bottom disk must be moved to one of the free pegs (the peg to which the bottom disk will be moved next must be free). The bottom disk does not participate in these moves, so $K_{n}$ steps are necessary (and sufficient).

Stage 2 - from the first to the last move of the bottom disk. One step is sufficient: after the first move, the bottom disk can be left untouched.

Stage 3 - after the last move of the bottom disk. At the beginning of this stage, the peg from which the bottom disk was just removed is free. Thus, a tower of $n$ disks stands on the third peg, and it needs to be moved onto the bottom disk. For such a move, $K_{n}$ steps are also required.

Thus, $K_{n+1}=K_{n}+1+K_{n}=2 K_{n}+1$ (it has been shown above that fewer steps are not possible, and this number is sufficient).

Since $K_{1}=1$, we can sequentially calculate $K_{2}, K_{3}, \ldots, K_{8}$.

It is not difficult to derive a general formula: writing the obtained relation as $K_{n+1}+1=2\left(K_{n}+1\right)$, we have $K_{n}+1=2^{n-1}\left(K_{1}+1\right)=2^{n}$

Remark. "Guessing" the answer, it can be proven by induction.

b) We reason similarly. Note that here $K_{1}=2$.

First, we need to move the tower of $n$ disks from the 1st peg to the 3rd ( $K_{n}$ steps). Now we can

move the bottom disk to the 2nd peg. Then we need to return the other disks to the 1st peg, and then we can move the bottom disk to the 3rd peg. Finally, we need to move the remaining disks from the 1st peg to the 3rd. Therefore, in this situation, $K_{n+1}=K_{n}+1+K_{n}+1+K_{n}=3 K_{n}+2$.

Writing it as $K_{n+1}+1=3\left(K_{n}+1\right)$, we get $K_{n}+1=3^{n-1}\left(K_{1}+1\right)=3^{n}$.

c) Due to the fact that all towers containing the first disk must be assembled on the 3rd or 1st pegs, the difference from the reasoning in part b) is only that $K_{1}=1$. Therefore, from the same relation $K_{n}+1=3^{n-1}\left(K_{1}+1\right)$, we get $K_{n}=2 \cdot 3^{n-1}-1$.

## Answer

a) The shortest way contains $2^{8}-1=255$ moves.

b) $3^{8}-1=6560$ moves; c) $2 \cdot 3^{7}-1=4373$ moves.

Submit a comment