## Task $1 / 68$

At point $A$, there are $n$ disks $S_{i}$ with diameters $d_{i}(i=1 ; 2 ; \ldots ; n)$ stacked on top of each other such that $d_{j}<d_{k}$ for $j<k$.

They are to be moved one by one to point $B$, with point $C$ being available as an "intermediate storage".

The condition to be observed is that a larger disk must never be placed on a smaller one.

How many transport steps are minimally required?
One first tries to find a conjecture by experimenting:

For $n=1$, it is obviously necessary to take one step. For $n=2$, the first (top) disk is moved to $C$, then the second to $B$, and finally the first to $B$ (3 steps).

Similarly, one considers that for $n=3$, 7 steps are required, and for $n=4$, 15 steps are required.

Conjecture: For $n$ disks, the number of required steps is $2^{n}-1$.

Proof by complete induction:

For $n=1$ to $n=4$, the conjecture is obviously correct.

Because $2^{1}-1=1 ; 2^{2}-1=3 ; 2^{3}-1=7 ; 2^{4}-1=15$.

We assume that the first $k$ disks can be rearranged in $2^{k}-1$ steps. Then the first $k$ disks are moved to $C$, the $(k+1)$-th disk is moved to $B$, and the first $k$ disks are rearranged from $C$ to $B$ in $2^{k}-1$ steps.

The total number of steps is then

$$
\left(2^{k}-1\right)+1+\left(2^{k}-1\right)=2 \cdot 2^{k}-1=2^{k+1}-1
$$

Thus, the correctness of the conjecture is proven.