A tower and a doubling
Show on a big screenMove a stack of discs to another peg, one at a time. A big disc never sits on a small one. A peg is an upright stick that holds discs.
Loading lab…
- Both discs start on peg A.
- Move 1: small disc to peg B.
- Move 2: big disc to peg C.
- Move 3: small disc to peg C. Done in 3.
The rule
This puzzle is the Tower of Hanoi. The spare peg is neither the start peg nor the target peg. To move n discs, follow three steps.
- Move the top n − 1 discs to the spare peg.
- Move the biggest disc once.
- Move those n − 1 discs onto the biggest disc.
The stack of n − 1 discs moves twice. The biggest disc moves once.
moves for n discs = 2 × (moves for n − 1 discs) + 1
One disc needs 1 move. Two discs need 2 × 1 + 1 = 3. Three need 2 × 3 + 1 = 7. Four need 2 × 7 + 1 = 15. Five need 2 × 15 + 1 = 31.
| Discs | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Moves | 1 | 3 | 7 | 15 | 31 | 63 |
| Moves + 1 | 2 | 4 | 8 | 16 | 32 | 64 |
The last row doubles every time. So moves + 1 is 2ⁿ, and the moves are 2ⁿ − 1.
This is proved, not only seen. It proves the three steps use 2ⁿ − 1 moves. Suppose n discs use m moves. Then n + 1 discs use 2m + 1 moves. Add 1: 2m + 2 = 2 × (m + 1). So moves + 1 doubles with every extra disc.
Ten discs need 2¹⁰ − 1 = 1024 − 1 = 1023 moves.
Try the lab to finish this lesson.