# The Tower of Hanoi- A Game To End The World?

*I have been teaching mathematics in an Australian High School since 1982, and I am a contributing author to mathematics text books.*

The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. In 1889 he also invented a game he called **Dots and Boxes, **which is** **now commonly called **Join the Dots **and is probably played by children to avoid classwork.

## How to play Tower of Hanoi

There are three start positions labelled A, B and C. Using a given number of discs or blocks of different size, the aim is to move all of them from one position to another in the minimum number of moves possible.

The example below shows the six possible combinations involving start position and moving the topmost block.

## Rules for moving the blocks

1. Only one block may be moved at a time.

2. Only the topmost block can be moved.

3. A block can only be placed on top of a larger block.

Shown below are three moves that are not allowed.

## History

Different religions have legends surrounding the puzzle. There is a legend about a Vietnamese temple with three posts surrounded by 64 bags of gold.Throughout the centuries, priests have been moving these bags according to the three rules we saw previously.

**When the last move is completed, the world will end.**

(Is this a worry? Find out at the end of this article.)

## Move three blocks

Let's look at how the game is played using three blocks. The aim will be to move the blocks from position A to position C.

The number of moves needed was seven, which is also the minimum number possible when three blocks are used.

## Recursive form

The number of moves needed for a given number of blocks can be determined by noticing the pattern in the answers.

Below is shown the number of moves needed to move from 1 up to 10 blocks from A to C.

Notice the pattern in the number of moves.

3=2×1 +1

7=2×3 +1

15=2×7 +1

and so on.

This is known as **recursive form**.

Notice that each number in the second column is related to the number immediately above it by the rule 'double and add 1'.

This means that to find the number of moves for the N^{th} block, (call it block_{N}), we calculate 2×block_{N-1}+1, where block_{N-1 }means the number of moves needed to move N - 1 blocks.

This relationship is apparent when looking at the symmetry of the situation.

Suppose we start with B blocks. N moves are needed to move the top B-1 blocks to the empty position that is not the required final position.

One move is then needed to move the bottom (largest) block to the required position.

Finally, a further N moves will take the B-1 blocks to the top of the largest block.

Thus, the total number of moves is N + 1 + N or 2N + 1.

## Think about...

Will it take the same number of moves to shift N blocks from A to B as to move from B to A or from C to B?

Yes! Convince yourself of this using symmetry.

## Explicit form

The drawback with the recursive method to find the number of moves is that to determine, say, the number of moves needed to move 15 blocks from A to C, we must know the number of moves required to move 14 blocks, which requires the number of moves for 13 blocks, which requires the number of moves for 12 blocks, which requires.....

Looking again at the results, we can express the numbers using powers of two, as shown below.

Notice the connection between the number of blocks and the exponent of 2.

**5** blocks 2** ^{5 }**- 1

^{}

**8** blocks 2^{8} - 1

This means that for N blocks, the minimum number of moves needed is 2^{N} - 1.

This is known as the **explicit form** because the answer does not rely on having to know the number of moves for any other number of blocks.

## Back to the priests

The priests are using 64 bags of gold. At a rate of 1 move each second, this will take

2^{64}-1 seconds.

This is:

18, 446, 744, 073, 709, 600, 000 seconds

5,124,095,576,030,430 hours (divide by 3600)

213, 503, 982, 334, 601 days (divide by 365)

584, 942, 417, 355 years

Now you can appreciate why our world is safe. At least for the next 500 billion years!