# Towers of Hanoi.

Extracts from this document...

Introduction

Tom Lovett 10CB 4th April 2001

Maths GCSE Coursework Task

Towers of Hanoi

## Introduction

We have been asked during this piece of coursework to investigate the Towers of Hanoi. The Towers of Hanoi is a simple game whereby you must move of a pile of 3, 4, 5 or any other number of discs (1, 2, 3, etc) of decreasing radii from 1 of 3 poles to another pole (A, B, C).

You are only able to move one disc at a time and cannot place a larger disc on top of a smaller disc. You must also complete this task in the smallest amount of moves possible.

Our ultimate task was to complete the game with 4 discs and then 5 discs using the smallest amount of moves, then to find a formula to find the smallest amount of moves for any number of discs.

## Simple cases:

## 4 discs

Middle

m = previous number of moves

Next amount of moves = 2m + 1

I also decided to look at the differences between the smallest number of moves for each number of discs and the difference between these numbers. They are as shown is this table.

Smallest no. of moves for each disc | Difference between smallest no. of moves |

1 | 2 |

3 | 4 |

7 | 8 |

15 | 16 |

31 | 32 |

I noticed that all the differences were powers of 2. From this I predicted that the formula, needed to find the smallest number of moves from any number of discs, would somewhere involve the powers of 2.

From the results in this table where 2

Conclusion

For example, if we use 5 discs.

2 d – 1

2 5 – 1 = 31 Smallest number of moves for 5 discs = 31.

Upon revisiting my first formula I discovered that it was a repeating sequence whereby 2m was the first in the sequence. The next term in the sequence would therefore be 2m + 1. This turned out to be an iterative procedure where the output of a calculation would be the input for the next calculation and the sequence could be repeated again and again.

This could be shown using nth terms as well.

The last nth term: U n

The next nth term: U n +1

## Conclusion

From the results that I collected I was able to produce two formulas which enabled you to find the next amount of moves using either the previous amounts of moves or the number of discs. The first formula I produced I did so with the help of iterative procedures. The second formula I produce using the powers of 2.

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