Zoals aangekondigd zit ik zonder wifi bovenop een Alpentop. En toch een blogpost. Omdat ik er eentje in de wachtrij heb gezet. Houd u vast. Dit wordt een lange zit. Het is tenslotte vakantie.
Ieder jaar wordt de internationale wiskunde olympiade georganiseerd, waar middelbare scholieren door het oplossen van wiskundeproblemen kunnen strijden om eeuwige roem (-; De wedstrijd duurt twee dagen. Beide dagen krijgen de deelnemers 3 puzzels voorgeschoteld, en hebben ze vier-en-een-half uur de tijd om die puzzels op te lossen. Een perfecte score is uitzonderlijk, en erg zeldzaam.
Een puzzel
Vandaag wil ik jullie iets vertellen over de zesde opgave van de wedstrijd van 1988. De zesde opgave is altijd de lastigste opgave, en de opgave die we nu bekijken is zelfs berucht om zijn moeilijkheid. (Ik geef meteen toe dat ik de opgave niet zelf heb opgelost zonder te spieken.) Verscheidene professionele wiskundigen kregen de opgave voorgeschoteld, maar konden deze harde noot niet binnen 6 uur kraken.
De opgave: Laat $a$ en $b$ twee gehele getallen zijn, met $a \ge 0$ en $b \ge 0$. Stel dat $(a \cdot b + 1)$ een deler is van $a^2 + b^2$. Dan is $\frac{a^2 + b^2}{a \cdot b + 1}$ een kwadraat.
Met andere woorden: Als de breuk $\frac{a^2 + b^2}{a \cdot b + 1}$ gelijk is aan een of ander geheel getal $k$, dan bestaat er een geheel getal $d$ zodat $k = d^2$.
Als u deze puzzel wilt oplossen zonder verdere tips, dan moet u nu stoppen met lezen.
Het plaatje
Om een beetje gevoel voor het probleem te krijgen, toon ik u nu de grafiek van $\frac{a^2 + b^2}{a \cdot b + 1}$.
Een eerste opmerking: In de opgave kijken we naar gehele getallen $a$ en $b$. In deze grafiek worden de waarden voor alle $a$ en $b$ op de getallenlijn getoond. Anders zouden we alleen een losse verzameling punten zien. Vanaf nu kijken we alleen nog maar naar punten $(a,b)$ waarbij $a$ en $b$ gehele getallen zijn.
De grafiek is dus enorm stijl dicht bij de assen, en heel erg vlak verder bij de assen vandaan. Er is ook een bepaalde symmetrie. Dat is niet toevallig, want de formule is ook symmetrisch in $a$ en $b$. Dus de waarde bij $(a,b)$ is gelijk aan de waarde bij $(b,a)$. Vanwege deze symmetrie mogen we in de opgave aannemen dat $a \le b$ geldt. Zo niet: dan verwisselen we $a$ en $b$ gewoon.
De gekleurde lijnen in het vlak op de bodem van de afbeelding zijn zogeheten contourlijnen. De rode lijn bestaat precies uit alle punten $(a,b)$ waarvoor $\frac{a^2 + b^2}{a \cdot b + 1} = 4$ geldt. Zoals te zien in het plaatje bestaat iedere contourlijn uit twee losse stukken. Een stuk met punten $(a,b)$ waarvoor $a < b$ geldt, en een stuk met punten $(a,b)$ waarvoor $a > b$ geldt.
Dat klopt niet helemaal. Er zijn natuurlijk ook nog de punten $(a,b)$ waarvoor $a = b$ geldt. Dat is de diagonaal in het vlak. Laten we eens kijken wat er bij die punten gebeurt. Dan geldt $\frac{a^2 + a^2}{a \cdot a + 1} = \frac{2a^2}{a^2 + 1} = k$. Dus $2a^2 = k \cdot (a^2 + 1) = k \cdot a^2 + k$. De waarden in de grafiek zijn positief, dus $k$ is positief. De enige manier waarop deze gelijkheid kan gelden is als $k = 1$. En… $1$ is een kwadraat. Dus voor de punten $(a,a)$ op de diagonaal is de opgave waar.
Aan de slag
Goed. Dan kunnen we nu terug gaan naar de punten $(a,b)$ met $a \ne b$, die dus niet op de diagonaal liggen. De opgave zegt dat als $a$ en $b$ gehele getallen zijn, en op de contourlijn van waarde $k$ liggen, dan is $k$ een kwadraat. Met andere woorden: Als $k$ geen kwadraat is, dan mag de contourlijn van $k$ dus geen enkel “gridpunt” bevatten. (Met een “gridpunt” bedoel ik een punt $(a,b)$ waarbij $a$ en $b$ gehele getallen zijn.)
Laten we dat dus maar proberen te doen. Neem een getal $k$, en bekijk de contourlijn van $k$. Zoals gezegd bestaat die uit twee delen. Het deel $H$ (hoog) van punten $(a,b)$ met $a < b$, en het deel $L$ (laag) van punten $(a,b)$ met $a > b$.
Twee gevallen
Nu gaan we een slimme truc toepassen. Dat gaat als volgt. Stel dat er een gridpunt $(a,b)$ bestaat in $H$, dus met $a < b$. Nu moeten we twee gevallen bekijken. Het geval $a = 0$, en het geval $a > 0$. Voordat we die gevallen bekijken, leg ik eerst uit wat de strategie is. In het geval $a = 0$ laten we zien dat $k$ een kwadraat is. En dus zijn we klaar. De opgave is voor dat geval bewezen.
In het andere geval, met $a > 0$ gaan we een nieuw gridpunt bouwen, zeg $(c,d)$, met de volgende eigenschappen: het punt $(c,d)$ ligt ook op $H$, en $d < b$. We hebben dan dus een nieuw gridpunt op $H$ met een kleinere $y$-coördinaat dan het oude punt. Nu kunnen we voor dit nieuwe punt weer de twee gevallen bekijken: ofwel $c = 0$, ofwel $c > 0$. Als $c = 0$ dan volgt opnieuw dat $k$ een kwadraat is. Als $c > 0$, dan kunnen we een nieuw gridpunt bouwen met een lagere $y$-coördinaat en… het proces herhaalt zich.
Maar het proces moet wel een keer stoppen! Want voor de punten $(x,y)$ op $H$ geldt $x < y$. En we vinden telkens een nieuw punt met een lagere $y$-coördinaat. Dus de $x$-coördinaat wordt ook steeds kleiner. Daarom moeten we na eindig veel stappen een keer een gridpunt vinden met $x = 0$. Zoals beloofd, is de opgave dan bewezen.
Terug naar ons oorspronkelijke punt $(a,b)$. Nu moeten we dus nog twee dingen doen: als $a = 0$ moeten we laten zien dat $k$ een kwadraat is, en als $a > 0$ dan moeten we een nieuw punt op $H$ maken met een kleinere $y$-coördinaat.
Stel dat $a = 0$. Dan zegt onze vergelijking $\frac{0^2 + b^2}{0\cdot b + 1} = k$. Oftewel $b^2 = k$. En, inderdaad. We zien dat $k$ een kwadraat is.
De sleutelsprong
Op naar het volgende geval. Stel dat $a > 0$. We moeten een gridpunt $(c,d)$ maken dat op $H$ ligt, dus $\frac{c^2 + d^2}{c \cdot d + 1} = k$ en $c < d$. Daarnaast willen we ook dat de $y$-coördinaat kleiner wordt, dus $d < b$.
Omdat ons punt $(a,b)$ op $H$ ligt, geldt $\frac{a^2 + b^2}{a \cdot b + 1} = k$. Dat kunnen we omschrijven naar $a^2 + b^2 = k \cdot (a \cdot b + 1)$. Die vergelijking kunnen we nog weer een beetje verder omschrijven naar $$b^2 – (a \cdot k) \cdot b + (a^2 – 1). \qquad (\star)$$
We zien dus dat $b$ een nulpunt is van de parabool $f(X) = X^2 – (a \cdot k) \cdot X + (a^2 – k)$. Kies nu het punt $c = a \cdot k – b$. Met een klein beetje rekenwerk zien we dat $g(X) = (X – b) \cdot (X – c) = X^2 – (b + c) \cdot X + (b \cdot c)$. Maar $b + c = a \cdot k$, en $$b \cdot c = b \cdot (a \cdot k – b) = a \cdot b \cdot k – b^2.$$ Over deze vergelijking kunnen we nog iets meer zeggen. Want we weten hebben ook vergelijking $(\star)$. Door deze twee vergelijkingen te combineren, vinden we $b \cdot c = a^2 – k$.
Dat is bijzonder! Dat betekent dat $f(X) = g(X)$, en dus dat $c$ ook een nulpunt is van de parabool $f(X)$. De twee formules $a \cdot k = b + c$ en $a^2 – k = b \cdot c$ staan bekend als de formules van Vieta. Dat is de Vieta uit de titel van deze blogpost. En nu komt de sprong van Vieta.
Omdat $c$ een nulpunt is van de parabool $f(X)$, weten we dat $$c^2 – (a \cdot k) \cdot c + (a^2 – k) = 0.$$ Dat kunnen we weer omschrijven naar $a^2 + c^2 = k \cdot (a \cdot c + 1)$, en dus naar $\frac{a^2 + c^2}{a \cdot c + 1} = k$. Met andere woorden: $(a,c)$ is een nieuw punt op de contourlijn van $k$! We zijn met de formules van Vieta naar een ander punt gesprongen.
Zoals gezegd bestaat de contourlijn van $k$ uit twee delen. Het deel $H$, met punten $(x,y)$ waarvoor $x < y$ geldt. En het deel $L$, met punten $(x,y)$ waarvoor $x > y$ geldt. Laten we nog een keer kijken naar een plaatje van de contourlijnen.
In dit plaatje zijn de contourlijnen geprojecteerd op het vlak. We kunnen hier een interessante observatie doen. Als we een contourlijn kiezen (dus een gekleurde lijn in het plaatje), dan zijn er voor iedere $x$-coördinaat maar twee mogelijke punten op de contourlijn. Een punt onder de diagonaal, en een punt boven de diagonaal. (Dit is natuurlijk geen bewijs, maar deze blogpost is lang genoeg. In het bijzonder is het niet duidelijk dat het nieuwe punt boven de $x$-as ligt. Een puzzeltje voor de enthousiaste lezer…)
Het punt $(a,c)$ ligt dus op de contourlijn van $k$. En het heeft dezelfde $x$-coördinaat als het punt $(a,b)$. Dus weten we dat $(a,c)$ onder de diagonaal ligt. Met andere woorden, $a > c$, en dus ligt $(a,c)$ in $L$.
Nu gebruiken we de spiegelsymmetrie die we helemaal aan het begin hebben opgemerkt. Als $(a,c)$ op de contourlijn van $k$ ligt, dan ook $(c,a)$. Omdat we spiegelen in de diagonaal, ligt $(c,a)$ in $H$. Inderdaad: $c < a$.
En nu zijn we klaar. We moesten een nieuw punt $(c,d)$ maken dat in $H$ ligt en een kleinere $y$-coördinaat heeft dan $(a,b)$, dus $d < b$. Welnu, $(c,a)$ ligt in $H$, en heeft $y$-coördinaat $a$. En zoals gezegd geldt $a < b$, omdat het oorspronkelijke punt $(a,b)$ ook in $H$ ligt.
Einde bewijs. QED.
Als u tot hier hebt door gelezen: mijn complimenten! En een hele fijne vakantie toegewenst.