Copyright © University of Cambridge. All rights reserved.
'Tower of Hanoi' printed from https://nrich.maths.org/
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.