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:
2 Rings = 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
2 RINGS = 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
2 RINGS = 3 MOVES
Move the 2 rings from Helper Tower 2 onto Target Tower 3 (3 legal moves, takes exactly 3 moves).
đĨ The Tower-Building Recipe:
3 Rings = 2 Ã (3) + 1 = 7 Moves
Next Tower = 2 Ã (Previous Tower) + 1
đ Master Rule: 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) | Minimum Moves | +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 Magic Formula
Minimum Moves = 2âŋ â 1
(where n = number of rings)
đĨ 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
10 Rings: 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 rule "Next Steps = 2 Ã Previous Steps + 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.