Home > Riddles > The Tower of Hanoi (Indian tradition)

The Tower of Hanoi (Indian tradition)

Timeless ingenuityLevel 2 · Core · ●●○○○

There are three rods and a tower of $n$ discs of different sizes, stacked from largest to smallest. You can only move one disk at a time and never put a large disk on top of a small disk. What is the minimum number of movements necessary to move the entire tower to another rod?
Classic problem attributed to the Brahma puzzle

Solve this riddle

Hints

Show hints
  1. To move n disks: You move the top n-1 to an auxiliary rod.
  2. To move n disks: You move the largest disk (1 movement).
  3. That gives the recurrence: T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1, T(1)=1.

Solution

Show full solution

Answer: The minimum is

$$ T(n)=2^n-1. $$

Tower of Hanoi: recurrence and growth of the minimum moves
Explanation:
To move $n$ disks:

  1. You move the upper $n-1$ to an auxiliary rod.
  2. You move the larger disc (1 movement).
  3. You move those $n-1$ disks over the largest one again.

That gives the recurrence:

$$ T(n)=T(n-1)+1+T(n-1)=2T(n-1)+1,\quad T(1)=1. $$

Solving:

$$ T(1)=1,\;T(2)=3,\;T(3)=7,\ldots \Rightarrow T(n)=2^n-1. $$

Related riddles

The crossing of the river (classical China)
Timeless ingenuity · Level 2 · Core The three vessels of the wise man (ancient India)
Timeless ingenuity · Level 2 · Core The inheritance of the 17 camels (Arab tradition)
Numerical territory · Level 2 · Core

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The crossing of the river (classical China) · Next: The island of blue eyes →