Tower of Hanoi
The classic recursive puzzle invented by Edouard Lucas in 1883. Move all disks from the left peg to the right peg, one at a time, never placing a larger disk on a smaller one. The minimum solution requires 2n − 1 moves — exponential growth from the simplest possible recursion.
The recursive solution
To move n disks from peg A to peg C using peg B as auxiliary: first move the top n−1 disks from A to B (using C as auxiliary), then move the largest disk from A to C, then move the n−1 disks from B to C (using A as auxiliary). This recursive decomposition yields exactly 2n − 1 moves — which is provably optimal.
Exponential growth
With 3 disks, the puzzle takes 7 moves. With 10, it takes 1,023. With 64 disks (as in the legend of the Tower of Brahma), it would take 18,446,744,073,709,551,615 moves. At one move per second, that is roughly 585 billion years — about 42 times the current age of the universe. The legend says the world will end when the monks complete their 64-disk tower.
The legend
According to the story that accompanied Lucas’s puzzle, in the temple of Benares (or Brahma), monks are transferring 64 golden disks between three diamond posts, following the same rules. When they finish, the world will end. The story is almost certainly an invention of Lucas himself, but it captures the visceral surprise of exponential growth: a task that seems finite becomes cosmologically large.
Connections
The Tower of Hanoi is a standard example in computer science for teaching recursion. The state space forms a Sierpinski triangle (for 3 pegs) — itself a fractal. The puzzle connects to Gray codes, binary counting, and the Stern-Brocot tree. Frame-Stewart conjectured the optimal solution for 4 pegs in 1941; it was only proven in 2014 for specific cases.