PROBLEEM

door Archimedes in versvorm bedacht en aan de

specialisten in Alexandria ter oplossing voorgelegd

in een brief aan Eratosthenes van Cyrene.

Vertaling: Hendrik Lenstra

1. Hoeveel runderen telde de Zonnegod? Reken dat uit, vriend,

2.    buig u erover met zorg, als ge het inzicht geniet.

3. Eertijds graasde zijn vee op de weilanden van het Sicilisch

4.    eiland Thrinacia, in vier kudden onderverdeeld,

5. al naar kleur onderscheiden: het vel bij de ene was melkwit,

6.    bij nummer twee lag een zwart glanzende kleur op de vacht,

7. dan kwam een bruine, en bont was de laatste. In iedere kudde

8.    waren de mannetjes sterk vertegenwoordigd. Van hun

9. aantallen lagen als volgt de verhoudingen. Neem van de zwarte

10.    stieren de helft, o vriend, reken een derde erbij,

11. tel het totaal bruinharige mee—zo kent ge de witte;

12.    maar van de bonte een kwart, met nog een vijfde erbij,

13. plus het totaal van de bruine—dat geeft u het aantal der zwarte.

14.    Hoeveel stieren tot slot bontgevlekt waren van kleur,

15. zie, dat beliep net een zesd’ en een zevende deel van de witte,

16.    waarbij dan weer gevoegd worde het bruine totaal.

17. Nu wat de wijfjes betreft, zo meld ik het volgende. Witte

18.    zag men precies evenveel als van het zwartgekleurd vee

19. —stieren en koeien tezamen—een derde geteld bij een vierde;

20.    maar de zwartharige, die waren van hun kant gelijk

21. aan het totaal van een kwart plus een vijfde gedeelte der bonte,

22.    als met de stieren tezaam die zich begaven ter wei.

23. Dan, van de rossige kudde een vijfde gevoegd bij een zesde,

24.    zo groot was het getal koeien bontkleurig van vel.

25. Aan bruinharige was er de helft van een derde gedeelte

26.    van al het witgekleurd vee, plus nog een zevende deel.

27. Noemt ge me nu nauwkeurig de omvang van Helios’ kudden,

28.    noemt ge apart het getal koeien van iedere kleur,

29. tevens de stevige stieren apart, zo, vriend, kunt ge gelden

30.    als in de rekenkunst niet onbekend noch onbekwaam,

31. doch zo telt ge nog niet als expert. Maar kom, onderzoek ook

32.    al wat ik verder vermeld over het vee van de Zon.

33. Zo vaak als met z’n alle de roomblanke stieren de zwarte

34.    opzochten, stonden ze dicht opgesteld in een figuur

35. dat naar lengte en breedte gelijk was, en deze immense

36.    massa vulde en bloc ’t wijde Thrinacische veld.

37. Maar als de bruine en bonte bijeenkwamen vormden ze rijen

38.    langzaam oplopend, één enkele stier in rij één,

39. samen een zuiver driehoekig figuur completerende, zonder

40.    één stier anders van kleur, zonder dat één er ontbrak.

41. Analyseert ge dit, vriend, uw geestkracht erop concentrerend,

42.    geeft ge me omvang en tal al dezer menigten aan,

43. ga dan, beroem u op uw overwinning, en weet hoe het oordeel

44.    zeker zal luiden: dat gij ’t opperste inzicht bezit.

Zoals je in het bovenstaande gedicht kunt lezen wordt gevraagd te bepalen hoeveel runderen de zonnegod Helios heeft. Deze grazen vredig in vier kudden op het eiland Thrinacia. In regels 9 tot en met 26 staat in woorden een aantal vergelijkingen beschreven waar de aantallen witte, zwarte, gevlekte en bruine runderen aan moeten voldoen. In regels 27 – 30 staat dat je een goede rekenaar bent als je die vergelijkingen kunt oplossen – je verdient dan het cijfer 8 voor je werk. Maar als je een 10 wilt verdienen –laten zien dat je het “opperste inzicht bezit” – dan moet je het uitgebreide probleem oplossen; daarbij worden extra eisen aan de aantallen opgelegd. Je zult zien dat je voor die 10 hard moet werken.

De runderen van Helios worden ook in boek 12 van de Odyssee genoemd. Daar wordt vermeld dat er zeven kuddes runderen zijn en zeven kuddes schapen elk vijftig hoofden groot. Dat levert overzichtelijke aantallen van 350 runderen en 350 schapen. De oplossingen van de problemen van Archimedes leveren veel grotere aantallen runderen.

Circe had Odysseus gewaarschuwd geen van de dieren te slachten, want dan zouden hij en zijn mannen streng gestraft worden. De mannen van Odysseus sloegen de waarschuwing in de wind en slachtten de beste van de dieren op het eiland. Dat liep inderdaad niet goed af: alle mannen verdronken door toedoen van Zeus op zee, behalve Odysseus, die na een lang verblijf bij Kalypso uiteindelijk toch terug naar Ithaca kon reizen.

 

Het eerste probleem

Zoals gezegd zijn er stieren en koeien van vier kleuren: geheel wit, geheel zwart, gevlekt en geheel bruin. Er zijn meer stieren dan koeien en er zijn relaties tussen de acht aantallen gegeven. Laten we met $W$, $Z$, $G$, en $B$ de aantallen witte, zwarte, gevlekte en bruine stieren aangeven, en met $w$, $z$, $g$, en $b$ de verschillende aantallen koeien. De relaties laten zich als volgt weergeven. Uit regels 9–11 halen we informatie over de witte stieren

$$(1)\qquad W = (\frac12 + \frac13 )Z + B$$

dan geven regels 12 en 13 informatie over de zwarte stieren

$$(2)\qquad Z = (\frac14 + \frac15)G + B$$

en regels 14–16 gaan over de gevlekte stieren

$$(3)\qquad G = (\frac16 + \frac17)W + B$$

Dan komt er informatie over de aantallen koeien. Over de witte koeien zien we in regels 17–19 dit

$$w = (\frac13 + \frac14)(Z + z),$$

in regels 20–22 staat over de zwarte koeien dit

$$z = (\frac14 + \frac15)(G + g),$$

over de gevlekte koeien lezen we in regels 23 en 24

$$g = (\frac15 + \frac16)(B + b)$$

en ten slotte zeggen regels 25 en 26 dit over de bruine koeien

$$b = (\frac16+ \frac17)(W + w)$$

Dit probleem heeft een flauwe oplossing: nul runderen van alle soorten. Dat is natuurlijk niet de bedoeling; je verwacht dat de zonnegod toch wel wat runderen zal hebben.

Als je naar de vergelijkingen kijkt zie je er zeven, met acht onbekenden. Dat betekent dat er inderdaad oplossingen ongelijk aan de nuloplossing te vinden moeten zijn: we verwachten ten minste één vrijheidsgraad. Denk aan één vergelijking met twee onbekenden als $3x - 4y = 0$: één van de variabelen is dan in de andere uit te drukken en die andere is vrij te kiezen. Zoiets geldt ook als je twee vergelijkingen met drie onbekenden hebt.

Om die oplossingen te vinden moet je systematisch te werk gaan: telkens onbekenden uit vergelijkingen elimineren tot je ziet welke onbekende vrij te kiezen is en hoe de andere daar van afhangen.

Als je eerst naar de stieren kijkt en $W$ uit vergelijking $(3)$ elimineert door vergelijking $(1)$ in te vullen, en daarna $Z$ elimineert krijg je $G = \frac{1580}{891} B$.  Als je dat in $(2)$ invult komt er $Z = \frac{1602}{891} B$ en ten slotte vind je dan $W = \frac{2226}{891} B$. Als je dan $B = 891$ kiest vind je de volgende oplossing, alleen voor de stieren:

$$(W, Z, G, B) = (2226, 1602, 1580, 891)$$

met in totaal $6299$ stieren dus. Maar elk veelvoud van de oplossing is er ook een; we hebben oneindig veel oplossingen:

$$(W, Z, G, B) = s \cdot (2226, 1602, 1580, 891)$$

met $s$ een willekeurig natuurlijk getal. Maar dit is nog steeds alleen voor de stieren. Met nog meer werk kun je in de overige vergelijkingen $w$, $z$, $g$, en $b$ ook in $B$ uitdrukken.

Als je stug volhoudt dan zul je vinden dat de $s$ in de oplossing voor de stieren een veelvoud van 4657 moet zijn, dus $s = 4657 \cdot k$.

De aantallen koeien zijn dan te schrijven als

$$k ⋅ (7206360, 4893246, 3515820, 5439213)$$

in de volgorde $(w, z, g, b)$, net als bij de stieren. De aantallen stieren worden dus

$$k \cdot 4657 \cdot (2226, 1602, 1580, 891)$$

(met telkens dezelfde $k$ natuurlijk). De kleinste, die met $k = 1$, levert dan in totaal $50.389.082$ runderen.

In ieder geval geeft ons dit (veel) meer runderen dan beschreven in de Odyssee.

Het uitgebreide probleem

Als je wilt laten zien dat je een getallenmeester bent moet je een oplossing vinden die aan de volgende voorwaarden voldoet: als de witte en de zwarte stieren bij elkaar gaan staan dan kunnen ze een vierkant vormen (regels 33–36), en de gevlekte en bruine stieren kunnen bij elkaar in een mooie driehoek gaan staan (regels 37–40). Dat betekent dat $W + Z$ een kwadraat moet zijn en $G + B$ een driehoeksgetal. Een driehoeksgetal is een getal dat je door middel van stippen in een driehoek kan leggen; ze zijn van de vorm $1 + 2 + … + n$ en dus te schrijven als $\frac12 n (n+ 1)$.

Met andere woorden: we moeten $k$ zo bepalen dat $W + Z = 4657 \cdot 3828 \cdot k$ een kwadraat is en $G + B = 4657 \cdot 2471 \cdot k$ een driehoeksgetal.

Om te beginnen met $W + Z$: ontbind $ 4657 \cdot 3828$ in factoren, $2^2 \cdot 3 \cdot 11 \cdot 29 \cdot 4657$ (ja, $4657$ is een priemgetal). Om

$$W+ Z = 2^2 \cdot 3 \cdot 11 \cdot 29 \cdot 4657 \cdot k$$

een kwadraat te laten zijn moet $k$ dus van de vorm $3 \cdot 11 \cdot 29 \cdot 4657 \cdot l^2$ zijn.

Nu $G + B$. Als $D = \frac12 n (n+1)$ een driehoeksgetal is dan is $8D + 1 = (2n + 1)^2$ een kwadraat, en omgekeerd. Dus $8(G + B) +1$ moet een kwadraat zijn, zeg $m^2$.

Als we dat invullen komt er

$$m^2 = 8 \cdot 4657 \cdot 2471 \cdot k + 1,$$

met $k = 3 \cdot 11 \cdot 29 \cdot 4657 \cdot l^2$ wordt dat

$$m^2 = 8 \cdot 4657 \cdot 2471 \cdot 3 \cdot 11 \cdot 29 \cdot 4657 \cdot l^2 + 1$$

of, helemaal uitgeschreven:

$$(*)\qquad m^2 = 410.286.423.278.424 \cdot l^2 + 1$$

of, iets korter

$$(**)\quad m^2 = 4729494 \cdot (2 \cdot 4657 \cdot l)^2 + 1$$

Nu hoeven we alleen nog oplossingen van vergelijking (*) te vinden; het blijkt minder werk te zijn vergelijking (**) op te lossen, dat wil zeggen, eerst

$$m^2 = 4729494 \cdot n^2 + 1$$

oplossen en onder de oplossingen die $n$-en zoeken die een veelvoud van $2 \cdot 4657$ zijn.

 

De Pell-vergelijking

Een vergelijking van de vorm als boven, $m^2 = d \cdot n^2 + 1$, staat bekend als een Pell-vergelijking. Over dit soort vergelijkingen is veel bekend, onder andere dat ze voor elke $d$ die geen kwadraat is oneindig veel oplossingen hebben en dat die oplossingen een speciale structuur hebben.

Om te beginnen: je schrijft de vergelijking meestal als $m^2 – dn^2 = 1$. Dan kun je het linkerlid ontbinden:

$$(m + n \sqrt{d}) (m - n \sqrt{d}) = 1.$$

Daaraan kun je zien dat de oplossingen misschien iets met $\sqrt{d}$ te maken hebben. En dat is ook zo.

We bekijken eerst eens $d = 2$. Dan kun je makkelijk een oplossing gokken: $m = 3$ en $n = 2$. want $3^2 = 2 \cdot 2^2 + 1$.

Hoe maken we meer oplossingen?

Dat kan als volgt: merk op dat $(\sqrt{2} - 1) (\sqrt{2} + 1) = 2 - 1 = 1$.

Dat kun je schrijven als

$$(\natural) \qquad \sqrt2-1=\frac1{\sqrt2+1}$$

of

$$\sqrt2=1+\frac1{\sqrt2+1}$$

Nu kun je $\sqrt2+1$ omschrijven tot $2+\sqrt2-1$, dus

$$\sqrt2-1=\frac1{2+\sqrt2-1}$$

maar dan kun je $\sqrt2-1$ vervangen door het rechterlid in $(\natural)$:

$$\sqrt2=1+\frac{1}{2+\frac{1}{2+\sqrt2-1}}$$

en nog een keer

$$\sqrt2=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\sqrt2-1}}}$$

en nog een keer

$$\sqrt2=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\sqrt2-1}}}}$$

je krijgt een oneindig lange kettingbreuk:

$$\sqrt2=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{\ddots}}}}}$$

Dit werkt als volgt: je kapt die breuk telkens af:

$$1, 1+\frac12, 1+\frac{1}{2+\frac{1}{2}},1+\frac{1}{2+\frac{1}{2+\frac12}},1+\frac{1}{2+\frac{1}{2+\frac1{2+\frac12}}}, \ldots$$

en werkt die partiële breuken uit:

$$1, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}, \ldots$$

De rij rationale getallen die je zo krijgt convergeert naar $\sqrt2$.

Kijk nu naar de breuken $\frac32$ en $\frac{17}{12}$, hun tellers en noemers geven telkens een oplossing van de vergelijking $m^2=2n^2+1$. De eerste hadden we all en de tweede vullen we even in: $17^2=289=288+1=2\cdot12^2+1$.

Hier zit een heleboel theorie achter. Zo kun je bijvoorbeeld bewijzen dat de partiële breuken om en om kleiner en groter zijn dan het getal waar het om gaat, in dit geval $\sqrt2$. Voor $\sqrt2$ geldt dan dat elke even partiële breuk een oplossing levert van $m^2=2n^2+1$.

 

Opgave 1

Bereken nu de zesde breuk en bepaal zo nog een oplossing van de vergelijking $m^2=2n^2+1$.

 

Er zit nog meer achter deze rij breuken. Bekijk het getal $3+2\sqrt2$ en kwadrateer het:

$(3+2\sqrt2)^2=9+12\sqrt2+8=17+12\sqrt2$. Daar herkennen we de tweede oplossing van de vergelijking.

 

Opgave 2

Bereken $(3+2\sqrt2)^3$ en ga na dat je de derde oplossing van daarnet krijgt.

 

Er geldt zelfs meer: als je $(3+2\sqrt2)^p$ uitwerkt en schrijft als $m_p+n_p\sqrt2$ met natuurlijke getallen $m_p$ en $n_p$ dan krijg je zo precies de oplossingen van $m^2=2n^2+1$.

 

Opgave 3

Kijk eens of je kunt bewijzen dat je zo inderdaad oplossingen van $m^2-2n^2=1$ krijgt.

(Bewijzen dat er niet meer oplossingen zijn is moeilijker en vergt wat algebra.)

 

In Pythagoras 36-5, juni 1997, staat een artikel van Peter Stevenhagen over het vinden van getallen die zowel een kwadraat als een driehoeksgetal zijn; ook dat probleem leidt tot de Pell-vergelijking $m^2-2n^2=1$ èn de omgekeerde Pell-vergelijking $2n^2-m^2=1$. Daar kun je zien dat de oneven partiële breuken nu net oplossingen leveren van de tweede vergelijking. Ook wordt daar voor de tellers en de noemers van de hele rij breuken aangetoond dat die voldoen aan de betrekking $a_{k+1}=2a_k+a_{k-1}$. Voor de tellers begin je met $m_1=1$ en $m_2=3$, en voor de noemers begin je met $n_1=1$ en $n_2=2$.

 

Meer werk

We zijn nog niet helemaal klaar. Aan het oplossen van willekeurige vergelijkingen van de vorm $m^2=d\cdot n^2+1$ zitten nog een paar haken en ogen. Dat zie je goed bij $d=13$. We schrijven de kettingbreuk even in een wat overzichtelijkere notatie:

$$[3;1,1,1,1,6,1,1,1,1,6,1,1,1,1,6,\ldots]$$

Hieraan kun je zien dat de rij getallen die je krijgt periodiek is, in dit geval met periode $5$.

Bekijk de eerste tien breuken: $\frac31$, $\frac41$, $\frac72$, $\frac{11}2$, $\frac{18}5$, $\frac{119}{33}$, $\frac{137}{38}$, $\frac{256}{71}$, $\frac{393}{109}$, en $\frac{649}{180}$, en schrijf telkens $m^2-13n^2$ op ($m$ is de teller, $n$ is de noemer). Je krijgt $-4$, $3$, $-3$, $4$, $-1$, $4$, $-3$, $3$, $-4$, en $1$.

Dit illustreert twee dingen: de breuken die echt belangrijk zijn horen bij de periode; daar is het verschil $m^2-13n^2$ het kleinst in absolute waarde, namelijk $1$. En door het om en om kleiner en groter zijn dan $\sqrt d$ van de breuken moet je bij een oneven periode wachten tot de dubbele periode voor je een oplossing van $m^2=d\cdot n^2+1$ vindt. (De vijfde levert een oplossing van de omgekeerde Pell-vergelijking $13n^2-m^2=1$.)

Dit hadden we, achteraf, ook bij $m^2-2n^2=1$ gezien: de periode was daar gelijk aan $1$ en elke tweede breuk gaf ons een oplossing van de vergelijking $m^2-2n^2=1$.

Voor onze vergelijking

$$m^2=4729494n^2+1$$

betekent dit dat je eerst de periode voor de kettingbreuk van $\sqrt{4729494}$ op moet sporen. Dat werd in 1880 door A. Amthor gedaan, de periode is $92$. Nu is dat gelukkig even, dus je hoeft maar $92$ diep te gaan in de kettingbreuk om de eerste oplossing te vinden. De getallen die je krijgt zijn behoorlijk groot: $m_1=10.993.198.673.289.734.979.866.232.821.433.543.901.088.049$ en $n_1=50.549.485.234.315.033.074.477.819.735.540.408.986.340$. Maar dan zijn we er nog niet, we moeten een oplossing $(m_p,n_p)$ hebben waarbij $n_p$ een veelvoud van $2\cdot 4657$ is. Daar kwam nog meer Algebra en Getaltheorie bij kijken.

Het bleek dat

$$(m_1+n_1\sqrt{4729494})^{2329}$$

een oplossing van de grotere Pell-vergelijking $(*)$ oplevert. Die oplossing is heel erg groot, en levert uiteindelijk een totaal aantal runderen op van $206545$ cijfers. Dat lijkt me wel een kudde de Zonnegod waardig.

Als je meer wilt weten over de oplossing en wat er allemaal bij komt kijken dan moet je het artikel Solving the Pell equation van Hendrik Lenstra maar eens opslaan: http://www.ams.org/notices/200202/fea-lenstra.pdf. Daarin staan formules voor alle mogelijke oplossingen van het probleem. Daar kun je ook lezen waarom het geen toeval is dat $2329=(4657+1)/2$.

Rond 1980 werd dit probleem gebruikt om een (toen) nieuwe supercomputer te testen, de CRAY-1. De computer had zo'n tien minuten nodig om alle berekeningen te doen. Het totaal aantal runderen uit de kleinste oplossing werd afgedrukt en beslaat 47 pagina's. Je kunt het vinden in: Harry L. Nelson, A solution to Archimedes' cattle problem. Journal of Recreational Mathematics 13 (1980/81), no. 3, 162--176.