The Tower of Hanoi
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.