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.

Authors Avatar

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, it takes 1 move to move disc A from pole 1 to pole 3;
  2. For 2 discs, it takes 3 moves:    2(Un-1) +1 = 2(1)  + 1 =  3 
  3. For 3 discs, it takes 7 moves:    2(Un-1) +1= 2(3)  + 1 =  7 
  4. For 4 discs, it takes 15 moves:   2(Un-1) +1= 2(7)  + 1 = 15 
  5. For 5 discs, it takes 31 moves:   2(Un-1) +1= 2(15) + 1 = 31

To understand how this works, coding is needed to see how a disc moves individually.  Coding should show me the patterns involved and then I should be able to justify my formula based on this.

Coding is on the next page.

Coding

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

Join now!

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 ...

This is a preview of the whole essay