Copyright © University of Cambridge. All rights reserved.

'Tower of Hanoi' printed from http://nrich.maths.org/

Show menu



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.