The optimal solution

Share this page

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 2n1 moves. For any other pair of starting configurations the shortest solution involves at most 2n1 moves. First let's consider the game with one disc. Clearly solving the puzzle only involves one move. Since 211=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 2n1. 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 2n1 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 2n1 moves. You've now solved the puzzle in 2(2n1)+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(2n1)+1=2n+12+1=2n+11. 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 2n1 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 Hn+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 Hn+1 consists of three copies of the Hanoi graph Hn joint pairwise by one edge. If s and f lie within the same copy of Hn then m(s,f)2n12n+11 by our hypothesis that the result is true for n. Suppose they lie in two different copies, copy 1 and copy 2 of Hn. 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 2n1 . Thus, m(s,f)2(2n1)+1=2n+11. QED

Back to main article