Tower of Hanoi
In the Tower of Hanoi you move a stack of disks from one peg to another, one disk at a time, never placing a larger disk on a smaller one. There are three pegs.
What is the minimum number of moves for 5 disks? What about n disks?
Show hint
To move the biggest disk, the other n − 1 disks must first be out of the way on the spare peg, and afterwards they must be moved back on top.
Show solution
31 moves for 5 disks, and 2n − 1 in general.
Moves(n) = Moves(n − 1) + 1 + Moves(n − 1) = 2 · Moves(n − 1) + 1, with Moves(1) = 1. That gives 1, 3, 7, 15, 31. It is a classic example of exponential growth from a simple recursion.
Want a problem like this every day? See today's problem and keep a streak going.