Tower of Hanoi
Problem
This problem is in two parts. The first part provides some building blocks which will help you to solve the final challenge. These can be attempted in any order. Of course, you are welcome to go straight to the Final Challenge without looking at the building blocks!
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.
A video showing the most efficient way of moving the discs from one end to the other is available here
Click on a question below to get started:
Question A
i) One disc?
ii) Two discs?
iii) Three discs?
iv) Four discs?
Do you notice anything interesting about the way the number of moves increases?
Can you explain any patterns you find?
Question B
The Tower of Hanoi puzzle can be completed in 15 moves with four discs. Can you use this to work out how many moves would be needed with five discs?
In general, can you describe a way of working out how many moves are needed when one extra disc is added?
Final Challenge
Extension
Printable NRICH Roadshow resource.
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.
Hint for building block B: Think about moving all the discs except the largest one onto the middle peg first.
Hint for Extension question: Current theory and observations suggest that between 13.5 and 14 billion years have elapsed since the Big Bang.
Student Solutions
Matthew, from Verulam School, made the following observations:
Question B helps you work out the difference between the numbers: 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.
Teachers' Resources
Why do this problem?
The Tower of Hanoi is a well-known mathematical problem which yields some very interesting number patterns. This version of the problem involves a significant 'final challenge' which can either be tackled on its own or after working on a set of related 'building blocks' designed to lead students to helpful insights.
Initially working on the building blocks gives students the opportunity to then work on harder mathematical challenges than they might otherwise attempt.
The problem is structured in a way that makes it ideal for students to work on in small groups.
Possible approach
An alternative version of this problem, with videos showing the most efficient way to move the discs, can be found here.
Start by explaining how the Tower of Hanoi game works, making clear the rules that only one disc can be moved at a time, and that a disc can never be placed on top of a smaller disc.
It is important to set aside some time at the end for students to share and compare their findings and explanations, whether through discussion or by providing a written record of what they did.
Key questions
What important mathematical insights does my building block give me?
Possible extension
Of course, students could be offered the Final Challenge without seeing any of the building blocks.
Possible support
Encourage groups not to move on until everyone in the group understands. The building blocks could be distributed within groups in a way that plays to the strengths of particular students.