• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month
Page
  1. 1
    1
  2. 2
    2
  3. 3
    3
  4. 4
    4
  5. 5
    5
  6. 6
    6
  7. 7
    7
  8. 8
    8
  9. 9
    9
  • Level: GCSE
  • Subject: Maths
  • Word count: 2120

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.

Extracts from this document...

Introduction

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

Number Of Discs

Least Number Of Moves

Previous term

(Doubled)

1

1

2

3

2

3

7

6

4

15

14

5

31

30

6

63

62

7

127

126

8

255

254


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,
...read more.

Middle

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.

Disc:

Disc A

Disc B

Disc C

Disc D

Disc E

Disc F

Total

Number of times each disc moves:

3 Discs

4

2

1

7

4 Discs

8

4

2

1

15

5 Discs

16

8

4

2

1

31

6 Discs

32

16

8

4

2

1

63

...read more.

Conclusion

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.

...read more.

This student written piece of work is one of many that can be found in our GCSE Consecutive Numbers section.

Found what you're looking for?

  • Start learning 29% faster today
  • 150,000+ documents available
  • Just £6.99 a month

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related GCSE Consecutive Numbers essays

  1. GCSE Maths Coursework - Maxi Product

    is the highest number so far that can be retrieved from 7 and 8 when the number is 15, in whole numbers. I will now try in decimal numbers if I can get a number higher than 56. (7.1,7.9)= 15 --> 7.1+7.9 --> 7.1x7.9=56.09 (7.2,7.8)= 15 --> 7.2+7.8 --> 7.2x7.8=56.16

  2. Maths Investigation - Pile 'em High

    I recognise this pattern. It is the sequence of triangular numbers. N= 1, 2, 3, 4, 5 (term number) 1 3 6 10 15 .......line 1 +2 +3 +4 +5 .......line 2 1 1 1 .......line 3 The numbers on line 1 are the sequence of total number of tins

  1. In this investigation I will explore the relationship between a series of straight, non-parallel, ...

    10 10 6 16 6 15 12 10 22 I will start this part of my investigation by looking for a recursive pattern (the way each term relates to the one before it) and use what I have learnt about sequences to create formulas to predict the results for a diagram with 7 (or 'n')

  2. Nth Term Investigation

    Here is a table showing my results: n x n x n 1 x 1 x 1 8 0 0 1 2 x 2 x 2 8 12 6 8 3 x 3 x 3 8 24 24 27 4 x 4 x 4 8 36 54 64 For the second column ( )

  1. Chessboard coursework

    3 2 Y= Ax1 + Bx1 + Cx1 + D=1 A+B+C+D=4 1 (x+2) 3 2 Y= Ax2 + Bx2 + Cx2 + D=5 8A+4B+2C+D=5 2 (x+3) 3 2 Y= Ax3 + Bx3 + Cx3 + D=14 27A+9B+3C+D =14 3 (x+4)

  2. I am to conduct an investigation involving a number grid.

    x 7 which means that each sized box will be: 2 x 2 = 1 x 7 = 7 (+ 21) 3 x 3 = 4 x 7 = 28 (+ 35) 4 x 4 = 9 x 7 = 63 (+ 49)

  1. Study the topic of trios and work on from that, to discover patterns and ...

    of trios: 5 --> 6 6 --> 10 7 --> 15 8 --> 21 I have noticed, by looking at the numbers of trios for 5, 6, 7, and 8, that they are all triangular numbers. A triangular number is a number which can be 'stacked' to make a triangle.

  2. Towers of Hanoi.

    From these two observations I decided to try and construct a formula to give the smallest number of moves from any number of discs. d = number of discs m = smallest number of moves 2 d was what I used to start my formula.

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work