The Tower of Hanoi

  • Medium
  • Mathematical puzzles
  • Tests: Building a recurrence from a single idea

The puzzle

Eight discs of different sizes are stacked on one of three pegs, largest at the bottom. Move the whole stack to another peg, one disc at a time, never placing a disc on top of a smaller one.

What is the fewest moves? And how long would 64 discs take at one move a second?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

To move 8 discs you must first move the top 7 out of the way, then move the biggest, then move the 7 back on top of it.

Hint 2

So f(8) = 2*f(7) + 1. Work down to f(1) = 1.

Show the answer Hide the answer

255 moves, which is 2^8 - 1. For 64 discs it is 2^64 - 1 moves - about 585 billion years at one a second.

How to get there

Let f(n) be the fewest moves for n discs. The largest disc can only move when the other n-1 are all on the spare peg, so you must move n-1 discs across (f(n-1) moves), move the largest (1 move), then move the n-1 back on top (f(n-1) again). So f(n) = 2*f(n-1) + 1.

With f(1) = 1 that gives 1, 3, 7, 15, 31, 63, 127, 255 - each one short of a power of two, so f(n) = 2^n - 1. For eight discs, 255.

The recurrence is also a proof of optimality: the largest disc must move at least once, and clearing the way for it genuinely requires moving the other n-1 discs to one peg, which is the same problem one size smaller. For 64 discs, 2^64 - 1 is about 1.8 x 10^19 moves, or 585 billion years - the legend's point exactly.

The technique worth keeping

Find the one move that the whole problem turns on - here moving the largest disc - and ask what must be true just before it. That question is usually the same problem a size smaller, which is the recurrence.