*Navigation Panel:*

Go up to The Tower of Hanoi

Go forward to Discovering the Mathematics, Continued

Switch to text-only version (no graphics)

Go to University of Toronto Mathematics Network
Home Page

### Discovering the Mathematics Behind the Game

If you've played the game as well as possible, you should have
discovered that the minimum number of turns it takes to win (for 1, 2, 3,
and 4 disks, respectively) are 1, 3, 7, and 15.
**Looking for the Pattern.** To figure out how many turns it'll
take for more than four disks, and to figure out how long it'll take
the monks to finish their task, you need to find a pattern relating
the number of disks to the minimum number of turns it takes to win the
game. Write down the minimum number of turns it takes for one, two,
three, and four disks. Can you conjecture a pattern? (*Hint:* try
adding one to each of the numbers; do you recognize a pattern now?)

**Justifying the Pattern.** It's great that you've found a
pattern. But maybe the pattern is just a coincidence, and doesn't
continue for larger numbers of disks. To see if it does, we need a
more systematic, mathematical approach. We will proceed by
*induction*: if we know how many turns it takes to win the
*n*-disk game, we'll try to use that to find how many turns it takes
to win the (*n*+1)-disk game. Having done that, we'll be able to find
the number of turns for any *n*.

So, suppose we know that it takes *M* turns to move a pile of *n*
disks from one post to another. How many turns will it take to move
*n*+1 disks?

Think of it this way: *imagine you can move the top **n* disks as
a single unit. Now, what's the quickest way to move all *n*+1 disks?
Your answer should involve a certain number of moves of the top *n*
disks (as a single unit), and a certain number of moves of the bottom
disk (by itself).

Now, although this is illegal (you can't move the top *n* disks as a
unit), *you can achieve the same effect in **M* legal moves, because we
know that it takes *M* turns to move a pile of *n* disks from one post
to another.

Therefore, you now have a procedure for legally moving all *n*+1 disks
to their new home: follow the procedure you devised before, but
instead of moving the top *n* disks as a unit, use the *M* legal moves
required to achieve the same effect. How many turns does this
procedure take?

The answer is in the next section, but don't go
there until you've tried to work it out for yourself.

This page last updated: May 26, 1998

Original Web Site Creator / Mathematical Content Developer:
Philip Spencer

Current Network Coordinator and Contact Person:
Joel Chan - mathnet@math.toronto.edu

*Navigation Panel:*