Few pieces unite mechanism and growth so well. Each movement is simple; The amazing thing appears when that simplicity is repeated until an unexpectedly large quantity is produced.
The Tower of Hanoi
Riddle statement
There are three rods and a tower of 7 discs of different sizes, stacked from largest to smallest on one of them.
You can only move one disc at a time and you can never place a large disc on a small one.
What is the minimum number of moves necessary to move the entire tower to another rod?
Show solution
Solution
Answer: 127 movements are required**.
To move a tower of $n$ discs, the largest disc cannot move until the upper $n-1$ discs are on the auxiliary rod. This first block requires $T(n-1)$ movements.
Then the larger disc is moved only once.
Finally, the $n-1$ discs must be moved from the auxiliary rod to the destination rod: another $T(n-1)$ movements.
The resulting recurrence is:
With the initial condition $T(1) = 1$, the closed formula is obtained:
For $n = 7$:
The minimum is 127 moves.