Tower of Hanoi: Problem, Solution, and Proof¶
The Problem¶
The Tower of Hanoi is a classic puzzle that beautifully demonstrates the power of recursive thinking and mathematical induction. Here's how it works:
Setup¶
- Three pegs: A (source), B (auxiliary), C (destination)
- n disks of different sizes, initially stacked on peg A
- Initial state: All disks on peg A, largest at bottom, smallest at top
- Goal: Move all disks from peg A to peg C
Rules¶
- Move one disk at a time - only the top disk from any peg
- Never place a larger disk on a smaller disk - maintain size order
- Use peg B as auxiliary - temporary storage during the process
Visual Example (3 disks)¶
The Recursive Solution¶
Key Insight¶
To move n disks from A to C, we can break it into three steps: 1. Move n-1 disks from A to B (using C as auxiliary) 2. Move the bottom disk from A to C 3. Move n-1 disks from B to C (using A as auxiliary)
Recursive Algorithm¶
def hanoi(n, source, destination, auxiliary):
"""
Move n disks from source peg to destination peg using auxiliary peg.
Args:
n: number of disks to move
source: starting peg (e.g., 'A')
destination: target peg (e.g., 'C')
auxiliary: helper peg (e.g., 'B')
"""
if n == 1:
# Base case: move single disk directly
print(f"Move disk from {source} to {destination}")
else:
# Step 1: Move n-1 disks out of the way
hanoi(n-1, source, auxiliary, destination)
# Step 2: Move the bottom disk
print(f"Move disk from {source} to {destination}")
# Step 3: Move n-1 disks to destination
hanoi(n-1, auxiliary, destination, source)
Example: hanoi(3, 'A', 'C', 'B')¶
Execution trace:
hanoi(3, A, C, B):
├── hanoi(2, A, B, C):
│ ├── hanoi(1, A, C, B): Move disk from A to C
│ ├── Move disk from A to B
│ └── hanoi(1, C, B, A): Move disk from C to B
├── Move disk from A to C
└── hanoi(2, B, C, A):
├── hanoi(1, B, A, C): Move disk from B to A
├── Move disk from B to C
└── hanoi(1, A, C, B): Move disk from A to C
Step-by-Step Solution for 3 Disks¶
Let's trace through the complete solution with visual representations:
Initial State¶
Goal: Move all disks from A to CStep 1: Move disk 1 from A to C¶
Strategy: Start moving the top 2 disks (1,2) from A to B
Explanation: We can move the smallest disk directly. This is part of moving disks 1&2 to peg B.Step 2: Move disk 2 from A to B¶
Strategy: Continue moving top 2 disks to B
Explanation: Now we can move the medium disk to B since B is empty.Step 3: Move disk 1 from C to B¶
Strategy: Complete moving top 2 disks to B
Explanation: Place the small disk on top of the medium disk on B. Now disks 1&2 are on B, and we can move the large disk.Step 4: Move disk 3 from A to C¶
Strategy: Move the bottom disk to its final destination
Explanation: With the top 2 disks out of the way, we can move the largest disk directly to C.Step 5: Move disk 1 from B to A¶
Strategy: Start moving disks 1&2 from B to C (using A as auxiliary)
Explanation: To move disks 1&2 from B to C, we first move the small disk out of the way to A.Step 6: Move disk 2 from B to C¶
Strategy: Continue moving disks from B to C
Explanation: Now we can move the medium disk from B to C, placing it on top of the large disk.Step 7: Move disk 1 from A to C¶
Strategy: Complete the solution
Explanation: Finally, move the small disk from A to C. All disks are now on C in the correct order!Understanding the Recursive Structure¶
Notice how the solution follows our recursive algorithm perfectly:
Phase 1: Move top n-1 disks (1,2) from A to B¶
- Steps 1-3:
hanoi(2, A, B, C) - Move disks 1 and 2 from A to B using C as auxiliary
Phase 2: Move bottom disk (3) from A to C¶
- Step 4: Move the largest disk directly
- This is always just one move
Phase 3: Move n-1 disks (1,2) from B to C¶
- Steps 5-7:
hanoi(2, B, C, A) - Move disks 1 and 2 from B to C using A as auxiliary
Key Insights¶
- Recursive Pattern: Each phase follows the same pattern as the overall problem
- Auxiliary Peg: The auxiliary peg changes depending on what we're trying to accomplish
- Bottom Disk: The largest disk only moves once - directly to its destination
- Symmetry: Phase 1 and Phase 3 are mirror images of each other
Total moves: 7 = 2³ - 1 ✓
Proving the Number of Moves¶
The Formula¶
Claim: The minimum number of moves to solve the Tower of Hanoi with n disks is M(n) = 2ⁿ - 1.
Recursive Relation¶
From our algorithm, we can see that: - M(1) = 1 (base case: move one disk directly) - M(n) = M(n-1) + 1 + M(n-1) = 2M(n-1) + 1 for n > 1
This gives us the recurrence relation: M(n) = 2M(n-1) + 1
Proof by Mathematical Induction¶
Theorem: For all positive integers n ≥ 1, M(n) = 2ⁿ - 1.
Base Case (n = 1)¶
- M(1) = 1 (by definition - one move to transfer one disk)
- Formula: 2¹ - 1 = 2 - 1 = 1 ✓
- Base case holds.
Inductive Hypothesis¶
Assume that for some k ≥ 1, the formula holds: M(k) = 2ᵏ - 1
Inductive Step¶
We need to prove that M(k+1) = 2^(k+1) - 1.
From our recursive relation:
Using our inductive hypothesis (M(k) = 2ᵏ - 1):
This matches our formula for n = k+1. ✓
Conclusion¶
By mathematical induction, M(n) = 2ⁿ - 1 for all positive integers n ≥ 1.
Verification with Small Cases¶
| n | Calculated M(n) | Formula 2ⁿ - 1 | Match? |
|---|---|---|---|
| 1 | 1 | 1 | ✓ |
| 2 | 3 | 3 | ✓ |
| 3 | 7 | 7 | ✓ |
| 4 | 15 | 15 | ✓ |
| 5 | 31 | 31 | ✓ |
The Connection: Recursion ↔ Induction¶
This problem beautifully illustrates the deep connection between recursive algorithms and mathematical induction:
| Recursive Algorithm | Mathematical Induction |
|---|---|
Base case: if n == 1 |
Base case: Prove M(1) = 1 |
Recursive call: hanoi(n-1, ...) |
Inductive hypothesis: Assume M(k) works |
| Recursive structure: Break into smaller problems | Inductive step: Build M(k+1) from M(k) |
| Trust: Assume smaller cases work | Trust: Assume inductive hypothesis holds |
Exponential Growth and Real-World Impact¶
The Legend¶
According to legend, monks in a temple are working on a 64-disk Tower of Hanoi puzzle. When they complete it, the world will end.
The Mathematics¶
For n = 64 disks: - Number of moves: 2⁶⁴ - 1 = 18,446,744,073,709,551,615 - At 1 move per second: About 584 billion years - Universe age: About 13.8 billion years
Conclusion: We're safe! 😄
Why Exponential Growth Matters¶
This demonstrates why understanding algorithmic complexity is crucial: - Linear growth: Adding one disk doubles the work - Exponential problems become intractable very quickly - Recursive solutions can be elegant but expensive
Key Takeaways¶
- Recursive Structure: Complex problems can often be broken into smaller, similar subproblems
- Mathematical Induction: Provides the theoretical foundation for understanding why recursion works
- Base Cases Matter: Both recursive algorithms and inductive proofs need proper base cases
- Trust the Process: In recursion, we trust that smaller cases work; in induction, we trust the inductive hypothesis
- Exponential Complexity: Some problems grow exponentially, making them impractical for large inputs
Practice Problems¶
- Trace the algorithm: Work through
hanoi(4, 'A', 'C', 'B')by hand - Verify the formula: Calculate M(6) using both the recursive relation and the formula
- Modify the problem: What if we had 4 pegs instead of 3? How would this change the solution?
- Implementation: Code the Tower of Hanoi solution and test it with different values of n
Connection to Course Topics¶
This problem connects to several key concepts we're studying:
- CS 5001 (Programming): Recursive algorithms, function calls, problem decomposition
- CS 5002 (Mathematics): Mathematical induction, proof techniques, exponential functions
- Integration: How mathematical reasoning guides algorithmic design
The Tower of Hanoi is a perfect example of how mathematical thinking and programming skills reinforce each other!