Math Playground
Back to Puzzles

Puzzles › Hanoi

Tower of Hanoi

Move all the disks to the rightmost peg. Move one at a time, never put a bigger disk on a smaller one.

Tower of Hanoi

Move all disks to the right peg. Bigger never on smaller.

Moves: 0 · best: 15

The 2ⁿ − 1 rule

With n disks, the smallest number of moves needed is 2ⁿ − 1. Three disks: 7 moves. Four disks: 15. Five: 31. Doubling-plus-one each time.

Why?

To move all n disks to the right peg, you have to:

  1. Move the top n − 1 disks out of the way (to the middle peg).
  2. Move the biggest disk to the right peg (1 move).
  3. Move those n − 1 disks back on top.

So if T(n) is the move count for n disks: T(n) = 2 × T(n − 1) + 1. That solves to 2ⁿ − 1.

The legend

A monastery is said to be moving 64 golden disks, one per second, following the rules. At 2⁶⁴ − 1 moves that's about 585 billion years. The universe is fine for a while.