How often the smallest disk moves

In an optimal solution to the Tower of Hanoi with 7 disks, how many of the total moves are made by the smallest disk?

Show hints (2)+

The largest disk moves once. How many times is a sub-tower of size $k$ relocated across the whole solution?
Disk $k$ (with $1$ = smallest) moves $2^{\,n-k}$ times; the shares $64,32,16,\dots$ sum to $2^n-1$ .

Answer

Reveal answer →

Create a free account to see the full worked solution and track your progress.