AI summary by TwinMind
The Hydra Game - Numberphile
Numberphile
21m 54s
Hydra Game Introduction
- Based on Hercules' second labor from Greek mythology
- Original myth: Hydra had 9 heads, when 1 chopped off, 2 grew back
- Hercules cheated using fire to prevent regrowth
- Mathematical version explores how many heads Hercules would actually need to chop
Game Rules Definition
- Uses rooted graph structure with single parent nodes tracing back to root
- Step 1: Pick leaf X (furthest point along branch)
- Step 2: Pick integer n (whole number)
- Step 3: Remove X
- Step 4: Add n new branches to X's grandparent (not parent)
- Repeat process until no heads remain
Hercules Example Calculation
- Starting configuration: 9 heads total
- 3 main stems from central body
- Each stem has 3 heads
- Maximum distance D = 2 from root
- Fixed n = 2 (2 heads grow back each time)
- Process:
- Chop off 9 original heads at distance 2
- Each removal adds 2 new heads to grandparent (root level)
- Results in 21 heads at distance 1 from root
- These 21 heads can be removed without regrowth (no grandparent exists)
- Total heads chopped: 30 (9 original + 21 final)
- Result independent of chopping order for this symmetric case
Game Termination Proof
- Question: Will game always end or could it run infinitely?
- Answer: Always terminates (proven by mathematical induction)
- Key insight: Maximum distance D between leaf and root
- Proof strategy:
- When D = 1: Kill shot - can remove all remaining heads without regrowth
- When D ≥ 2: Remove all heads at distance D
- New heads only grow at distance D-1 (never at same level or higher)
- Repeat process, reducing D by 1 each cycle
- Eventually reach D = 1, guaranteeing termination
- Numbers can grow very large but remain finite
Growth Rate Analysis (Fixed n)
- Mathematical formula derived using geometric series
- For distance D with W_d heads at each level:
- Total steps = W₁ + [(1-n²)/(1-n)]×W₂ + [(1-n³)/(1-n)]×W₃ + ... + [(1-n^D)/(1-n)]×W_D
- Hercules verification: 3 + [(1-4)/(1-2)]×9 = 3 + 3×9 = 30 ✓
- Growth involves exponential powers of n
- Even with fixed n, creates "exponential growth on steroids"
Rapid Growth Example
- Modified rules for extreme growth demonstration:
- Pick rightmost leaf (algorithmic approach)
- Variable n = step number (step 1: n=1, step 2: n=2, etc.)
- Simple straight-line graphs of length Y:
Results for Straight-Line Graphs:
- Y = 1: 1 step
- Y = 2: 3 steps
- Y = 3: 11 steps
- Y = 4: 98,338 steps
- Y = 5: Unknown - never computed despite proof it must terminate
Computational Complexity Mystery
- Dramatic jump from 11 → 98,338 → unknown
- Y = 5 case remains unsolved despite:
- Having proof of termination
- Seemingly simple rules
- Availability of powerful computers
- Suggests computational complexity beyond straightforward calculation
- Challenge issued to viewers to compute Y = 5 result
