Classic Problem - Tower of Hanoi
Problem
In this problem, you will be working on a famous mathematical puzzle called The Tower of Hanoi. There are three pegs, and on the first peg is a stack of discs of different sizes, arranged in order of descending size. The object of the game is to move all of the discs to another peg. However, only one disc can be moved at a time, and a disc cannot be placed on top of a smaller disc.
The video below shows the most efficient way of moving the discs from one end to the other, starting with 3, 4, 5 or 6 discs.
Watch the video. You might like to pause it at various points. Can you predict what will happen next? What patterns can you see?
Click below to see videos for 7, 8, 9 and 10 discs. Do the patterns that you noticed continue?
Explain how you could work out the number of moves needed for the Tower of Hanoi puzzle with $n$ discs.
There is a legend that a 64-disc version of the Tower of Hanoi is being played out in a temple, and when the final move is made, the world will come to an end. If one move is made each second, how long would it take to complete the game with 64 discs? Do we need to worry yet, if the first disc was moved at the very beginning of time?
Getting Started
Look at the sequence below:
$1, 2, 4, 8, 16...$
Can you describe how to get from one term to the next?
Can you describe the $n^{th}$ term of the sequence?
Now try adding together terms from the sequence:
$1 + 2$
$1 + 2 + 4$
$1 + 2 + 4 + 8$
Do you notice anything interesting?
Can you predict what $1 + 2 + 4 + ... + 64 + 128$ would be? Check to see if you are right.
How could you write the answer to $1 + 2 + 4 + ... + 2^n$?
Justify why your formula works.
Student Solutions
Matthew, from Verulam School, made the following observations:
With 1 disc the moves done will be 1, with 2 discs the moves done will be 3, with 3 discs the moves done will be 7, and with 4 discs the moves done will be 15.
There's a pattern: the difference between the 1st and the 2nd disc is 2, the difference between the 2nd and 3rd disc is 4, and the difference between the 3rd and 4th disc is 8 - it's just doubling the difference each time.
Tom, from Wilson's School worked out a formula for the Final Challenge and had a go at the extension:
If there are $n$ discs on the tower to find out the number of moves you need to work out $2^{n-1}$ then multiply your answer by $2$ and then subtract $1$
$2(2^{n-1}) -1$
Extension:
$64$ discs would be $2^{64-1} = 2^{63} = 9,223,372,036,854,775,808$
Multiply by $2: 18,446,744,073,709,551,616$,
Subtract $1: 18,446,744,073,709,551,615$ seconds
Divide by $60: 307,445,734,561,825,860.25$ minutes
Divide by $60: 5,124,095,576,030,431.004$ hours (3 d.p.)
Divide by $24: 213,503,982,334,601.292$ days (3 d.p.)
Divide by $365.25: 584,542,046,090.626$ years (3 d.p.)
It will take roughly 584.5 billion years from the start of time.
As the universe is approximately 13.7 billion years old now I don't think we need to worry yet!
Miltoon explained how to generate the formula:
From watching the video, I see that for two discs, $3$ moves are needed. For three discs, I first see $2$ discs being removed, and re-piled, therefore, three steps are used. Now, the largest disc is moved to the pole at the end. Now the two discs have to be re-piled again, on top of that largest disc, which also takes $3$ moves. So in total, $3 + 3 + 1$ moves are needed, because we re-piled the 'two discs' twice ($6$ moves), and moved the largest disc once, leaving us with $7$ moves.
If you have $D$ discs, and you know the amount of moves needed for $D$ discs - let's call it $F$, then if you want to calculate the number of moves needed for $D + 1$ discs, physically your tower will have a new base - and you move your $D$ discs out first, and re-pile them, which takes $F$ moves, you move the new, large disc, and put it at the furthest pole, which increased the number of moves one unit, and then you re-pile the $D$ disc tower again, but this time on top of the new large disc, so in total, it takes $2F+1$ moves for a tower with $D+1$ discs.
Now I can be sure that the sequence goes: $1, (2\times1 + 1) = 3, (2\times3 + 1) = 7, (2\times7 + 1) = 15 \dots$
Therefore, the formula is just $2^D - 1$ where $D$ is the number of discs.