Here are the first 7 moves for the Towers of Hanoi.

After you get the first 3 rings moved, what do you want to move next?

Towers of Hanoi: minimum moves

If you start with 1,2, 3 rings you should start to see a pattern.

Two rings takes 3 moves. To move three rings, you first have to move the two rings to the centre post (3 moves) and then the third ring to the far post (1 move) and then the two rings from the centre post to the far post (3 more moves).

 Number of Rings Number of Moves Needed 1 1 2 3 3 7 4 15 5 31

From the table we can see that the number of moves for any number of rings (n)  is the number of moves for one less ring (n-1) multiplied by 2 with 1 added.

If we want to get a useful expression to describe the minimum number of moves, we need to get it in terms of the number of rings.

 Number of Rings (n) Number of Moves Needed (m) 2 to the power of n 2n 1 1 1 2 3 4 3 7 8 4 15 16 5 31 32

We can see from the table above that the number of moves m is given by the formula

m= 2n-1

So 10 rings would take m= 210-1 = 1024 – 1 = 1023 moves.

How long will it take to do 64 rings. It is good to have a guess before working this out using the formula.

m= 2n-1

So 64 rings would take m= 264-1

You need to do this on a calculator.

264 is a very large number. It is so large it is given on my calculator as 1.844674407371 e19

That is a 20 digit number. We dont have to be able to see this number in its entirety.

The priests can do one move a second, that is 3600 moves an hour.

So we divide this number by 3600 to get the numbers of hours it would take.

The calculator will display this:

5,124,095,576, 030,431

Then divide the result by 24 to see how many days it would take.

213,503,982,334,601.3

Then by 365 to find out how many years it would take (we don’t need to worry about leap years here).

584,942,417,355 years.

Which is longer than the known age of the universe (approx 13,000,000,000)

So we have plenty of time left.

This is an example of exponential growth. With exponential growth numbers can get very big very fast.