# The Towers of Hanoi

Extracts from this document...

Introduction

The Towers of Hanoi

The “Towers of Hanoi” is a mathematical game/puzzle consisting of three poles and discs of decreasing radii. The difficulty of the puzzle can be changed by adding or removing discs. The aim is to move the pile of discs from one of three stacks/poles to another.

There are two rules:

- You are only allowed to move one disc at a time.
- You cannot place a larger disc on top of a smaller disc.

One Disc

At its simplest the puzzle contains only one disc. At this level he game can be completed in only one move.

- One Disc = One Move

Two Discs

- See Diagram 1

- Two Discs = Three Moves

ThreeDiscs

- See Diagram 2

- Three Discs = Seven Moves

Predictions and Pattern One

So far I have completed the puzzle with one disc; two discs and three discs. Next I will try four discs, but first I will predict how many moves I can do it in.

Here are the results I have had so far:

- One disc = One move
- Two discs = Three moves
- Three discs = Seven moves

Middle

So we can predict that for Five Discs we will need thirty one moves. The only problem with this is that if I want to find out how many moves with ten discs I must know how many moves nine discs take and to know that I must know how many moves eight discs take and so on. This means this method may not be the best one.

Predictions and Pattern Two

Our results so far:

- One disc = One move
- Two discs = Three moves
- Three discs = Seven moves
- Four discs = Fifteen moves

A way I often look for patterns is to look at the between results. I this case we get:

This is a clear pattern of a doubling difference. This could also be seen as powers of two.

- Two = 21
- Four = 22
- Eight = 23

Both patterns predict thirty one moves for five discs.

Five Discs

- See Diagram 4

- Five Discs = Thirty-One Moves

Predictions and Pattern Two(Part 2)

Our prediction was correct again. So now we have a method which does not need to know how many discs were used last time we can create a formula using powers of 2.

So now we have some patterns emerging in these formulas. We can put them together to say that when:

- n is the number of discs we’re using

The number of moves taken is:

2n - 1

This is good to have found out but why does it happen like this?

Pattern Two (Part 3)

How about tracking how many moves each disc makes? For example the largest disc moves only once.

Each disc moves exactly the same number of times no matter how many discs there are. Discs 2 takes double the moves of Disc 1 and Disc 5 takes double the moves of Disc 4. Disc n moves 2n-1 times.

Four Poles

The next challenge with this puzzle is to use four poles (or stacks) instead of three. The rules are exactly the same as before.

One Disc

With only one disc having four poles changes it nothing it still only takes one move.

- One Disc = One Move

Conclusion

ThreeDiscs

At three discs having four poles makes a difference.

- See Diagram 5

- Three Discs = Five Moves

FourDiscs

- See Diagram 6

- Four Discs = Nine Moves

FiveDiscs

- See Diagram 7

- Five Discs = Thirteen Moves

SixDiscs

- See Diagram 8

- Six Discs = Seventeen Moves

Predictions and Pattern Three(Part 2)

So far we have seen no obvious patterns. One thing I tried was to subtract the number of moves required for 4 poles from that you needed for three poles. Again the numbers 0, 0, 2, 6 and 18 have no obvious pattern. After a lot of experimenting I realised that as 3 Poles used powers of two in the answer then four poles might use powers of three. This is what I came up with:

- 31 – 30 = 2
- 32 – 31 = 6
- 33 – 32 = 18

This also works for:

- 30 – 3-1 = 0
- 3-1 – 3-2 = 0

This comes out as:

- 3n-2 – 3n-3

So what is the actual formula?

We have:

We can rearrange this as:

So for 4 discs are formula is:

- 2n – 1 – (3n-2 – 3n-3)

by Gregory Auger

Towers of Hanoi Page of Gregory Auger

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

## Found what you're looking for?

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