The optimal solution

Suppose we’ve got the Tower of Hanoi puzzle with three pegs and $n$ discs. We will show that for the usual starting and finishing configurations of discs, all discs sitting on one peg, the shortest solution involves $2^ n-1$ moves. For any other pair of starting configurations the shortest solution involves at most $2^ n-1$ moves.

First let’s consider the game with one disc. Clearly solving the puzzle only involves one move. Since $2^1-1=1$ the result is true for $n=1$ .

Now suppose you’re playing the game with $n+1$ discs using the usual starting and finishing configurations and assume that the result is true for the $n$ -disc version of the game: the smallest number of moves required is $2^ n-1.$ To solve the $n+1$ -disc version, first move the $n$ smaller discs onto one of the free pegs using the shortest method which takes $2^ n-1$ moves. Now move the largest disc onto the remaining free peg. Then shift the $n$ -tower on top of it, again using the method that takes $2^ n-1$ moves. You’ve now solved the puzzle in $2(2^ n-1)+1$ moves. It’s easy to see that this is the shortest solution as you cannot get away from moving the $n$ -tower at least twice and the largest disc at least once. Therefore, the shortest number of moves required to solve the $n+1$ -disc version of the game is

$2(2^ n-1)+1=2^{n+1}-2+1=2^{n+1}-1.$

This shows that if the result is true for $n$ it is true for $n+1$ . So we have proved by induction that the result is true for all $n$ .

Now suppose you are playing the game with arbitrary starting and finishing configurations of discs. We will show that at most $2^ n-1$ moves are required to solve the puzzle.

Again we start with $n=1,$ in which case there are only three possible configurations separated pairwise by one move. So the result is true.

Now assume it is true for $n$ and see what happens for $n+1$ .

In the Hanoi graph $H_{n+1}$ write $s$ and $f$ for the nodes representing the starting and finishing configurations respectively and write $m(s,f)$ for the length of the shortest path taking you from $s$ to $f$ . (By the length of the path we mean the number of edges it traverses.) The Hanoi graph $H_{n+1}$ consists of three copies of the Hanoi graph $H_{n}$ joint pairwise by one edge. If $s$ and $f$ lie within the same copy of $H_{n}$ then

$m(s,f) \leq 2^ n-1 \leq 2^{n+1}-1$

by our hypothesis that the result is true for $n$ . Suppose they lie in two different copies, copy 1 and copy 2 of $H_ n$ . You can get from $s$ to $f$ by moving from $s$ to the vertex in copy 1 that is linked to copy 2, traversing the linking edge and then moving to $f$ within copy 2. By our assumption that the result is true for $n$ the first and the last part of this route have length at most $2^{n}-1$ . Thus,

$m(s,f) \leq 2(2^ n-1)+1=2^{n+1}-1.$

QED

Back to main article