a) The "Tower of Hanoi" puzzle consists of eight disks arranged in decreasing size 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 as 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 peg 2)?

c) How many moves will be required if, in addition to the conditions in part a), an additional requirement is added: the first (smallest) disk cannot be placed on peg 2?
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 it takes (and is sufficient) $K_{n}$ steps.

Stage 2 - from the first to the last move of the bottom disk. One step is enough: 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 is 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$.

![](https://cdn.mathpix.com/cropped/2024_05_06_eab8c6bbe58aee0b55b3g-29.jpg?height=54&width=1784&top_left_y=2300&top_left_x=40)

Move the bottom disk to the 2nd peg. Then it will be necessary to return the remaining disks to the 1st peg, and then the bottom disk can be moved to the 3rd peg. It will remain to move the remaining disks from the 1st peg to the 3rd peg. 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