Maths Coursework

Robert Allen

Queen Elizabeth Grammar School

The Towers of Hanoi

The Towers of Hanoi is an ancient mathematical game.  The aim of this coursework is to try to identify patterns and rules associated with the game and explain them in mathematical terms.  The definitions and rules are:

Rules:

• There are only three positions a disc can be placed.  Poles A, B or C.
• A disc can only go on top of a larger one.  (I.e. Disc A can only go on top of Discs B and C, but Disc B cannot go on top of disc A)
• The object of the game is to get all the discs to move from pole A to pole B of C in the least number of moves.
• Only one disc may be moved at a time.

Finding Formula A

From looking at the table it is quite clear that there is a pattern linking the number of discs and the least number of moves.  It is clear that there is an element of doubling involved, as the least number of moves nearly doubles each time.  When I add the extra column see above, it is clear that there is a doubling element involved.

When I look again, I can see that the pattern is the previous term doubled plus 1.  This can be expressed mathematically as:

Un = 2(Un-1) +1

This can be shown in:

1. For 1 disc,

A

A

E

A

B

A

C

A

B

A

D

A

B

A

C

A

B

A

From my coding it is now clearer why that formula is that particular formula.  It can be seen that there is symmetry involved in each pattern.  The symmetry is always about the name of the bottom disc. I.e. with 3 discs the symmetry is about disc C and this is the bottom disc

From the coding, I can also see that the pattern of moves for 2 discs is present in the beginning of 3 discs, 4 discs etc.  The pattern for 3 discs is also in the pattern for 4 discs and so on.  This is can therefore be explained as:

In n number of discs where n is greater than 2, the first three moves will always be ABA.  This is because the n-1 discs pattern is included in the n pattern.  We have

(Un-1), because we take into account the previous terms pattern when making the next tower.

We have the 2 term because this pattern is repeated twice, firstly to deconstruct the tower and then to rebuild the tower on top of the bottom disc.

We have the +1 term because this is where the bottom disc moves from Pole A to Poles B or C.  This can be demonstrated when we move three tiles.

ABA – This is the move pattern for 2 tiles (Un-1). This allows C to be able to move.

C –      This is when the bottom tile moves and we therefore get the +1 from.

ABA – This is where the doubling element comes in as well as the n-1 discs moves                                                         pattern.  This is where the tower is rebuilt on top of disc C.

So overall, we get the formula: 2(Un-1) +1

There are limitations to this however. Un-1 has to be an integer because we cannot have 3.5 moves.  Un-1 has to also be equal to or greater than 0 and has to be an integer because the formula wouldn’t work as the result would be negative and we cannot have a negative number of moves.

Formula B – Finding the formula that shows how many times a certain disc moves

From formula A I now have a basis on which to work.  Given a certain number of discs I need to be able to say how many times a desired disc moves.

Firstly, I need to analyze my results from the coding.

When I had 4 discs however, I noticed that the pile finished on where I did not place tile A which was Pole B.

This can therefore be expressed as:

If the number of discs in the pile to start with is even then the bottom disc will land where you place Disc A to start off with.

If the number of discs in the pile is odd however, then the bottom disc in the pile will finish up on the pole where you did not place Disk A.

Therefore where you put Disc A can be considered crucial to where you want your pile to land

Overview:

If I have 25 discs in my pile, I can expect there to be:

33554431 moves involved in the series.

Disc A will move 16777216 times; whereas disc y will move only once.

The Pile will end up on the pole where you place disc A, so if I leave it on pole B to start with, the pile will end up on Pole B.

According to the monks in Hanoi, the world will end in over 500 Million Years.

The problems with my investigation:

I have realized that there are only 26 letters in the alphabet.  With my system of labeling, it is impractical for me to label each disc A, B C etc because I will run out of letters.  I will either have to name the poles ABC or call each disc past 26, A1 etc.