AI summary by TwinMind
The Notorious Question Six (cracked by Induction) - Numberphile
Numberphile
28m 42s
Problem Introduction & Background
- Zvezda discusses legendary 1988 International Math Olympiad Problem 6 (Australia)
- She was 18 years old student who solved it in 20 minutes using induction with cubic polynomial
- Teammate Emanouil Atanassov won brilliancy award for simpler solution using quadratic polynomial
- This solution led to Zvezda receiving US scholarship recommendation from Australian committee
- Problem: Given natural numbers a,b where (a²+b²)/(1+ab) = r is integer, prove r is perfect square
Problem Statement & Setup
- Start with natural numbers a,b (positive integers ≥1)
- Ratio r = (a²+b²)/(1+ab) must be integer
- Must prove r is perfect square (1², 2², 3², etc.)
- Cannot be non-integers like 7/4 or non-perfect squares like 7
- Example: a=30, b=112 gives r=4 (which is 2²)
Solution Strategy Overview
- Fix ratio r as constant, vary pairs (a,b) that produce same r
- Extend allowed values to non-negative integers (including 0)
- Use quadratic equations and Vieta's formulas to find "phantom" twin roots
- Systematically reduce pairs until reaching one containing zero
- Apply finite induction to prove process always terminates
Detailed Example Walkthrough
- Starting pair: (30, 112) with r=4
- Rewrite original equation as quadratic: a² - (rb)a + (b²-r) = 0
- For a as unknown x: x² - (rb)x + (b²-r) = 0
- Vieta's formulas: sum of roots = rb, product = b²-r
- First attempt replacing a: x₂ = rb - a = 4(112) - 30 = 418 (larger, not helpful)
- Switch to reducing b: rewrite as b² - (ra)b + (a²-r) = 0
- New b value: y₂ = ra - b = 4(30) - 112 = 8
- New pair: (30, 8) still gives r=4
- Continue reducing: new a = 4(8) - 30 = 2, pair becomes (2, 8)
- Final reduction: new b = 4(2) - 8 = 0, pair becomes (2, 0)
- When b=0: r = 2²/1 = 4, confirming r is perfect square
General Proof Structure
- Fix arbitrary positive integer r and natural numbers a,b satisfying ratio
- Create quadratic equations for both variables
- Use Vieta's formulas: x₁ + x₂ = rb, y₁ + y₂ = ra
- Products: x₁x₂ = b²-r, y₁y₂ = a²-r
- Proof by contradiction: assume both replacements increase values
Contradiction Argument
- Assume a₂ ≥ a and b₂ ≥ b (no reduction possible)
- From Vieta's: a₂ ≥ a² and b₂ ≥ b²
- But product formulas give: aa₂ = b²-r and bb₂ = a²-r
- Adding: a² + b² - 2r ≥ a² + b²
- This implies -2r ≥ 0, so r ≤ 0
- Contradicts r being positive integer
- Therefore at least one pair must reduce
Finite Induction Process
- Algorithm always produces smaller pair in at least one step
- Continue until one coordinate becomes zero
- Process terminates in finite steps
- Final form: either (a_n, 0) or (0, b_n)
- Ratio becomes either a_n² or b_n², proving perfect square
- Can work backwards from (a,0) or (0,b) to generate all solutions
Historical Context & Anecdotes
- Zvezda finished all 3 problems in 1 hour 20 minutes, fell asleep during exam
- Terence Tao was in same room, didn't solve problem 6
- After exam, young Tao asked Zvezda for hint
- She said "induction on the product" - sufficient hint for Tao
- Problem considered one of most difficult in IMO history
- Many brilliant students including Tao couldn't solve it
- Demonstrates power of induction in number theory problems
