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