The Tower of Hanoi
Inductive Reasoning & Recursion
Scan to Follow
🗼 The Rules of Hanoi: Legal Moves vs. Violations
Rule 1: Move only 1 disk at a time • Rule 2: Never place larger on smaller!
⚠️ The 2 Golden Rules of Hanoi
SACRED LAWS
1. Move only one disk at a time.
2. A larger disk can never sit on a smaller disk.
2. A larger disk can never sit on a smaller disk.
✅ DEMONSTRATION: The Legal Move
VALID
Move exactly one top disk at a time to an open peg or larger disk.
❌ COUNTER-EXAMPLE 1: "Greedy Grab"
FORBIDDEN
Grabbing 2 or more disks at once is strictly illegal.
Golden Rule 1: Move ONLY ONE disk at a time!
Golden Rule 1: Move ONLY ONE disk at a time!
❌ COUNTER-EXAMPLE 2: "Crush Hazard"
FORBIDDEN
Placing a large disk on top of a smaller disk is strictly illegal.
Golden Rule 2: A larger disk can NEVER sit on a smaller disk!
Golden Rule 2: A larger disk can NEVER sit on a smaller disk!
🗼 The 2-Ring Base Case: Finding Minimal Moves
Start: 2 rings stacked on Tower 1. Move both to Tower 3!
Start: 0 Moves
Mission: Transfer all rings from Tower 1 to Tower 3 in the fewest possible moves!
🎯 Objective: 2-Ring Base Case
How many moves are required to transfer 2 rings to Tower 3? Let's count step-by-step!
MOVE 1: Small Ring (Tower 1 → 2)
STEP 1
Move Ring 1 out of the way to the Helper Tower (Tower 2).
MOVE 2: Big Ring (Tower 1 → 3)
STEP 2
With the path clear, move largest Ring 2 to Target Tower (Tower 3).
MOVE 3: Small Ring (Tower 2 → 3)
STEP 3
Reunite Ring 1 onto Tower 3, resting securely on top of Ring 2.
✨ Base Case Result:
a₂ = 3 Moves
For 2 rings, the absolute minimum number of moves is 3!
🧩 The 3-Ring Breakthrough: The Recursive Leap
Start: 3 rings stacked on Tower 1. How do we move them to Tower 3?
Initial: 3 Rings on Tower 1
Key Insight: Don't move single rings randomly — think in 3 Macro-Phases!
PHASE 1: Clear the Top 2 Rings
a₂ = 3 MOVES
Move top 2 rings from Tower 1 to Helper Tower 2 (3 legal moves using our base case: 3 moves).
PHASE 2: Move the Base King Disk
1 MOVE
With the bottom clear, move largest Ring 3 directly from Tower 1 to Tower 3 in 1 move.
PHASE 3: Rebuild the Top 2 Rings
a₂ = 3 MOVES
Move the 2 rings from Helper Tower 2 onto Target Tower 3 (3 legal moves, takes exactly 3 moves).
🔥 The Golden Recursive Formula:
a₃ = 2·a₂ + 1 = 7
aₙ = 2 · aₙ₋₁ + 1
👉 Master Rule: Next Steps = 2 × Previous Steps + 1
"Double the steps of the smaller tower, then add 1 for the King!"
🏆 Pattern Recognition & The 10-Ring Challenge
📊 The Inductive Discovery Table
| Rings (n) | Least Moves (aₙ) | +1 Discovery | Power of 2 Formula |
|---|---|---|---|
| 1 | 1 | 1 + 1 = 2 | 2¹ − 1 = 1 |
| 2 | 3 | 3 + 1 = 4 | 2² − 1 = 3 |
| 3 | 7 | 7 + 1 = 8 | 2³ − 1 = 7 |
| 4 | 15 | 15 + 1 = 16 | 2⁴ − 1 = 15 |
Universal General Formula
aₙ = 2ⁿ − 1
🔥 The Grand Challenge
Suppose the ancient monks give you a 10-Ring Tower.
What is the minimum number of moves required?
What is the minimum number of moves required?
Applying the Formula: n = 10
a₁₀ = 2¹⁰ − 1 =
?
1,023 Moves!
💡 Pro Mental Math: 2¹⁰ = 1,024, so 1,024 − 1 = 1,023 steps!
⚡ 10-Ring Speed Run
Move: 0 / 1,023
Speed:
🎊 Math Superpower Unlocked! 🎊
From 2 golden rules to recursion and exponential powers!
You have mastered the ancient secrets of the Tower of Hanoi!
You have mastered the ancient secrets of the Tower of Hanoi!
🚀 After-Class Mastery: Test Your Superpowers!
Challenge 1: 5-Ring Tower
How many minimum moves are needed to transfer a 5-ring Tower of Hanoi?
Minimum moves:
Challenge 2: 6-Ring Tower
Using the recursive formula aₙ = 2·aₙ₋₁ + 1, calculate the moves for 6 rings.
Minimum moves:
Challenge 3: 8-Ring Challenge
An Australian Mathematics Competition puzzle has 8 disks. Find the least steps needed.
Minimum steps:
Challenge 4: Ancient Myth (Bonus)
Temple monks are moving 64 golden rings at 1 move per second. How many steps in total?
Total steps:
ℹ️
Standard Setup: All challenges follow the classic 3-peg (3-tower) setup under the two sacred laws.