Towers of Hanoi Quiz Puzzle Answer

The Towers of Hanoi is a well-known puzzle, but we have a bit of a twist on the old favourite.

In the puzzle there are five discs of different sizes that have a hole in the middle, and three pegs. At the start of the puzzle the five discs are on peg one, and each disc is on a disc that is bigger than it. That is, the biggest disc is at the bottom, the second biggest next, up to the smallest disc on top.

The challenge is to move all five discs to peg two. However, you can only move one disc at a time, and you cannot put a disc on top of a disc that is smaller than it. You can place a disc on an empty peg.

If you have not seen the puzzle before it is fun to try to solve it. Use five coins of different sizes as a makeshift version.

Solving the puzzle does take a lot of moves; probably more than you first expect.

So the first part of the puzzle - how many moves does the five-disc puzzle take?

And the second part - can you produce a formula for the number of moves with any number of discs?

This puzzle is often used as an example of recursion in computer programming.

Moving a five-disc pile from peg one to peg two can be achieved by moving a four-disc pile from peg one to peg three, moving a disc from peg one to peg two, and then moving the four-disc pile from peg three to peg two.

And moving the four-disc pile from peg one to peg three can be achieved by moving a three-disc pile from peg one to peg two, moving a disc from peg one to peg three, and then moving the three-disc pile from peg two to peg three.

And so on, until moving a one-disc pile is just moving that one disc.

From this we can see that moving a one-disc pile requires one move. And moving an n-disc pile needs two times the moves needed for an (n-1)-disc pile plus one.

One disc needs one move, two discs needs three moves, three discs needs seven moves, and so on.

The number of moves is 2^n - 1, and for five discs that works out at 31 moves.