The Tower of Hanoi is a classic mathematical puzzle invented by French mathematician Édouard Lucas in 1883. It features three rods and a stack of disks of different sizes.
The Rules
- Move one disk at a time.
- You can only move the top disk from any rod.
- A larger disk can never be placed on top of a smaller disk.
The Hidden Formula: 2ⁿ - 1
How many minimum moves does it take to transfer n disks from the first peg to the third peg?
- 1 disk:
2¹ - 1 = 1 move - 2 disks:
2² - 1 = 3 moves - 3 disks:
2³ - 1 = 7 moves - 4 disks:
2⁴ - 1 = 15 moves - 5 disks:
2⁵ - 1 = 31 moves
Each time you add one disk, the required moves double plus one! It is a brilliant visual introduction to exponential growth and binary patterns.