Add new comment

Puzzle page

September 2006

Hanoi towers

The Towers of Hanoi

The Towers of Hanoi

The Towers of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. It consists of three pegs and a number of discs of decreasing sizes. Initially, all discs sit on the same peg in the order of their size, with the biggest disc at the bottom. The aim is to move the whole tower of discs onto another peg, subject to the following rules:

  • when you remove a disc from a peg you must place it on one of the other two pegs before you can move any other disc,
  • you can only place a disc on a peg if either the peg is empty or if the discs already sitting there are larger than the disc you're about to place.

If you've only got two discs in total, then the puzzle is easy: move the top disc from peg 1 to peg 2, then move the bottom disc from peg 1 to peg 3, and finally move the smaller disc on peg 2 onto the larger disc on peg 3 — done. A little thought will show you that moving a tower of three discs is possible also. But can you show that it is possible to move a tower consisting of any number of discs?

Hint: Suppose that you have n discs in total. We've already seen that the puzzle can be solved for n equal to 2 and 3. Now assume that you can move a tower of n-1 discs: does this help you to move a tower of n discs? If yes, then why does this prove that the puzzle can be solved for any number of discs? (A proof that uses this way of thinking is an example of the principle of induction.)

Your proof now gives you a recipe for solving the puzzle for any number of discs. Write mn for the number of moves you need to solve the puzzle with n discs according to this recipe. Can you express mn in terms of mn-1? Can you show that mn is in fact the minimum number of moves needed to solve the puzzle with n discs, in other words that there is no quicker way?

If you are stumped by last issue's puzzle, here is the solution.

For some challenging mathematical puzzles, see the NRICH puzzles from this month or last month.

Filtered HTML

  • Web page addresses and email addresses turn into links automatically.
  • Allowed HTML tags: <a href hreflang> <em> <strong> <cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.
  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • What do chocolate and mayonnaise have in common? It's maths! Find out how in this podcast featuring engineer Valerie Pinfield.

  • Is it possible to write unique music with the limited quantity of notes and chords available? We ask musician Oli Freke!

  • How can maths help to understand the Southern Ocean, a vital component of the Earth's climate system?

  • Was the mathematical modelling projecting the course of the pandemic too pessimistic, or were the projections justified? Matt Keeling tells our colleagues from SBIDER about the COVID models that fed into public policy.

  • PhD student Daniel Kreuter tells us about his work on the BloodCounts! project, which uses maths to make optimal use of the billions of blood tests performed every year around the globe.