The optimal solution

Share this page

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

  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • What do chocolate and mayonnaise have in common? It's maths! Find out how in this podcast featuring engineer Valerie Pinfield.

  • Is it possible to write unique music with the limited quantity of notes and chords available? We ask musician Oli Freke!

  • How can maths help to understand the Southern Ocean, a vital component of the Earth's climate system?

  • Was the mathematical modelling projecting the course of the pandemic too pessimistic, or were the projections justified? Matt Keeling tells our colleagues from SBIDER about the COVID models that fed into public policy.

  • PhD student Daniel Kreuter tells us about his work on the BloodCounts! project, which uses maths to make optimal use of the billions of blood tests performed every year around the globe.