Computing

Why one extra disc doubles the work: the Tower of Hanoi and 2ⁿ − 1

Five coloured discs stacked on the first of three pegs, with the formula 2ⁿ − 1 above
30seconds
The 30-second version

Move a stack of discs between three pegs, never putting a big disc on a small one. It sounds easy, and with 3 discs it is. But every extra disc doubles the work: the fewest moves is 2^n − 1.

Play it yourself, watch the perfect solution run, and drag a slider up to the legendary 64 discs, where the job would outlast the universe many times over.

Deep dive · 3 min
Deep dive · 3 min

More in Computing

View all →
Why sorting gets slow so fast: bubble sort versus merge sort and n log n Two sorting methods can both be perfectly correct and still differ by a factor of 25,000 on a big list. Race bubble sort against merge sort on the same… Computing3 min read How your phone finds the quickest route: Dijkstra's shortest-path algorithm Your phone finds the fastest route across millions of roads without trying them all. The trick is a rule Edsger Dijkstra devised in 1956: always finish the… Computing3 min read Why eight yes/no answers can draw a fractal, make noise or compute: elementary cellular automata Take a row of lit and dark squares and repeat one tiny rule to make the next row: look at a square and its two neighbours, then decide if it is lit. There are… Computing3 min read Why one flipped bit can be found and fixed: Hamming's error-correcting code A single flipped bit can turn a good file into garbage, yet a machine can find and repair it without ever seeing the original. In 1950 Richard Hamming, tired… Computing4 min read Why swapping cards at random is not a fair shuffle: Fisher–Yates and the 27 paths Shuffling three cards by swapping each one with a random card from the whole row looks fair, but it is not. It makes 3 × 3 × 3 = 27 equally likely paths for… Computing4 min read How to find one name among a billion in 30 looks: binary search Pick a number from 1 to 1,000,000 and you can find it in at most 20 yes-or-no questions. The trick is binary search: look in the middle of a sorted list, throw… Computing4 min read