AI summary by TwinMind
Epic Induction - Numberphile
Numberphile
41m 13s
Introduction to Mathematical Induction
- Domino demonstration: finite induction (black dominoes) vs infinite induction (white dominoes)
- Induction as vehicle/scheme for proving mathematical statements
- Requires creative driver - induction doesn't provide answers, only proves conjectures
- Key limitation: need to know answer ahead of time
Subset Counting Problem (Warm-up)
- Problem: Find number of subsets for set with n elements
- Examples: 3 people → 8 groups, 4 people → 16 groups
- Pattern recognition: 2^n subsets for n elements
- Conjecture: S_n = 2^n for n ≥ 1
Induction Proof Structure
- Base Step (BS): n = 1
- One person A: subsets are {A} and {} (empty set)
- Total: 2 = 2^1 ✓
- Inductive Hypothesis (IH): Assume true for some n ≥ 1
- S_n = 2^n subsets exist
- Inductive Step: Prove for n+1 people
- Brady either selected or not selected
- Not selected: 2^n teams from remaining n people
- Selected: 2^n teams (add Brady to each subset of n people)
- Total: 2^n + 2^n = 2·2^n = 2^(n+1) ✓
- Conclusion: All statements S_n true for n ≥ 1
- Extension: Works for n = 0 (empty set has 1 subset: empty set)
Square Cutting Problem
- Problem: Cut square into n smaller squares (no overlaps, exact tiling)
- Initial exploration:
- n = 1: trivial ✓
- n = 4: window technique (cut in half vertically and horizontally) ✓
- n = 7: window one of the 4 squares → adds 3 more ✓
- Pattern: window technique adds 3 squares each time
Systematic Analysis
- Window technique sequence: 4 → 7 → 10 → 13 → 16...
- n = 6: Start with 9 squares, merge 4 into 1 large square ✓
- n = 8: Cut sides into 4 parts, create 1 large + 7 small squares ✓
- From n = 6: can reach 6, 9, 12, 15... (adding 3s via window technique)
- From n = 8: can reach 8, 11, 14, 17... (adding 3s via window technique)
Impossibility Proofs (Contradiction)
- n = 3: 4 corners, 3 squares → one square must cover 2 corners → covers entire square (contradiction)
- n = 5: 4 corners + 1 extra square
- Cannot cover 2 corners with one square
- Fifth square must be interior, but creates uncoverable edge pieces
- Enlarging corner squares to cover edges leads to overlaps
- n = 2: Left as homework
Strong Induction Formalization
- Base Steps: n = 6, 7, 8 (need multiple base cases)
- Inductive Hypothesis: All S_n true for n ∈ {6, 7, 8, ..., k}
- Inductive Step: Prove S_(k+1) true
- Use window technique: go back 3 steps to proven case
- Add window technique (+3) to reach k+1
- Safety barrier: 3 base cases prevent landing on impossible cases (2, 3, 5)
- Conclusion: Possible for all n ≥ 6
Direct Proof Alternative
- Even numbers (e.g., 2000): Cut side into 1000 parts, create grid with 1 large + 1999 small squares
- Formula: 1000 + 1000 + 1 - 1 = 2000 (subtract corner overlap)
- Odd numbers: Apply window technique to even case (+3)
- Still cannot achieve n = 5 (going back 3 from any valid case lands on n = 2, which is impossible)
Odd Pie Fight Problem
- Setup: Odd number of people (≥3) at pairwise different distances
- Rule: Each person pies their closest neighbor
- Claim: There is always at least one survivor (unpied person)
Base Case (n = 3)
- Scalene triangle with vertices L (Laurel), H (Hardy), B (Brady)
- Side lengths: a < b < c
- L and H are closest → pie each other
- B survives (pies someone but receives no pies)
Inductive Proof
- Inductive Hypothesis: S_(2n-1) true for n ≥ 2
- Inductive Step: Prove S_(2n+1) true
- Method: Take closest pair (L, H) who pie each other
- Remaining 2n-1 people play separate game → has survivor by IH
- In original game:
- No new pies fly into the smaller group (they have closer targets)
- Some pies may redirect from smaller group to L or H
- L and H cannot pie into smaller group (closest to each other)
- Survivor of smaller game remains unpied in original game
Even Numbers Counterexample
- n = 2: L and H pie each other, no survivor
- General even case (e.g., n = 18):
- Pair people into 9 couples
- Send to 9 different planets (distances between planets >> distances on planet)
- Each spouse pies their partner
- No survivors
Relaxed Conditions Analysis
- If equal distances allowed → no guaranteed survivor
- Counterexample: Equilateral triangle
- All pairwise distances equal
- Each person can choose whom to pie
- Possible configuration: L pies H, B pies L, H pies B → no survivor
- Conclusion: Pairwise different distances requirement is necessary
