You may also like

problem icon

Rotating Triangle

What happens to the perimeter of triangle ABC as the two smaller circles change size and roll around inside the bigger circle?

problem icon

Doodles

A 'doodle' is a closed intersecting curve drawn without taking pencil from paper. Only two lines cross at each intersection or vertex (never 3), that is the vertex points must be 'double points' not 'triple points'. Number the vertex points in any order. Starting at any point on the doodle, trace it until you get back to where you started. Write down the numbers of the vertices as you pass through them. So you have a [not necessarily unique] list of numbers for each doodle. Prove that 1)each vertex number in a list occurs twice. [easy!] 2)between each pair of vertex numbers in a list there are an even number of other numbers [hard!]

problem icon

Russian Cubes

How many different cubes can be painted with three blue faces and three red faces? A boy (using blue) and a girl (using red) paint the faces of a cube in turn so that the six faces are painted in order 'blue then red then blue then red then blue then red'. Having finished one cube, they begin to paint the next one. Prove that the girl can choose the faces she paints so as to make the second cube the same as the first.

Tower of Hanoi

Stage: 4 Challenge Level: Challenge Level:2 Challenge Level:2


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.