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

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome