Tower of Hanoi

Let $T(n)$ be the minimum number of moves needed to transfer a tower of $n$ rings to another peg. The largest ring never blocks a smaller ring, because it sits at the bottom of whatever peg it is on. So it does not change which moves of the smaller rings are legal.

Lower bound. The largest ring must move at least once.

Consider its first move, from the starting peg to some peg $Q$. At that moment nothing can lie on top of it, and nothing can lie on $Q$, since a smaller ring would end up beneath it. So all $n-1$ smaller rings are stacked on the third peg. Moving them there from their starting position as a tower takes at least $T(n-1)$ moves.

Now consider the last move of the largest ring, onto the target peg. By the same reasoning, the $n-1$ smaller rings are all on one other peg at that moment. They still have to be moved onto the target, which takes at least $T(n-1)$ further moves.

These two groups of moves are disjoint: the first happens before the largest ring’s first move and the second after its last move. Hence

Upper bound. The bound is achieved recursively:

1. move the top $n-1$ rings to the spare peg, in $T(n-1)$ moves;
2. move the largest ring to the target, in one move;
3. move the $n-1$ rings onto it, in $T(n-1)$ moves.

Solving the recurrence. We therefore have $T(n)=2T(n-1)+1$ with $T(1)=1$. Equivalently $T(n)+1=2\bigl(T(n-1)+1\bigr)$, so $T(n)+1=2^n$ and

For ten rings, $T(10)=2^{10}-1$:

Key idea. Every solution must clear the $n-1$ smaller rings out of the way before the largest ring moves and rebuild them on top of it afterwards, so the optimal count doubles with each ring added.