# The Towers of Hanoi.

Extracts from this document...

Introduction

The Towers of Hanoi

The Towers of Hanoi is a mathematical game. It consists of 3 poles in alphabetical order and 3-7 discs numbered in size order. At the beginning of the game all the discs are on pole A in size order. The object of the game is to transfer the entire amount of discs from pole A to pole B or pole C in the minimum amount of moves possible.

These are the rules of the towers of Hanoi:

- A disc must never be placed on top of a smaller disc than its self.
- Only one disc may move at a time.
- The discs must be on a pole at all times except for one moving

Discs | Moves |

3 | 7 |

4 | 15 |

5 | 31 |

6 | 63 |

7 | 127 |

By looking at the table it is clear there is a pattern.

Every move that is made doubles the last number of moves and adds one.

The algebra equation: 2x+1. (Where x is the previous amount of moves)

The tower with 3 discs makes 7 moves.

Therefore using the rule 2x+1 x = 7

2*7 + 1= 15 = no. moves made in a 4 disc tower.

Each

Middle

Number of discs in tower | 3 disc tower | 4 disc tower | 5 disc tower | 6 disc tower | 7 disc tower |

Pole the tower finishes on | C | B | C | B | C |

Number of discs | 1st disc | 2nd disc | 3rd disc | 4th disc | 5th disc | |

Moves made | 3 discs 4 discs 5 discs | 4 | 2 | 1 | ||

8 | 4 | 2 | 1 | |||

16 | 8 | 4 | 2 | 1 |

This is a table of the moves made by each disc.

Each disc’s number of moves doubles every time a new disc is added (as it goes down the table). The number of moves made by each disc is halved as the disc number goes up.

For example in a 3 disc tower the number of moves made by the 1st disc (4) is halved to get the number of moves made by the 2nd disc (2). This pattern occurs throughout Hanoi.

The General rule is 2n-1. This rule means 2 is to the power of the number of discs, subtract 1.

For example for a 4 disc tower:

2x2x2x2 =16

16 – 1 = 15

The difference between the number of moves doubles as the disc number occurs in descending order. Therefore to get from one number to another, 2 must multiply the initial number. As the difference requires a multiplication in sum, this means this is a geometric sequence.

Conclusion

k is the general term

r is the common ratio

n is the number of terms

ak+1 =rak

This means the kth term is equal to the k term when it is multiplied by the common ratio.

### Example

#### When ak is 4.

ak+1

= 4+1

= 8

r = 2

2*4 = 8

4+1 = 8 = 2*4

##### The Sum of the terms of a geometric sequence

I will use the 5-disc tower sequence to investigate the Sum of the terms of a geometric sequence.

Number of discs | 1st disc | 2nd disc | 3rd disc | 4th disc | 5th disc | |

No. of moves | 5 discs | 16 | 8 | 4 | 2 | 1 |

1+2+4+8+16+32 = 63

1+2+4+8+16+32 = 64 –1.

The geometric series with 6 terms and common ratio 2:

1+2+4+8+16+32 = 63

1+2+4+8+16+32 = Series(s)

Then I multiplied it by the common ratio 2:

2+4+8+16+32+64 = 2S

2S = + 2 + 4 + 8 + 16 +.32 + 64

S = 1 + 2 + 4 + 8 + 16 + 32

S = -1 + 0 + 0 + 0 + 0 + 0 + 64

S = 64-1

S = 63

2S = 21+ 22 + 23 + 24 + 25 + 26

S = 1 + 2 + 4 + 8 + 16 + 32

S = -1 + 0 + 0 + 0 + 0 + 0 +26

S = 26-1

The equation is

S = rn-a1

The series is equal to the common ratio to the power of the number of terms minus the first term.

This method can obtain a formula:

Explanation in algebra of the general geometric sequences:

S = a + ar +ar2

This is the rule for each number: arn-1

## This is sequence is then multiplied by the common ratio ( r )

rS = ar + ar2 + ar3

This is the rule: arn

Then I subtracted the sequence from the sequence multiplied by the common ratio .

This gives:

(r-1)S= -a +arn

= a(rn-1)

S=a(rn-1)

(r-1)

Kate Charman 10T

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