Curiosa Mathematica [version 2 Sep 2019 ed.] [PDF]

Zitiervorschau

Curiosa Mathematica

Jens Bossaert

cba CC BY-SA 4.0: Creative Commons Attribution–ShareAlike . International You are free to: • Share: copy and redistribute the material in any medium or format. • Adapt: remix, transform, and build upon the material for any purpose, even commercially. Under the following terms: • Attribution: you must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in a way that suggests the licensor endorses you or your use. • ShareAlike: if you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.



Inhoudsopgave

Getaltheorie  Perfecte getallen . . . . . . .  Moessners magie . . . . . . .  Zeef van Erd˝os–Jabotinsky .  Egyptische breuken . . . . .  N-piramide . . . . . . . . . .  Eigenschap van Juzuk . . . .  De aap en de kokosnoten . . ˇ  Sindelsequenties . . . . . . .  Veelhoeksgetallen . . . . . .  Kerstmisstelling van Fermat

. . . . . . . . . .

         

Combinatoriek  Magische zeshoeken . . . . . . . .  Formule van Cayley . . . . . . . .  -puntenprobleem . . . . . . . .  Vermoeden van Erd˝os–Gy´arf´as .  Kruskals bomenstelling . . . . . .  Identiteit van Proizvolov . . . . .  Superpermutaties . . . . . . . . . .  Kirkmans schoolmeisjesprobleem

       

Algebra  Gershgorincirkels .  Sturmketens . . . . .  Formules van Vieta .  Stelling van Marden  Solitaire . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . .

. . . . .

. . . . . . . . . .

. . . . .

. . . . .

    

Analyse  Formule van Wallis . . . . . . . . .   Integraal van Gauss . . . . . . . . 

 Stelling van Sharkovsky . . . . . .   Gemiddelden . . . . . . . . . . . .  Kansrekening  Parkeerprobleem van R´eyni . . . .   Kwartet van Anscombe . . . . . .   Paradox van Bertrand . . . . . . .  Meetkunde  Hyperbolische meetkunde  Schoenveterformule . . . .  Haberdasherpuzzel . . . . .  Voderbergbetegelingen . .  G¨omb¨ocs . . . . . . . . . .  Cirkel van Conway . . . . .  Mirakel van Morley . . . .  Stelling van Erd˝os–Anning  Kaartprojecties . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

        

Varia  Lindenmayersystemen . . . . . .  Lexicodes . . . . . . . . . . . . .  Conways soldaten . . . . . . . .  Arrows onmogelijkheidsstelling  Paradox van Braess . . . . . . . .  Tropische wiskunde . . . . . . .  Conways look-and-say-rij . . . .

. . . . . . .

      

Logica

Quotes Index

Getaltheorie

1

Perfecte getallen

Nogal wat culturen doorheen de geschiedenis begiftigden bepaalde families van getallen met religieuze of magische eigenschappen, en de perfecte getallen vormen een ideaal voorbeeld. Deze werden in het bijzonder bestudeerd door de oude Grieken; zo bewees Euclides in zijn magnum opus de Elementen een voldoende voorwaarde voor perfectie van even getallen, die tevens een noodzakelijke voorwaarde bleek. Concreet noemt men een getal perfect als deze gelijk is aan de som van al diens strikte delers. Het kleinste perfecte getal is , want  +  +  = . Ook  voldoet, want  +  +  +  +  = . Nogal wat exegeten hebben beweerd dat het scheppingsverhaal in de Hebreeuwse Bijbel niet toevallig over zes dagen geschiedt, of de maan in  dagen rond de aarde heen draait, maar dat deze getallen juist de perfectie van de schepping in de verf zetten. De volgende twee perfecte getallen ( en ) waren de Grieken eveneens bekend, maar de volgende werden pas veel later ontdekt: in Europa duurde het tot de de eeuw vooraleer een onbekende wiskundige de vijfde () vond, en in de de eeuw kon Pietro Cataldi de zesde () en de zevende () identificeren. Enkele eeuwen daarv´oo´ r had Egyptisch wiskundige Ismail ibn Fall¯us die drie ook ontdekt, samen met enkele foutieve. De perfecte getallen vormen uiteindelijk de rij [] beginnend met , , , , , , , , . . . Wiskundig is het iets eleganter om een functie σ op de natuurlijke getallen in te voeren, σ ∶ N ∖ {} → N ∖ {} ∶ n ↦ ∑ d, d∣n

die een natuurlijk getal n ≠  afbeeldt op de som van al diens delers, inclusief het getal n zelf. Dan is duidelijk dat n een perfect getal is als en slechts als σ(n) = n. Het voordeel van deze karakterisatie is dat σ aan enkele handige eigenschappen voldoet, zoals multiplicativiteit. Lemma. De functie σ is multiplicatief: als a en b copriem zijn, dan is σ(a ⋅ b) = σ(a) ⋅ σ(b). Bewijs. De assumptie dat a en b copriem zijn, betekent dat elke deler van ab op unieke wijze het product is van een deler van a met een deler van b. Met andere woorden, iedere term in de som σ(ab) komt ook precies e´e´n keer voor in σ(a) ⋅ σ(b) en vice versa. ∎ De helft van de volgende stelling is de constructie van Euclides, een getaltheoretische climax die boek IX van zijn Elementen afsluit. Pas zo’n twee millennia later werd duidelijk dat deze constructie alle even perfecte getallen oplevert, zoals Leonhard Euler in  bewees ([]).



Stelling (Euclides–Euler). De even perfecte getallen zijn precies de natuurlijke getallen van de vorm k−1 ⋅ (k − ), waarbij k ⩾  en k −  een priemgetal is. Bewijs. E´en richting lukt best rechttoe-rechtaan dankzij de eigenschap dat σ multiplicatief is. Beschouw immers een getal n van de vorm k−1 ⋅ (k − ) met k −  priem, dan is σ(n) = σ(k−1 ) ⋅ σ(k − ) = ( +  +  + ⋯ + k−1 ) ⋅ ( + (k − )) = (k − ) ⋅ k = n, zodat n inderdaad een perfect getal blijkt. Anderzijds, beschouw een even perfect getal n, en schrijf n = k−1 ⋅ d met d oneven en k ⩾ . Dan volgt dat k ⋅ d = n = σ(n) = σ(k−1 ) ⋅ σ(d) = (k − ) ⋅ σ(d). De oneven factor k −  ⩾  in het rechterlid moet een deler zijn van d links. Deel deze factor links en rechts weg en vul de twee reeds gekende delers van d in: k ⋅

d d k ⋅ d = σ(d) = d + + (eventuele andere delers) = + (andere delers). k −  k −  k − 

Deze gelijkheid kan enkel kloppen als er geen andere delers meer zijn! Met andere woorden, er moet gelden dat d = k −  en dat d bovendien priem is, wat het bewijs vervolledigt. ∎ Bemerk dat de priemgetallen van de vorm k −  de zogenaamde Mersennepriemgetallen zijn (zie curiosum ??) en impliceren dat k zelf ook priem is. Ook is het best interessant dat de even perfecte getallen binair uitgeschreven aan een mooie regelmaat voldoen dankzij hun vorm k−1 ⋅ (k − ): eerst k bits 1 gevolgd door k −  bits 0.  = 1102  = 111002  = 1111100002  = 11111110000002  = 11111111111110000000000002  = 1111111111111111100000000000000002 De resultaten van Euclides en Euler karakteriseren enkel de even perfecte getallen, dus het is een heel natuurlijke vraag hoe het zit in het oneven geval. Verrassend genoeg is het antwoord op die vraag nogal ontnuchterend: na meer dan twee millennia is het nog steeds niet geweten of er ook oneven perfect getallen bestaan! Ren´e Descartes gaf in een brief aan Marin Mersenne in  toe dat hij geen enkele reden zag waarom er geen oneven exemplaar zou kunnen bestaan. Hij beschreef ter illustratie het getal n =  = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ . Daarvoor zou σ(n) = ( +  + 2 ) ⋅ ( +  + 2 ) ⋅ ( +  + 2 ) ⋅ ( +  + 2 ) ⋅ ( + ) = n,



tenminste, mocht de factor  = 2 ⋅  een priemgetal zijn. . . Helaas ontbreken er dus enkele termen in deze berekening en blijkt de correcte waarde σ(n) > n, maar Descartes schreef dat het best mogelijk was dat een andere factor wel zou werken. James Sylvester uitte zich w´el overtuigd dat de constructie van Euclides alle perfecte getallen genereert. Hij slaagde er onder andere in te bewijzen dat een oneven perfect getal ten minste zes verschillende priemfactoren zou moeten hebben en schreef ([]): I hope, numine favente, sooner or later to discover a general principle which may serve as a key to a universal proof of the non-existence of any other than the Euclidean perfect numbers, for a prolonged meditation on the subject has satisfied me that the existence of any one such—its escape, so to say, from the complex web of conditions which hem it in on all sides—would be little short of a miracle. Thus then there seems every reason to believe that Euclid’s perfect numbers are the only perfect numbers which exist! Getuige de moeilijkheid van het probleem zei Sylvester bovendien ([]): Whoever shall succeed in demonstrating the absolute non-existence of odd perfect numbers will have solved a problem of the ages comparable in difficulty to that which previously to the labors of Hermite and Lindemann environed the subject of the quadrature of the circle. Vandaag zijn er reeds vele strenge eigenschappen afgeleid waaraan oneven perfecte getallen zouden moeten voldoen en lijkt het bestaan van zo’n getal erg onwaarschijnlijk. Het kleinste exemplaar zou alleszins al groter dan 1500 moeten zijn ([]) en uit minstens  priemdelers zijn opgebouwd, waarvan zeker  verschillende en zeker e´e´n groter dan 8 . Het is niet moeilijk in te zien dat perfecte getallen steeds harmonisch zijn (zie curiosum ??), en ook in deze algemenere context vermoedt men dat oneven getallen uitgesloten zijn. Een andere veralgemening bespreken we in curiosum ??.

[1] L. Euler, De numeris amicibilibus. Commentationes Arithmeticae, vol. 2, 1849, p. 627–636. [2] P. Ochem, M. Rao, Odd perfect numbers are greater than 101500 . Mathematics of Computation, vol. 81, no. 279, 2012, p. 1869–1877. [3] J. Sylvester, Note on a proposed addition to the vocabulary of ordinary arithmetic. Nature, vol. 37, no. 946, 1887, p. 152–153. [4] J. Sylvester, On the divisors of the sum of a geometrical series whose first term is unity and common ratio any positive or negative integer. Nature, vol. 37, no. 957, 888, p. 417–418. [5] S. Wagon, Perfect numbers. Mathematical Intelligencer, The Evidence, vol. 7, no. 2, 1985, p. 66–68. [6] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A000396.



2

Moessners magie

Start met een lijst van alle natuurlijke getallen, schrap elk tweede getal, en neem van de overblijvende getallen de cumulatieve som. De resulterende getallen zijn precies de kwadraten. , , ×

, ×

, , ×

, ×

, , ×

, ×

, , ×

, , × , ×

, , × , ×

, , × , ×

, , × , ×

, . . . ×

Schrappen we in het begin elk derde getal, nemen we de cumulatieve som, schrappen we vervolgens elk tweede getal en sommeren we nogmaals, dan staan er precies de derdemachten. , , , ×

, , ×

, ×

, , , ×

, , ×

, ×

, , , , , × ×

, ×

, , , , , × ×

, ×

, , , ×

, , ×

, ×

, . . . , , ×

Zoals Alfred Moessner in  ([]) opmerkte, blijkt dit proced´e voor algemene n op te gaan; schrap ieder n-de getal, sommeer, schrap ieder (n − )-de getal, sommeer. . . en uiteindelijk blijven zo precies de n-de machten over. Voor n =  bijvoorbeeld: , , , , ×

, , , ×

, , ×

, ×

, , , , ×

, , , , , × ×

, ×

, , , , , , , , × , × ×

, , , , × , , , , , × , × ×

, . . . ×

Moessner heeft nooit een bewijs voor zijn vondst gepubliceerd; het eerste bewijs was van de hand van Oskar Perron ([]) hetzelfde jaar en opende de deur naar allerlei andere bewijzen en veralgemeningen. Een variant van Ivan Paasche bijvoorbeeld vertrekt vanuit het schrappen van de driehoeksgetallen , , , , , . . . en resulteert opmerkelijk genoeg in de faculteiten! , ×

, , ×

, ×

, , , ×

, , ×

, ×

, , , , , , , × ×

, , ×

, , , , , × , , , , , , , × , , × , × ×

, , × , , , , , ×

... ... ... ... ... ...

Door te vertrekken van de getallen , , , , , . . . (waartussen de verschillen driehoeksgetallen zijn) vinden we de zogenaamde superfaculteiten, n!! = n! ⋅ (n − )! ⋯ ! ⋅ ! ⋅ !



, ×

, , , ×

, , ×

, ×

, , , , , , , , , , , , , , × , , , × , , × , × ×

, ×

, , , , , , , , , , ×

, , , , , , , , , , , 1054, , 1388, 2442, , 2372, 4814, 1272, 3644, 8458, 1560, 5204, × 1848, × ×

, , , 1521, 3963, 8777, ×

, , , 2109, 6072, ×

... ... ... ... ...

Over het algemeen, als we starten met de getallen van de vorm links te schrappen, vinden we de getallen van de vorm rechts als resultaat. a1 = x1 , a1 + a2 = x2 , a1 + a2 + a3 = x3 , a1 + a2 + a3 + a4 = x4 , ⋮

a1  ⋅ a2 a1 ⋅ a2 ⋅ a3 a1 ⋅ a2 ⋅ a3 ⋅ a4 a1

⇒

= = = = ⋮

y1 , y2 , y3 , y4 ,

[1] D. Kozen, A. Silva, On Moessner’s theorem. The Mathematical Gazette, vol. 66, no. 438, 1982, p. 273–277. [2] C. Long, Strike it out—add it up. The American Mathematical Monthly, vol. 120, no. 2, 2013, p. 131–139. [3] A. Moessner, Eine Bemerkung u¨ ber die Potenzen der nat¨urlichen Zahlen. Sitzungsberichten der Bayerischen Akademie der Wissenschaften, vol. 3, 1951, p. 29. [4] O. Perron, Beweis des Moessnerschen Satzes. Sitzungsberichten der Bayerischen Akademie der Wissenschaften, vol. 4, 1951, p. 31–34.



3

Zeef van Erd˝os–Jabotinsky

Kies een natuurlijk getal n > . Rond dit getal langs boven af naar het eerstvolgende veelvoud van n − , daarna dit resultaat naar een veelvoud van n − , enzovoort tot een veelvoud van . In symbolen, definieer recursief u1 = n,

u i+1 = ⌈

ui ⌉ ⋅ (n − i) n−i

voor alle i ⩽ n. Bijvoorbeeld voor n =  geeft dit proces de tussenstappen 11

10

9

8

7

6

5

4

3

2

1

 Ð→  Ð→  Ð→  Ð→  Ð→  Ð→  Ð→  Ð→  Ð→  Ð→  Ð→ . Het beeld van onze startwaarde n onder deze procedure noteren we als z(n). Ook al verloopt de afleiding van z(n) schijnbaar redelijk chaotisch, toch is er een sterke asymptotische regelmaat van kracht; er geldt immers dat n2 z(n) = + O(n4/3 ), π met deze verbazingwekkende limietwaarde als gevolg: n2 lim = π. n→∞ z(n) Paul Erd˝os en Eri Jabotinsky bestudeerden in [] een alternatieve en algemenere constructie (vergelijkbaar met de zeef van Eratosthenes voor priemgetallen) die in een speciaal geval tot dezelfde rij leidt. Begin met de rij der positieve natuurlijke getallen en schrap elke k-de term, te beginnen met volgnummer k − , voor k = . Herhaal dit schrappen op de resterende rij voor k = , daarna k = , et cetera: (k = ) (k = ) (k = )

, , , ,

, , , , , , , , , , , , , , , , , . . . , × , × , × , × , × , × , × , × , . . . , , , × , , × , , . . . , , , , , × , . . .

De resterende getallen vormen precies de rij z(), z(), z(), z(), . . .

[1] P. Erd˝os, E. Jabotinsky, On a sequence of integers generated by a sieving process. Indagationes Mathematicae, vol. 61, 1958, p. 115–128. [2] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A002491.



4

Egyptische breuken

Tot ’s werelds oudst gekende geschriften behoort het zogeheten Rhindpapyrus, een Egyptisch document dat Schots antiquaar Henry Rhind in  in Luxor opkocht en dat na diens dood in het British Museum terechtkwam, waar de meerderheid van de archeologische vondst tot op heden wordt bewaard. Het document werd geschreven door een klerk genaamd Ahmes, die in de inleiding ‘een grondige studie voor inzicht in alle bestaande dingen en alle duistere geheimen’ belooft. Na deze ambitieuze aanvang beschrijft Ahmes uiteindelijk niet veel meer dan  praktische wiskundige problemen (met uitwerking van hun oplossing) plus een tabel met expansies voor rationale getallen van de vorm /n naar het Egyptische getallensysteem, alles bedoeld voor dagdagelijkse situaties. De vraagstukken vari¨eren tussen vermomde lineaire vergelijkingen, rudimentaire algoritmes en meetkundige volumeformules, en geven blijk van onder meer een bescheiden begrip van rekenkundige en meetkundige reeksen. Bij een uitwerking voor het volume van een cilinder blijkt ook de benadering π ≈ / te bespeuren. De papyrus geeft ook inzicht in hoe Egyptenaren getallen voorstellen. Hun systeem was best eenvoudig: alle machten van tien tot aan een miljoen hadden een eigen symbool, die zonder vaste volgorde bij elkaar werden geplaatst.

| = , 2 = , 3 = , 4 = , 5 = , 6 = , 7= . Zo betekende bijvoorbeeld

33 22|| = . 554332||||| Ook breuken waren de Egyptenaren bekend, maar slechts op een curieuze, restrictieve vorm. Men schreef een mondvormig symbool boven een getal om de inverse ervan voor te stellen, zodat bijvoorbeeld  . = 

r 2| 33322

Zo’n stambreuken werden vervolgens samengeteld om andere rationale getallen te bekomen. De enige restrictie was dat men doorgaans geen twee identieke termen in een representatie schreef, maar bijvoorbeeld enkel een som / + / + / voor het getal /. Als uitzondering werden soms nog aparte symbolen gebruikt voor de getallen / en /. Waarom de Egyptenaren zich tot dit systeem beperkten is niet zo duidelijk. Ronald Graham bestudeerde stambreuken in zijn PhD-thesis en vroeg Andr´e Weil om een verklaring, die na wat nadenken verklaarde, “It is easy to explain. They took a wrong turn!”



Ahmes behandelde in zijn papyrus enkele technieken om met breuken te rekenen. Daartoe illustreerde hij de noodzaak om effici¨ent breuken te verdubbelen met een uitgebreide tabel van Egyptische representaties voor getallen van de vorm /n. Er zijn meerdere schrijfwijzes mogelijk voor eenzelfde breuk en het is helemaal niet duidelijk op welke manier de Egyptenaren deze vonden—al zitten er een aantal algemene technieken tussen de  problemen en een uitgesproken voorkeur voor weinig termen en kleine noemers. Voor veelvouden van drie en vijf beschrijft Ahmes bijvoorbeeld de formules       = + , = + , n n n n n n die onder te brengen zijn in de algemeen geldige formule    = + , n +  n +  (n + )(n + ) en een van Ahmes’ vraagstukken komt in essentie neer op de algebra¨ısche ontbinding     ⋅ = + .  n +  (n + ) (n + ) Tot in de middeleeuwen bleef het Egyptisch getalsysteem standhouden. Uiteindelijk haalde het Arabische systeem echter de bovenhand in Europa, niet in het minst dankzij Fibonacci’s magnum opus Liber Abaci, waarin hij onder andere een aantal numerieke stelsels vergeleek. Zelf hanteerde Fibonacci een gemengde notatie voor rationale getallen, tussen Egyptische en moderne breuken in; hij gaf ook enkele manieren om rationale getallen in Egyptische vorm om te zetten. Voor gevallen waarop alle andere methodes faalden, suggereerde Fibonacci ook een gretig algoritme, in volle besef dat die niet altijd tot een handige stambreuksom leidt: . Gegeven een breuk  < a/b <  met a ≠ , bepaal eerst het getal n = ⌈b/a⌉, waarvoor   a ⩽ < . n b n− . Bereken de restterm

a ′ a  an − b = − = . b′ b n bn

. Als a ′ =  is de ontbinding compleet; herhaal anders het proces op de breuk a′ /b ′ . De keuze van n in de eerste stap garandeert dat a(n − ) < b ⩽ an, waaruit a ′ = an − b < a; de nieuwe term heeft met andere woorden strikt kleinere teller dan de oorspronkelijke term, en het algoritme zal dan ook altijd eindigen. Soms is het resultaat best aanvaardbaar, zoals     = + + ,     terwijl voor / dit algoritme een expansie in tien termen geeft, waarvan de laatste noemer meer dan  decimalen lang is! Toch bestaat er een relatief eenvoudige representatie als      = + + + .     



Een lichte wijziging in Fibonacci’s algoritme leidt tot een oneindige Egyptische representatie voor het getal , door voor elke nieuwe term n = ⌊b/a⌋ +  te kiezen (in plaats van n = ⌈b/a⌉). Dan verkrijgen we dat =

       + + + + + + +⋯       

De noemers van deze ontbinding vormen de zogeheten rij van Sylvester ([]), en voldoen aan de eigenschap dat elke term gelijk is aan het product van alle voorgaande termen, plus e´e´n. Door de reeks na de eerste k termen af te breken en van de laatste noemer e´e´n af te trekken, bekomen we eindige Egyptische sommen voor  van arbitraire lengte k.  =

              + = + + = + + + = + + + + = ⋯              

Zonder de aanpassingen aan de laatste noemers blijven er nog steeds de beste benaderingen van het getal  langs onder staan tussen alle Egyptische sommen van dezelfde lengte. Egyptische breuken kunnen tot boeiende en pittige wiskundige problemen leiden. Een voorbeeld is het vermoeden van Erd˝os–Strauss, dat al sinds  onopgelost blijft. Dit vermoeden stelt dat ieder rationaal getal van de vorm /n (met n ⩾ ) kan worden geschreven als de som van precies drie stambreuken. Er zijn enkele algemene patronen bekend (zoals voor getallen van de vorm hieronder) en computerberekeningen hebben alle natuurlijke getallen tot in 14 geverifieerd, maar het probleem is nog steeds niet in volle algemeenheid gekraakt!  k  k +   k +   k + 

   + + , k k +  k(k + )    = + + , k +  k +  (k + )(k + )    = + + , k +  k +  (k + )(k + )    = + + . k +  (k + )(k + ) (k + )(k + ) =

Ook varianten zoals het vermoeden van Waclaw Sierpi´nski met teller  in plaats van , staan nog open. De meest algemene variant werd geformuleerd door Andrzej Schinzel en beweert dat voor eender welke teller slechts een eindig aantal uitzonderingsgevallen bestaan. Het maakt trouwens niet uit of we de drie stambreuken verschillend eisen of niet, aangezien     + = + , k k k +  k(k + )

    + = + . k +  k +  k +  (k + )(k + )

De restrictie dat de stambreuken positief moeten zijn is w´el een essentieel obstakel, want als we ook negatieve termen toelaten, bestaat er een algemene oplossing voor oneven noemers:     = + − . k +  k k +  k(k + )(k + )



Een andere interessante onderzoekspiste is om de vorm van de termen te beperken in plaats van het aantal. Zo is een mooi resultaat uit [] het feit dat ieder natuurlijk getal te schrijven is als een Egyptische som van verschillende stambreuken, waarbij elke noemer een product is van precies drie priemgetallen. De auteurs vermoeden tevens dat hetzelfde resultaat opgaat met producten van twee priemgetallen als noemers, maar ook dat is nog niet bewezen. Allan Johnson vond een ontbinding van het getal  in  dergelijke termen ([]):         + + + + + + + ⋅ ⋅ ⋅  ⋅   ⋅   ⋅   ⋅   ⋅          + + + + + + + +  ⋅   ⋅   ⋅   ⋅  ⋅ ⋅  ⋅   ⋅          + + + + + + + +  ⋅   ⋅   ⋅   ⋅   ⋅   ⋅  ⋅  ⋅          + + + + + + + +  ⋅   ⋅   ⋅   ⋅   ⋅   ⋅   ⋅   ⋅          + + + + + + + +  ⋅   ⋅   ⋅   ⋅   ⋅   ⋅   ⋅   ⋅          + + + + + + + + = .  ⋅   ⋅   ⋅   ⋅   ⋅   ⋅   ⋅   ⋅ 

[1] S. Butler, P. Erd˝os, R. Graham, Egyptian fractions with each denominator having three distinct prime divisors. Integers: The Electronic Journal of Combinatorial Number Theory, vol. 15, 2015, A51, p. 1–9. [2] A. Johnson, Letter to the editor. Grux Mathematicorum, vol. 4, no. 7, 1978, p. 190. [3] O. Neugebauer, Vorlesungen u¨ ber Geschichte der antiken mathematischen Wissenschaften: Vorgriechische Mathematik. Springer-Verlag, 2013. [4] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A000058.



5

N-piramide

Er bestaat een eenvoudig maar elegant patroon in de natuurlijke getallen:

  +   +  +   +  +  + 

 + +  + +  + +  + +  +

     

+ + + + + +

     

= = = = = =

,     

+ , +  + +  + +  + +  +

,  + ,  +  + ,  +  +  + ,

enzovoort. Een bewijs hiervoor lukt heel rechtstreeks en is niet veel moeilijker. Bewijs. Beschouw de kde rij, die uit k +  termen bestaat. De eerste term van het linkerlid is precies  +  +  + ⋯ + (k − ) = k 2 , de laatste term k 2 + k. Via de somformule van Gauss blijkt de som van het linkerlid dus gelijk aan (k + ) ⋅

(k 2 ) + (k 2 + k)  = k(k + )(k + ).  

De eerste term van het rechterlid is k 2 + k + , de laatste term k 2 + k. De som is dus k⋅

(k 2 + k + ) + (k 2 + k)  = k(k + )(k + ),   ∎

precies gelijk aan de som van het linkerlid. Voor deze identiteiten bestaat ook een mooi visueel bewijs (hier ge¨ıllustreerd voor k = ).

=

=

[1] C. Alsina, R. Nelsen, Charming proofs: a journey into elegant mathematics. Mathematical Association of America, 2010.



6

Eigenschap van Juzuk

In  stelde Dov Juzuk een interessante manifestatie vast van de vierdemachten. Stelling. Schrijf de natuurlijke getallen neer in groepjes van e´e´n, twee, drie. . . getallen. ,

, ,

, , ,

, , , ,

, , , , ,

, , , , , ,

, , , . . .

, , , , , ,

, , , . . .

Schrap vervolgens ieder tweede groepje uit de lijst. ,

, ,

, , ,

, , , ,

, , , , ,

De som van de getallen in de eerste n overblijvende groepjes is dan precies gelijk aan n4 . Bewijs. We bewijzen dit via volledige inductie, en de uitspraak klopt op triviale wijze alvast voor n = . Merk op dat het k-de groepje getallen (v´oo´ r het schrappen) per constructie k getallen bevat, eindigt met het k-de driehoeksgetal k(k + )/, en zodus begint met (k − )k/ + . De som van dit groepje noteren we als S k en valt met de formule van Gauss makkelijk te berekenen. Sk =

k(k + ) k (k − )k ⋅( ++ ) = 21 k(k 2 + ).   

Na het schrappen is de som van de eerste n +  groepjes precies gelijk aan S1 + S3 + ⋯ + S2n+1 waarvan de eerste n termen volgens de inductiehypthese al sommeren tot n4 . De totale som is dan inderdaad S1 + S3 + ⋯ + S2n+1 = n4 + 21 (n + )((n + )2 + ) = n4 + n3 + n2 + n +  = (n + )4 . ∎

[1] D. Juzuk, Curiosa . Scripta Mathematica, vol. 6, 1939, p. 218.



7

De aap en de kokosnoten

Op  oktober  konden de lezers van The Saturday Evening Post een kortverhaal Coconuts van Ben Ames Williams ([]) lezen. In het verhaal trachtte een aannemer om een belangrijk contract binnen te rijven door een rivaal bezig te houden met volgend wiskundig raadsel. Vijf onfortuinlijke zeelieden spoelen aan op een verlaten eiland, dat bewoond blijkt door een aap. Ze besteden de eerste dag aan het verzamelen van kokosnoten. Alles wordt op een stapel gegooid en de vijf lieden gaan slapen. Even later schiet de eerste man terug wakker met de vrees dat er wel eens ruzie zou kunnen uitbreken tijdens het verdelen van de kokosnoten. Hij besluit om zijn deel van de buit alvast veilig te stellen en verdeelt alle kokosnoten in vijf gelijke stapels. Er blijft e´e´n kokosnoot over, die hij aan de aap geeft; hij verbergt zijn stapel, gooit de rest terug samen op een hoop en gaat slapen. Dan wordt de tweede man wakker en herhaalt het verhaal zich: hij verdeelt de hoop kokosnoten in vijf gelijke stapels, geeft e´e´n resterende kokosnoot aan de aap, gooit de rest terug samen en gaat slapen. De derde, vierde en vijfde man doen hetzelfde, telkens met e´e´n kokosnoot die overblijft voor de aap. De volgende dag wordt de hoop verdeeld en bekomen ze precies vijf gelijke porties (zonder overblijvende kokosnoten voor de aap). Uiteraard had iedereen door dat er kokosnoten ontbraken maar aangezien iedereen zich schuldig had gemaakt durfde niemand bekennen. Hoeveel kokosnoten verzamelden de schipbreukelingen de eerste dag in totaal? In het verhaal kwam de oplossing niet ter sprake. De volgende dagen werd het hoofdkantoor van The Saturday Evening Post overspoeld door zo’n  brieven van lezers die de oplossing wilden weten, in zodanige mate dat de redacteur een telegram stuurde naar Williams: FOR THE LOVE OF MIKE, HOW MANY COCONUTS? HELL POPPING AROUND HERE. Tot  jaar na publicatie bleef Williams lezersbrieven ontvangen over deze kokosnootpuzzel. Williams heeft het raadsel nochtans niet zelf verzonnen, maar een veel ouder raadsel lichtjes aangepast—in het originele vraagstuk kreeg de aap ook tijdens de uiteindelijke verdeling nog een laatste resterende kokosnoot toegegooid. Noemen we in de originele vraagstelling n het totale aantal kokosnoten, x1 , . . . , x5 het aantal kokosnoten dat de mannen afzonderlijk houden, en r het aantal eerlijk verdeelde kokosnoten, dan leidt de vraag tot het stelsel n = x1 + ,

x1 = x2 + ,

x2 = x3 + ,

x3 = x4 + ,

x4 = x5 + ,

x5 = r + .



Zo’n lineair stelsel is meestal rechttoe-rechtaan op te lossen, maar hier moeten we rekening houden met het feit dat alle variabelen natuurlijke getallen moeten zijn. Hoe dan ook vallen de termen x1 , . . . , x5 eenvoudig te elimineren tot n=

     6 5 4 3 2  ( ( ( ( (r + ) + ) + ) + ) + ) +  = 5 r + 5 + 4 + 3 + 2 + + ,           

zodat na vereenvoudiging

n = r + .

Deze lineaire vergelijking oplossen is best uitdagend zonder hulpmiddelen. Men ziet snel in dat wanneer (n, r) een oplossing vormt, dan ook (n + , r + ); in dat geval bestaan er dus oneindig veel oplossingen. De kleinste oplossing vinden is nog steeds geen kinderspel, tenzij we tijdelijk negatieve getallen toelaten! Na wat proberen blijkt immers (n, r) = (−, −) een “oplossing” voor het raadsel: een totale hoop van vier “negatieve” kokosnoten wordt dan opgedeeld in vijf stapels met elk e´e´n negatieve kokosnoot, waarna de aap e´e´n positieve noot krijgt en er opnieuw vier negatieve kokosnoten overblijven. Dit herhaalt zich nog vier maal en tot slot krijgt ieder nog een laatste negatieve kokosnoot bij de finale verdeling. Natuurlijk vormt dit nog geen geldige oplossing, maar de bovenstaande observatie leidt tot de correcte en minimale oplossing n = − +  = . Een andere manier om het antwoord te vinden—zonder trucjes maar met meer rekenwerk— bestaat erin om de termen in de lineaire vergelijking niet meteen te vereenvoudigen, maar eerst uit te werken als een meetkundige reeks. 5 n = 6 r + (5 +  ⋅ 4 + 2 ⋅ 3 + 3 ⋅ 2 + 4 ⋅  + 5 ) = 6 r + 5 ⋅

 − (/)6 = 6 r + 6 − 6  − /

Dit leidt tot het inzichtelijkere verband 5 ⋅ (n + ) = 6 ⋅ (r + ). Omdat beide leden natuurlijke getallen voorstellen, is het duidelijk dat 6 =  een deler van n +  moet zijn, en de kleinste waarde van n waarvoor dit geldt is n = . In de variant van Williams blijkt de minimale oplossing iets bescheidener: daar verzamelden de schipbreukelingen in totaal “slechts” n =  kokosnoten.

[1] G. Antonick, Martin Gardner’s the monkey and the coconuts. The New York Times, Numberplay, 2013. [2] M. Gardner, Concerning the celebrated puzzle of five sailors, a monkey and a pile of coconuts. Scientific American, Mathematical Games, vol. 198, no. 4, 1958, p. 118–125. [3] B. Williams, Coconuts. Saturday Evening Post, vol. 199, no. 15, 1926, p. 10.



ˇ Sindelsequenties

8

De Praˇzsk´y Orloj is een vernuftige astronomische klok, gebouwd in de Tsjechische hoofdstad Praag in . Op de klok valt onder meer de lokale tijd en datum af te lezen in verschillende tijdrekeningen, de zonsopgang en zonsondergang, de positie van de zon in de dierenriem en de positie van de maan, inclusief de maanfasen. De Orloj is de oudste astronomische klok ter wereld die nog steeds operationeel is (weliswaar na meerdere grondige renovaties, zoals recent nog in ) en is een toeristische trekpleister van Praag, niet in het minst omwille van de “parade van de twaalf apostelen” die elk uur plaatsvindt boven de klok. ˇ ˇ De astronomische klok werd ontworpen door Jan Ondˇrej˚uv, ook wel Sindel genoemd. Sindel was professor in de wiskunde en astronomie en tijdens de bouw van de klok tevens rector aan de Universiteit van Praag. Behalve historisch en astronomisch is de klok ook boeiend op wiskundig vlak. Er zit namelijk een verrassende eigenschap verborgen in het systeem dat zorgt voor het luiden van de klok om het uur. De Orloj volgt het -urensysteem en slaat dus in totaal  +  +  + ⋯ +  =  keer gedurende e´e´n dag. Dit wordt geregeld via een groot tandwiel met  tanden, die langs de rand  zorgvuldig geplaatste inkepingen heeft. Elk uur gaat een stopmechanisme omhoog en schuift het wiel herhaaldelijk e´e´n tand op, vergezeld van een klokslag, tot het mechanisme in de volgende inkeping valt. 







 



 ⋮

⋮



Bij immense astronomische klokken zoals die van Praag zijn onnauwkeurigheden (door bijvoorbeeld slijtage of weerseffecten) uiteraard problematisch. Voor het luiden van de klokken is een ingenieus mechanisme ingebouwd om de precisie te verscherpen. Het gaat concreet om een tweede, kleinere tandwiel met  tanden en zes inkepingen in de volgende vorm: 





 





Het grote wiel (met  tanden) maakt exact e´e´n volledige rotatie per etmaal. Het kleine wiel (met  tanden) wordt aangedreven door een overzetmechanisme, en maakt dan  rotaties per etmaal. Het slaan van de klok stopt pas wanneer het stopmechanisme bij de beide wielen in een inkeping valt.  



  



 ⋮

⋮



Het kleine wiel helpt onregelmatigheden opvangen, terwijl geen enkele inkeping in het grote wiel wordt overgeslagen. Dit wordt gegarandeerd door een bijzondere sommatie-eigenschap van de periodieke rij die het kleine tandwiel bepaalt—de rij , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , . . . Alle getallen tot en met  zijn achtereenvolgens terug te vinden door termen te groeperen! , , , , , , , , , , , ,             , , , , , , ,        , , , , .      Straffer nog, het blijkt dat deze eigenschap verder te zetten valt ad infinitum: door termen te groeperen kan achtereenvolgens e´lk natuurlijk getal gevonden worden. Merk op dat het voor de klok volstaat om tot aan  te geraken op voorwaarde dat het tandwiel om middernacht terug op diens startpositie staat. Voor de Praagse klok vormt dit geen probleem, daar  ∣ . ˇ Een periodieke rij van natuurlijke getallen met deze sommatie-eigenschap wordt een Sindelrij genoemd. Dit is geen triviale eigenschap: de gelijkaardige rij met periode , , , , , , ,  of periode , , ,  voldoet bijvoorbeeld niet. De som van alle termen in de minimale periode ˇ heet de modulus van de Sindelrij, en is gelijk aan  voor de originele Praagse klok. ˇ Vanuit de definitie is het slechts een eenvoudige observatie dat een periodieke rij deze Sindeleigenschap heeft als en slechts als elk driehoeksgetal optreedt als een partieelsom van de rij. In [] bewijzen de auteurs een veel praktischer criterium, waarbij het volstaat om slechts een eindig aantal driehoeksgetallen te controleren.



Stelling. Beschouw een periodieke rij met modulus s. ˇ • Als s = t +  oneven is, dan is dit een Sindelrij als en slechts als de eerste t driehoeksgetallen optreden als partieelsommen. ˇ • Als s = t even is, dan is dit een Sindelrij als en slechts als de eerste t −  driehoeksgetallen optreden als partieelsommen. Zonder bewijs. Zie [].

∎ Ò

In beide gevallen zijn de grenzen scherp. De rij met periode , , , , , ,  (modulus s = ) ˇ bijvoorbeeld is geen Sindelrij, maar die bereikt wel de eerste zes driehoeksgetallen. De rij met periode , ,  (modulus s = ) vormt een voorbeeld met even modulus. ˇ Gegeven een Sindelrij is er een nogal saaie manier om een nieuwe op te stellen door gewoon termen periodiek te ontbinden als sommen van kleinere termen. Zo kan men uit de Praagseklokrij met periode , , , , ,  meteen ook die met periode , , , , , , , ,  afleiden. We ˇ noemen een Sindelrij primitief als die niet op een dergelijke manier gevonden kan worden ˇ uit een kortere, dus als termen samennemen de Sindeleigenschap schendt. Zo is de originele rij met modulus  bijvoorbeeld primitief; vanuit praktisch uurwerkkundig standpunt is een primitieve rij uiteraard het interessantst, aangezien deze het grootste effect heeft op de nauwkeurigheid van de klok. ˇ Een kleine subtiliteit is dat de modulus van primitieve Sindelrijen strikt kleiner kan zijn dan van de afgeleide rijen. Zo is de rij met periode , , , ,  (modulus ) imprimitief, want deze kan worden afgeleid van de rij met periode ,  (modulus ). ˇ Stelling. Voor ieder oneven getal s bestaat er een unieke primitieve Sindelrij met modulus s, ˇ terwijl een Sindelrij met even modulus nooit primitief is. Zonder bewijs. Zie [] voor het volledige bewijs.

∎ Ò

ˇ De volgende bladzijde geeft een tabel met de eerste  primitieve Sindelrijen.

[1] Praˇzsk´y Orloj, http://www.orloj.eu. [2] C. Bae, J. Conway, L. Kohlhase, S. Park, Prague clocks? Mathematical Intelligencer, vol. 38, no. 1, 2016, p. 37–39. ˇ ˇ [3] M. Kˇr´ızˇek, A. Solcov´ a, L. Somer, Construction of Sindel sequences. Commentationes Mathematicae Universitatis Carolinae, vol. 48, no. 3, 2007, p. 373–388. ˇ [4] M. Kˇr´ızˇek, A. Solcov´ a, L. Somer, Deset matematick´ych vˇet o praˇzsk´em orloji. Pokroky Matematiky, Fyziky a Astronomie, vol. 54, no. 4, 2009, p. 281–300.



                                       



 ,  , ,  , , ,  , , ,  , , , , ,  , , , , , ,  , , , , ,  , , , , , , , ,  , , , , , , , , ,  , , , , , , ,  , , , , , , , , , , ,  , , , , , , , , , ,  , , , , , , , , , ,  , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , ,  , , , , , , , , , , ,  , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , ,  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 

9

Veelhoeksgetallen

De studie van veelhoeksgetallen gaat historisch terug tot op Pythagoras (en wellicht vroeger) maar dit soort getallen zijn doorheen de geschiedenis talloze wiskundigen blijven fascineren. Zoals de naam suggereert gaat het om figuratieve getallen gebaseerd op veelhoeken. De bekendste familie zijn ongetwijfeld de driehoeksgetallen ([]), , , , , , , , , , , , , , , , , , , , , . . . gebaseerd op het patroon

... Concreet worden de driehoeksgetallen P3 (k) gedefinieerd als P3 (n) =  +  +  + ⋯ + k = 21 k(k + ). Deze laatste uitdrukking wordt meestal aangeduid als de somformule van Gauss, refererend naar een anekdotisch voorval uit de jeugd van de geniale wiskundige Carl Friedrich Gauss. Volgens het verhaal gaf leerkracht B¨uttner de lagereschoolkinderen in zijn klas de opdracht om de som  +  +  + ⋯ +  uit te rekenen. Terwijl de overige leerlingen braaf de getallen e´e´n per e´e´n begonnen optellen, schreef de zevenjarige Gauss meteen het correcte antwoord— — op zijn schrijfbordje. Door de termen slim te groeperen had hij door dat de totaalsom eigenlijk gewoon vijftig keer  was: ( + ) + ( + ) + ( + ) + ⋯ + ( + ) + ( + ). Figuratief passen twee driehoeken precies naast elkaar in een makkelijker te tellen rechthoek, waaruit meteen af te lezen valt dat inderdaad  P3 (k) = k(k + ).

Over de authenticiteit van de anekdote valt veel te discussi¨eren. Brian Hayes vergelijkt in [] een heel aantal varianten van het verhaal; de oudste bron is het gedenkschrift [] van Gauss’ goede vriend Wolfgang Sartorius. Hoe dan ook staat het buiten kijf dat de formule al minstens een millennium eerder gekend was—vermoedelijk al door de oude Grieken.



Naast de driehoeksgetallen is er ook de familie van de vierhoeksgetallen, die in feite gewoon neerkomen op de volkomen kwadraten ([]), , , , , , , , , , , , , , , , , , , , , . . . gebaseerd op het patroon

... Voor de vierhoeksgetallen P4 (k) is dus eenvoudigweg P4 (k) = k 2 . Ook hier kunnen figuratieve voorstellen tot visuele bewijzen voor allerlei identiteiten leiden (die uiteraard ook algebra¨ısch te bewijzen zijn). Zo is de som van twee opeenvolgende driehoeksgetallen altijd een volkomen kwadraat: P3 (k − ) + P3 (k) = 21 (k − )k + 21 k(k + ) = k 2 = P4 (k).

Nog een interessant verband tussen driehoeksgetallen en kwadraten: een natuurlijk getal n is een driehoeksgetal als en slechts als n +  een (noodzakelijk oneven) volkomen kwadraat is. Dit volgt algebra¨ısch omdat n = 21 k(k + ) als en slechts als n +  = (k + )2 maar er bestaat ook een mooie meetkundige interpretatie.

Na de kwadraten komen de vijfhoeksgetallen ([]), , , , , , , , , , , , , , , , , , , , , . . . gebaseerd op het patroon

...



Op dezelfde manier zijn de zeshoeksgetallen ([]) , , , , , , , , , , , , , , , , , , , . . . gebaseerd op het patroon

... Geheel analoog kan men zevenhoeksgetallen, achthoeksgetallen. . . opstellen. Een expliciete algemene formule voor de n-hoeksgetallen Pn (k) met n ⩾  kan men bijvoorbeeld als volgt afleiden. Voor elke n is alvast Pn () = ; de volgende getallen krijg je door een aantal “ringen” rond dat eerste punt toe te voegen, waarbij de k-de ring een bijdrage van  + (n − ) ⋅ k levert. Voor het getal Pn (k) zijn er k −  zo’n ringen, zodat in totaal k−1

Pn (k) = ∑ ( + (n − ) ⋅ i) = k + (n − ) ⋅ 21 (k − )k, i=0

of met andere woorden, Pn (k) = k + (n − ) ⋅ P3 (k − ) = P3 (k) + (n − ) ⋅ P3 (k − ). Ook hier blijven de driehoeksgetallen opduiken! Opnieuw bestaat er een mooie meetkundige interpretatie van deze telling, hieronder ge¨ıllustreerd voor (n, k) = (, ).

Deze laatste figuur suggereert na wat herpuzzelen en vervormen ook een andere eigenschap: elk zeshoeksgetal is ook een driehoeksgetal!

Inderdaad, P6 (k) = P3 (k) +  ⋅ P3 (k − ) = 21 k(k + ) +  ⋅ 21 (k − )k = 21 (k − )k = P3 (k − ).



Pierre de Fermat beweerde in  dat elk natuurlijk getal de som is van hoogstens drie driehoeksgetallen, en hoogstens vier kwadraten, en hoogstens vijf vijfhoeksgetallen, enzoverder. Fermat zou Fermat niet zijn als hij zijn claim ook had bewezen. Pas in  kon Joseph Louis Lagrange de vierkwadratenstelling bewijzen—het geval n =  van de bewering van Fermat. Het was Gauss die in  het geval n =  kraakte. Ter gelegenheid hiervan schreef hij in zijn dagboek de ietwat cryptische regel

(EYPHKA: num = △+△+△); daarom staat dit resultaat ook wel gekend als de Eurekastelling. Het eerste volledige bewijs (voor arbitraire n) was van de hand van Augustin-Louis Cauchy, in . In  publiceerde Melvyn Nathanson een elementair (maar nog steeds technisch) bewijs in [].

[1] B. Hayes, Gauss’s day of reckoning. American Scientist, vol. 94, no. 3, 2006, p. 200–205. [2] M. Nathanson, A short proof of Cauchy’s polygonal number theorem. Proceedings of the American Mathematical Society, vol. 99, no. 1, 1987, p. 22–24. [3] W. Sartorius von Waltershausen, Gauss: zum ged¨achtniss. Hirzel, 1856. [4] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A000217. [5] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A000290. [6] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A000326. [7] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A000384.



10

Kerstmisstelling van Fermat

Welke getallen zijn te schrijven als een som van twee kwadraatgetallen? Albert Girard doorzag in  als eerste een patroon, en beweerde dat het precies de volgende getallen waren. Determinaison d’un nombre qui se peut diviser en deux quarrez entiers. (I) Tout nombre quarr´e. (II) Tout nombre premier qui excede un nombre quaternaire de l’unit´e. (III) Le produict de ceux qui sont tels. (IV) Et le double de chacun d’iceux. Pierre de Fermat kondigde een gelijkaardig resultaat aan in een brief naar Marin Mersenne, gedateerd  december ; vanwege deze datum wordt het resultaat wel eens de kerstmisstelling genoemd. Het hoeft niet te verbazen dat Fermat geen toelichting gaf bij deze claim. Hij beperkte zich daarenboven tot priemgetallen, maar beweerde wel dat de schrijfwijze als een som van twee kwadraten in dit geval uniek is. Fermat schreef: Sur le sujet des triangles rectangles, voici mes fondements. Tout nombre premier qui surpasse de l’unit´e un multiple du quaternaire, est une seule fois la somme de deux quarr´es, et une seule fois l’hypot´enuse d’un triangle rectangle. Het eerste bewijs werd gevonden door Leonhard Euler en gebruikt een moeizame toepassing van het principe der oneindige afdaling—nota bene het favoriete bewijsprincipe van Fermat. Joseph Lagrange gaf een bewijs via kwadratische vormen dat later werd vereenvoudigd door Carl Friedrich Gauss. Doorheen de geschiedenis werden nog veel meer bewijzen gevonden, steunend op een verscheidenheid aan wiskundige ingredi¨enten. In  leverde Don Zagier een befaamd combinatorisch bewijs in e´e´n zin ([])! De kerstmisstelling zegt concreet het volgende. Stelling. Een oneven priemgetal p is te schrijven als een som van twee volkomen kwadraten als en slechts als p ≡  (mod ). Deze representatie is bovendien uniek (op volgorde na). Bewijs. Merk op dat (k)2 ≡  (mod ) en dat (k + )2 ≡  (mod ) voor elk geheel getal k, zodat een priemgetal p ≡  (mod ) nooit een som van twee kwadraatgetallen kan zijn. Beschouw een priemgetal p ≡  (mod ). Men kan op een aantal (rekenintensieve) manieren bewijzen dat er hoogstens e´e´n manier is om p te schrijven als een som van twee kwadraten. We geven nu twee verschillende argumenten die aantonen dat er steeds minstens e´e´n manier bestaat: een bewijs via het duivenhokprincipe en het elegante bewijs van Zagier. • Schrijf p = k + , definieer x = (k)! en reken na dat, modulo p, x 2 = (k)! ⋅ (−) ⋅ (−) ⋯ (−k) ≡ (k)! ⋅ (p − ) ⋅ (p − ) ⋯ (p − k) ≡ (p − )! ≡ −.



√ Beschouw de getallen van de vorm ax − b met  ⩽ a, b < p. Het aantal koppels (a, b) √ is (⌊ p⌋ + )2 > p, zodat er wegens het duivenhokprincipe twee verschillende koppels (a1 , b1 ) en (a2 , b2 ) bestaan met a1 x − b1 ≡ a2 x − b2 (mod p). Herschrijven leert dat (b1 − b2 )2 ≡ x 2 ⋅ (a1 − a2 )2 ≡ −(a1 − a2 )2 (mod p), of met andere woorden, (a1 − a2 )2 + (b1 − b2 )2 blijkt een veelvoud van p. Maar √ √  < (a1 − a2 )2 + (b1 − b2 )2 < ( p)2 + ( p)2 = p, zodat deze som van twee kwadraten wel gelijk moet zijn aan p zelf. • Beschouw de verzameling S p = {(x, y, z) ∈ N3 ∣ p = x 2 +yz}. Deze is uiteraard eindig. Men kan narekenen dat de afbeelding ⎧ (x + z, z, y − x − z) ⎪ ⎪ ⎪ ⎪ (x, y, z) ↦ ⎨(y − x, y, x − y + z) ⎪ ⎪ ⎪ ⎪ ⎩(x − y, x − y + z, y)

als x < y − z, als y − z < x < y, als x > y

een involutie op S p is met precies e´e´n fixpunt (, , k), dus S p bevat een oneven aantal elementen. Dan moet ook de involutie (x, y, z) ↦ (x, z, y) op S p een fixpunt hebben, noodzakelijk van de vorm (a, b, b), en dan is p = a2 + (b)2 . ∎

Een bewijs van uniciteit laten we achterwege.

Er bestaat een meetkundige visualisatie van de involutie van Zagier die helpt verklaren wat er achter de schermen speelt. Elk drietal (x, y, z) in de verzameling S p kan worden voorgesteld door middel van een vierkant met zijdelengte x en vier rechthoeken met zijdelengtes y en z, hieronder ge¨ıllustreerd voor p = . Zo’n constructie heeft oppervlakte x 2 + yz = p.

(, , )

←→

(, , )

(, , )

←→

(, , )

Uitsluitend kijkend naar de vorm van het geheel, bestaan er twee manieren om het originele vierkant met vier rechthoeken te reconstrueren; de involutie van Zagier wisselt deze net om. Op dezelfde manier kunnen we visualiseren dat (, , ) ←→ (, , ), (, , ) ←→ (, , ) en (, , ) ←→ (, , ). Er bestaat echter e´e´n configuratie waarbij deze reconstructie w´el uniek is: een kruisvormige figuur zoals hieronder, waarbij x = y. Aangezien de totale oppervlakte priem is, betekent dat dat x = y = . Deze configuratie komt precies overeen met het fixpunt (, , k).



(, , ) De stap van priemgetallen naar algemenere natuurlijke getallen (waarop de claim van Girard betrekking heeft) blijkt niet zo groot. Er bestaat namelijk een handige algebra¨ısche identiteit die toelaat een product van twee sommen van twee kwadraten te herschrijven naar een enkele som van twee kwadraten, op twee verschillende manieren zelfs. De formule staat bekend als de identiteit van Brahmagupta–Fibonacci, maar gaat eigenlijk terug tot Diophantus: (a2 + b 2 ) ⋅ (c 2 + d 2 ) = (ac − bd)2 + (ad + bc)2 = (ac + bd)2 + (ad − bc)2 . Samen met de kerstmisstelling voor priemgetallen leidt dit tot het volgende resultaat. Stelling. Een natuurlijk getal n is te schrijven als een som van twee volkomen kwadraten als en slechts als elke priemfactor congruent met  (mod ) optreedt met een even exponent. Merk op dat de stelling hierboven nog niet meteen informatie geeft over het aantal manieren om n te schrijven als een som van twee kwadraten. Als we nu w´el onderscheid maken tussen sommen met dezelfde termen maar in verschillende volgorde, dan kan men dit aantal heel elegant omschrijven als het totale aantal delers van n congruent met  (mod ) verminderd met het aantal delers van n congruent met  (mod ). Als we ook kwadraten van negatieve gehele getallen toelaten, dan wordt dit aantal nog eens vier keer groter. Noteer dit aantal manieren kortweg als r2 (n), dus expliciet, r2 (n) = ∣{(x, y) ∈ Z2 ∣ n = x 2 + y 2 }∣. Elk roosterpunt (x, y) in Z2 draagt e´e´n bij tot r2 (n) voor zekere n. De mogelijke manieren om de natuurlijke getallen tot en met n te schrijven als een som van twee gehele√kwadraten, komen dan precies overeen met de roosterpunten binnen een schijf met straal n rondom de oorsprong. Dit aantal roosterpunten is ongeveer gelijk aan de oppervlakte van de schijf, π ⋅ n. Men kan dit rigoureus maken en besluiten dat n

∑ r2 (i) ∼ π ⋅ n, i=0



zodat de “gemiddelde waarde” van r2 (n) voldoet aan  n ∑ r2 (i) = π. n→∞ n i=0 lim

Het afschatten van de foutterm in de eerste formule is de inhoud van het zogenaamde cirkel√ probleem van Gauss, die zelf kon aantonen dat de fout begrensd wordt door π n. Definieer ten slotte s(n) als het aantal natuurlijke getallen, niet groter dan n, die te schrijven zijn als de som van twee volkomen kwadraten (ongeacht het aantal schrijfwijzen). Edmund Landau ontdekte dat ook deze functie een opmerkelijke groei vertoont ([]), namelijk λ⋅n s(n) ∼ √ ln n met λ de zogenaamde constante van Landau–Ramanujan. Dit getal blijkt gelijk aan √ p2 −  p  π λ= √ ∏ √ = ≈ . . . . ∏ p  p≡3 p2 −   p ≡ 1 (mod 4)

(mod 4)

(waarbij beide producten lopen over priemgetallen p).

[1] M. Aigner, G. Ziegler, Proofs from the Book. Springer-Verlag, ed. 6, 2018. [2] L. Euler, Demonstratio theorematis Fermatiani omnem numerum primumformae 4n + 1 esse summam duorum quadratorum. Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, vol. 5, 1760, p. 3–13. [3] S. Finch, Mathematical constants. Oxford University Press, 2003. ¨ [4] E. Landau, Uber die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindeszahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate. Archiv der Mathematik und Physik (3), vol. 13, 1908, p. 305–312. [5] D. Zagier, A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares. American Mathematical Monthly, vol. 97, no. 2, 1990, p. 144.



10

(todo)

10.1 Vierkwadratenstelling van Lagrange & 15-stelling van Conway

10.16 Mersennepriemgetallen 10.17 Kanonskogelpuzzel

10.2 p-adische getallen 10.18 Harmonische getallen 10.3 Boom van Calkin–Wilf 10.19 Bevriende en sociale getallen 10.4 Boom van Stern–Brocot 10.20 Priemgetalstelling 10.5 Kettingbreuken 10.21 Inversieformule van M¨obius 10.6 Vermoeden van Gilbreath 10.22 Stelling van Midy 10.7 Fibonaccitest van Gessel 10.8 Machtige getallen 10.9 Lifting the exponent 10.10 Vermoeden van Collatz 10.11 Pythagorasdrietallen

10.23 Vermoeden van Catalan 10.24 Vermoeden van Goldbach 10.25 Priemgetalhiaten 10.26 abc-vermoeden

10.12 Fareysequenties

10.27 Kwadratische reciprociteit

10.13 Stelling van Hurwitz

10.28 Vermoeden van Collatz

10.14 Irrationale getallen

10.29 Tweelingpriemgetallen

10.15 Stelling van Euclides

10.30 Aritmetische afgeleiden



Combinatoriek

11

Magische zeshoeken

Net zoals de vertrouwdere magische vierkanten wordt een magische zeshoek opgebouwd uit kleine genummerde zeshoekjes die samenpassen in e´e´n grote zeshoek zoals hieronder, zodat de labels in iedere richting sommeren tot eenzelfde getal. De orde van een magische zeshoek is het aantal cellen langs elke zijde, en een visueel argument leert dat een zeshoek van orde n uit precies n(n − ) +  = n2 − n +  cellen bestaat.

Magische vierkanten zijn best wel talrijk: voor iedere orde n bestaan er exemplaren die juist de getallen {, , . . . , n2 } bevatten. Voor magische zeshoeken is de situatie helemaal anders! Stelling. Een magische zeshoek van orde n die juist de getallen {, , . . . , n2 − n + } bevat, kan enkel bestaan wanneer n =  of n = .

Bewijs. De som van alle getallen in zo’n zeshoek is wegens de formule van Gauss gelijk aan  S = (n2 − n + )(n2 − n + ).  In ieder van de drie richtingen moeten de n −  rijen sommeren tot eenzelfde constante m. Dat betekent na wat rekenwerk dat m=

S      = n3 − n2 + n − + , n −      (n − )

of na wat herschrijven dat (n − ) ⋅ (m − n3 + n2 − n + ) = . Gezien beide factoren gehele getallen zijn, blijkt n −  een deler van vijf. Maar in dat geval zijn er slechts twee mogelijkheden: ofwel is n −  = , ofwel n −  = . De stelling volgt. ∎



Voor n =  is een magische zeshoek niet bepaald spectaculair. 

Het geval n =  blijkt uitdagender. Rond  las de toen -jarige Clifford Adams een puzzel in een lokale krant, die vroeg om de getallen {, , . . . , } z´o in een zeshoek te schikken dat de som in iedere lijn gelijk is aan . Adams begreep algauw waarom de krant geen oplossing publiceerde: de telling in bovenstaand bewijs leert immers dat deze magische som voor n =  gelijk moet zijn aan . . . Ondanks dit numerieke inzicht en ondanks vele jaren puzzelwerk lukte het Adams maar niet om de magische zeshoek volledig correct in te vullen. Pas in , tijdens een revalidatie van een operatie, vond Adams eindelijk een oplossing! Helaas ging zijn ontdekking eerst verloren en duurde het nog eens vijf jaar vooraleer hij die kon reconstrueren.   

 

 

 



 

 





 



Adams stuurde zijn vondst naar Martin Gardner, die daar een Mathematical Games-column aan wijdde ([]). Zo raakten behalve het grote publiek ook enkele wiskundigen gefascineerd door de magische zeshoek: Charles Trigg publiceerde bijvoorbeeld een grondige analyse en geschiedenis ([]), en computerzoektochten van William Daly toonden aan dat de oplossing essentieel uniek is, op rotaties en spiegelingen na. Adams was zeker niet de eerste of enige die de magische zeshoek ontdekte; de oudst gekende referentie dateert van  door Ernst von Haselberg ([], []). Als we de eis laten vallen dat de zeshoekjes precies de getallen {, , . . . , n2 − n + } moeten bevatten, dan zijn er terug grotere interessante voorbeelden te vinden. Arsen Zahray ontdekte een zeshoek van orde  met de opeenvolgende getallen {, , . . . , } en magische som . 

  

 



 



 

 







 





 





 



 









 





Zahray vond ook een zeshoek van orde  met de getallen {, , . . . , }. 

   







 

 

  







 



 

 

 









 













 









 

 













 



 



In  vond Zahray een magische zeshoek van orde  met de getallen {, , . . . , }, gebruik makend van geavanceerde heuristieke optimalisatiealgoritmes zoals simulated annealing. 



  



  





 







 

 

  

 

 

 

 

    





  











 



   



 

  





 





























 

























 



 











 

 













 



  

 



  





 



Een indrukwekkend exemplaar met orde  werd gevonden door Louis Hoelbling in , en bevat alle gehele getallen {−, −, . . . , } die in elke richting precies tot nul sommeren. − − −

 − 



− −  −   −  −   −  − 







 − − 



−  − 

−  − − −  − − − 

 

 − − 



 

− −

 −  −  − − − 



 − −



 −  − 



− − −  − − 



 −

 − 

 −  − −  −

 − −

 − − −

−









− −  − −



− − −  −   − 

 − 





 −  − 

− 



 − −  − −



−

 − −  −  − −  − − − 

−





 −

 −  −  − − 

[1] H. Bauch, Zum magischen Sechseck von Ernst v. Haselberg. Wissenschaft und Fortschritt, vol. 40, no. 9, 1990, p. 240–242. [2] M. Gardner, Mathematical games: permutations and paradoxes in combinatorial mathematics. Scientific American, vol. 209, no. 6, 1963, p. 112–119. [3] C. Trigg, A unique magic hexagon. Recreational Mathematics Magazine, vol. 14, 1964, p. 40–43. [4] E. von Haselberg, Section . Zeitschrift f¨ur mathematischen und naturwissenschaftlichen Unterricht, vol. 19, 1888, p. 429. [5] E. von Haselberg, Section . Zeitschrift f¨ur mathematischen und naturwissenschaftlichen Unterricht, vol. 20, 1889, p. 263–264.



12

Formule van Cayley

Naar Arthur Cayley wordt een uitzonderlijk elegante formule in de combinatoriek genoemd, al werd het resultaat zo’n  jaar eerder al voorzien door Carl Borchardt en James Sylvester; Cayley was diegene die het probleem in modernere grafentheoretische termen verwoordde. Het telprobleem in kwestie vraagt hoeveel gelabelde bomen er bestaan met n toppen, waarbij de toppen dus onderling onderscheidbaar zijn. Op drie toppen bijvoorbeeld zijn er drie.

Op vier toppen zijn er meer mogelijkheden—de volgende zestien.

Op vijf toppen bestaan er  bomen, en voor algemene n geldt de volgende formule. Stelling (Cayley). Het aantal (gelabelde) bomen op n toppen is precies n n−2 . Bewijs. In dit bewijs kijken we algemener naar wouden: grafen waarin elke samenhangenscomponent een boom is. Concreet zijn deze wouden ook gelabeld (dus toppen zijn onderling onderscheidbaar) en geworteld (dus iedere component heeft een bijzondere top, de wortel). We schrijven W(n, k) voor de verzameling van gelabelde, gewortelde wouden met n toppen en k componenten. Merk alvast op dat W(n, n) slechts een enkel woud zonder bogen bevat, en dat we uiteraard op zoek zijn naar de kardinaliteit van W(n, ). De formule van Cayley zal volgen uit een dubbele telling voor het aantal gelabelde gewortelde wouden met n toppen, k componenten, en e´e´n gemarkeerde top die geen wortel is. Enerzijds is dit aantal gelijk aan ∣W(n, k)∣ ⋅ (n − k). Kies immers eerst een woud uit W(n, k), met n toppen en k componenten, en markeer daarna een van de n − k niet-worteltoppen. Anderzijds kunnen we ook starten vanuit een woud uit W(n, k + ) met k +  componenten. Kies een top v (uit de n opties) en een component T die deze top niet bevat (uit de k opties). Hang de gekozen component aan de gekozen top en markeer de top die de wortel van T was. Het resultaat is een woud uit W(n, k) met e´e´n gemarkeerde top, en daarnaast is het duidelijk dat elk zo’n woud op unieke manier kan worden verkregen uit dit proces.



T ⇒

v

De dubbele telling leert dus dat (n − k) ⋅ ∣W(n, k)∣ = kn ⋅ ∣W(n, k + )∣, zodat na recursief toepassen volgt dat ∣W(n, )∣ =

  ⋅  ⋯ (n − ) ⋅ n ⋅ ∣W(n, )∣ = ⋯ = ⋅ n n−1 ⋅ ∣W(n, n)∣ = n n−1 . n− (n − ) ⋅ (n − ) ⋯ 

De formule van Cayley volgt nu door op te merken dat het aantal gewortelde gelabelde bomen op n toppen gelijk is aan n keer het aantal ongewortelde bomen, want elk van de n toppen kan dienen als wortel. Er zijn dus inderdaad precies n n−2 ongewortelde bomen op n toppen. ∎ Het bovenstaande bewijs—van de hand van Arnon Avron en Nachum Dershowitz ([])— leert iets algemener dat n− ∣W(n, k)∣ = ( ) ⋅ n n−k . k− Voor de formule van Cayley zijn er meerdere elegante bewijzen gekend. Het volgende maakt gebruik van Pr¨ufercodes, zoals eerst gebruikt door Heinz Pr¨ufer ([]). Bewijs. We zullen elke gelabelde boom op n toppen identificeren met een sequentie getallen in {, , . . . , n} van lengte n − . Aangezien er uiteraard precies n n−2 zo’n sequenties bestaan, volgt de formule. Onderstel dat de labels van de boom net de getallen , , . . . , n zijn. In de ene richting, gegeven zo’n boom op n toppen, zoeken we iteratief het blad van de boom met het kleinste label. Daarna verwijderen we dit blad en voegen het label van diens buur toe aan de code. Herhaal dit met de resterende boom tot er nog twee toppen overblijven. 1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

4

3

4

3

4

3

4

3

4

3

4

3

4

3

4

3

(, )

(, )

(, )

(, )

(, )

(, )

(, )

(, )

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

4

3

4

3

4

3

4

3

4

3

4

3

4

3

4

3

(, )



(, )

(, )

(, )

(, )

(, )

(, )

(, )

In de andere richting, gegeven zo’n code van lengte n − , starten we met een lege graaf op de toppen met labels , , . . . , n. Bepaal iteratief ℓ1 als het kleinste nog ongebruikte label dat niet voorkomt in de code en ℓ2 als het eerste getal in de code. Voeg een boog toe tussen de toppen met labels ℓ1 en ℓ2 , markeer ℓ1 als gebruikt in de graaf en schrap ℓ2 uit de code. Herhaal dit tot de code leeg is, en voeg een boog toe tussen de twee toppen met nog ongebruikte labels. Met wat meer werk kan men aantonen dat dit tweede algoritme steeds een boom produceert, waarvan de Pr¨ufercode precies de oorspronkelijke inputsequentie is. Met andere woorden, deze twee constructies bepalen bijecties tussen de gelabelde bomen op n toppen en de sequenties uit {, , . . . , n} met lengte n − . ∎ Dit bewijs geeft ook een handige en effici¨ente manier om uniform random gelabelde bomen te genereren, vanuit uniform random gekozen Pr¨ufersequenties. Nog een geheel ander bewijs maakt gebruik van een straffe veralgemening, de matrix-boomstelling van Kirchhoff. De natuurkundige Gustav Kirchhoff beschreef dit resultaat impliciet doorheen een analyse van elektrische netwerken. Deze stelling geeft een verrassend verband tussen enerzijds het aantal opspannende bomen van een graaf G, deelgrafen met de vorm van een boom die alle toppen van G bevatten, en anderzijds de Laplaciaan L(G) van G, de matrix met rijen en kolommen ge¨ındexeerd door de toppen en met elementen als volgt gedefinieerd: ⎧ ⎪ ⎪deg(i) L(G)i j = ⎨ ⎪ ⎪ ⎩−(aantal bogen tussen i en j)

als i = j, als i ≠ j.

Merk op dat de Laplaciaan steeds symmetrisch is en de som van iedere rij en kolom gelijk is aan nul. Daaruit kan men afleiden dat alle cofactoren van L(G) identiek zijn. De stelling van Kirchhoff stelt nu dat deze cofactoren precies zijn aan het aantal opspannende bomen van G. Dit aantal kan ook concreet worden uitgedrukt als  ⋅ λ ⋅ λ ⋯ λ n−1 n 1 2 met de λ’s de eigenwaarden van L(G) verschillend van nul. De gelabelde bomen op n toppen zijn net de opspannende bomen van de complete graaf K n , dus hun aantal is met de stelling van Kirchhoff snel uitgerekend als een cofactor van ⎛n −  − ⎜ − n −  L(K n ) = n ⋅ I n − J n = ⎜ ⎜ ⋮ ⋮ ⎝ − −

⋯ − ⎞ ⋯ − ⎟ ⎟. ⋱ ⋮ ⎟ ⋯ n − ⎠

Men kan alternatief nagaan dat deze matrix behalve de eigenwaarde  ook de eigenwaarde n heeft met multipliciteit n − .



[1] M. Aigner, G. Ziegler, Proofs from the Book. Springer-Verlag, ed. 6, 2018. [2] A. Avron, N. Dershowitz, Cayley’s formula: a page from the Book. American Mathematical Monthly, vol. 123, no. 7, 2016, p. 699–700. [3] A. Cayley, A theorem on trees. Quarterly Journal of Pure and Applied Mathematics, vol. 23, 1889, p. 376–378. [4] E. Kirby, R. Mallion, P. Pollak, P. Skrzyn´nski, What Kirchhoff actually did concerning spanning trees in electrical networks and its relationship to modern graph-theoretical work. Croatica Chemica Acta, vol. 89, no. 4, 2016, p. 403–417. ¨ [5] G. Kirchhoff, Uber die Aufl¨osung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung Galvanischer Str¨ome gef¨uhrt wird. Annalen der Physik und Chemie, vol. 72, 1847 p. 497–508. [6] H. Pr¨ufer, Neuer Beweis eines Satzes u¨ ber Permutationen. Archiv der Mathematik und Physik, vol. 27, no. 3, 1918, p. 142–144.



13

18-puntenprobleem

Start met een re¨eel getal  ⩽ x1 < . Zoek vervolgens een tweede getal x2 , zodat geldt dat x1 en x2 in verschillende helften van het eenheidsinterval liggen. Herhaal dit proces, waarbij elke volgende term x n zodanig gekozen wordt dat de getallen x1 , . . . , x n in verschillende n-de delen van het eenheidsinterval liggen, zodat dus voor elke k ∈ {, . . . , n} de ongelijkheid k k− ⩽ xi < n n opgaat voor een (en dus juist e´e´n) index i ∈ {, . . . , n}. Hoe lang kunnen we zo’n rij maken? Dit onschuldig klinkende probleem van Hugo Steinhaus is niet zo eenvoudig als het schijnt; de initi¨ele termen moeten zeer zorgvuldig gekozen worden of de opgave loopt al snel spaak. Een geldige rij met  termen is bijvoorbeeld                  , , , , , , , , , , , , , , , , .                 

Opmerkelijk genoeg lukt het niet beter dan dit: een rij met  termen kan nooit voldoen aan alle gevraagde ongelijkheden! Elwyn Berlekamp en Ronald Graham gaven daar in  als eersten een bewijs voor uit ([]), waarbij ze vermeldden dat het resultaat Mieczyslaw Warmus toebehoorde. Deze publiceerde later ook zijn eenvoudigere bewijs ([]). [1] E. Berlekamp, R. Graham, Irregularities in the distributions of finite sequences. Journal of Number Theory, vol. 2, no. 2, 1970, p. 152–161. [2] H. Steinhaus, One hundred problems in elementary mathematics. Basic Books, 1964, p. 12. [3] M. Warmus, A supplementary note on the irregularities of distributions. Journal of Number Theory, vol. 8, no. 3, 1976, p. 260–263.



14

Vermoeden van Erd˝os–Gy´arf´as

Het volgende probleem dat eenvoudig genoeg te formuleren valt maar nog steeds open staat, is een van de vele vermoedens van Paul Erd˝os, geformuleerd in  in samenwerking met Andr´as Gy´arf´as. Erd˝os loofde (zoals hij nog wel vaker deed) een geldelijke prijs uit van $ voor een bewijs, of $ voor een tegenvoorbeeld. Het vermoeden gaat over simpele cykels in grafen—cykels waarin geen enkele top meermaals optreedt. Vermoeden (Erd˝os–Gy´arf´as). Een graaf met minimumgraad drie bevat een (simpele) cykel met een macht van twee als lengte, k voor zekere k ⩾ . Computerzoektochten van Gorden Royle hebben uitgewezen dat een tegenvoorbeeld zeker  toppen moet hebben. Klas Markstr¨om kon alle grafen tot en met  toppen verifi¨eren ([]) maar beperkt tot kubische grafen, waarin elke top precies graad drie heeft. Markstr¨om vond bovendien vier grafen op  toppen zonder - of -cykels, waaronder de onderstaande graaf; er zijn echter wel -cykels te vinden.

Ondanks dit gebrek aan voor de hand liggende tegenvoorbeelden twijfelden Erd˝os en Gy´arf´as uiteindelijk zelf aan de geldigheid van hun vermoeden. Erd˝os schreef in [], About three years ago, Andr´as Gy´arf´as and I thought at first that if G is any graph every vertex of which has degree ⩾  then our G has a cycle of length k for some k. We are convinced now that this is false and no doubt there are graphs for every r every vertex of which has degree ⩾ r and which contains no cycle of length k , but we never found a counterexample even for r = . Voor bepaalde families is het vermoeden wel al bewezen, bijvoorbeeld voor de zogenaamde klauwloze (claw-free) grafen door Daniel Dale en Stephen Shauger ([]). Een graaf is klauwloos als die de onderstaande graaf, die een klauw wordt genoemd, niet bevat als ge¨ınduceerde deelgraaf, dus als geen enkele top drie onderling niet-adjacente buren heeft.



[1] D. Dale, S. Shauger, A result on the Erd˝os–Gy´arf´as conjecture in planar graphs. Proc. 32nd Southeastern Int. Conf. on combinatorics, graph theory and computing, 2001, p. 129–139. [2] P. Erd˝os, Some old and new problems in various branches of combinatorics. Discrete Mathematics, vol. 165, 1997, p. 227–231. [3] C. Heckman, R. Krakovski, Erd˝os–Gy´arf´as conjecture for cubic planar graphs. Electronic Journal of Combinatorics, vol. 20, no. 2, 2013, P7. [4] K. Markstr¨om, Extremal graphs for some problems on cycles in graphs. Congressus Numerantium, vol. 171, 2004, p. 179–192. [5] J. Verstraete, Unavoidable cycle lengths in graphs. Journal of Graph Theory, vol. 49, no. 2, 2005, p. 151–167.



15

Kruskals bomenstelling

Joseph Kruskal bewees een vrij technisch resultaat dat aanleiding geeft tot een functie TREE, die onvoorstelbaar snel groeit en gigantische waarden bereikt zelfs voor n = . De stelling gaat over zogenaamde wel-quasi-ordeningen, waarin per definitie geen oneindig lange strikt dalende ketens en geen oneindig lange antiketens (met onderling onvergelijkbare elementen) optreden. Een voorbeeld van zo’n wel-quasi-ordening is de vertrouwde ordening op de natuurlijke getallen. Op de gehele getallen echter is dit geen wel-quasi-ordening, want daar is  > − > − > − > − > ⋯ een voorbeeld van een oneindige strikt dalende keten. De natuurlijke getallen geordend op deelbaarheid voldoen evenmin: daar bestaan weliswaar geen oneindige dalende ketens, maar vormen de priemgetallen een oneindige antiketen. Zij (X, ) zo’n wel-quasi-ordening en beschouw een willekeurige rij x1 , x2 , x3 . . . met termen in X. Het ontbreken van oneindig lange dalende ketens of antiketens impliceert het bestaan van twee indices i < j waarvoor x i x j en ook omgekeerd, als in elke rij twee zo’n termen te vinden zijn, dan is X een wel-quasi-ordening. Uit een eindige set L van “labels” kunnen we een nieuwe verzameling T(L) defini¨eren, van alle gewortelde en gelabelde bomen met labels in L. Beschouw nu twee zo’n bomen T1 en T2 . We noemen T1 een minor van T2 als deze kan worden bekomen door enkele toppen en bogen van T2 te verwijderen of samen te trekken, en noteren dan T1 T2 . Onderstaande illustratie verduidelijkt het idee. Bemerk dat minoren ori¨entaties van bogen (bepaald door de wortel) moeten respecteren.     













≈





 

 

 

Stelling (Kruskal). T(L) is wel-quasi-geordend volgens minoren. Zonder bewijs. Zie [] voor Kruskals originele bewijs, of [] voor een vereenvoudiging.

∎ Ò

Het is niet moeilijk om aan te tonen dat deze ordening volgens minoren reflexief en transitief is, of dat er geen oneindige strikt dalende ketens zijn (daar een minor in totaal steeds minder toppen en bogen heeft). De moeilijkheid schuilt hem voornamelijk in het kunnen uitsluiten van oneindige antiketens.



De oorspronkelijke formulering van Kruskal is eigenlijk nog algemener. We kunnen voor L een willekeurige wel-quasi-geordende verzameling kiezen, en een gelabelde minor defini¨eren als een minor waarbij bovendien de labels kleiner dan of gelijk aan de overeenkomstige labels van de originele graaf zijn (volgens de orde op L). Dan blijkt ook T(L) wel-quasi-geordend volgens gelabelde minoren. Passen we dit nu toe voor L eindig met alle elementen onderling onvergelijkbaar, dan bekomen we precies de bovenstaande formulering. Dankzij de stelling van Kruskal kunnen we een soort van spel spelen. Neem een aantal labels, hier L = {, , . . . , n}, en bouw een lijst T1 , T2 , T3 , . . . op van gelabelde en gewortelde bomen die voldoen aan de volgende twee spelregels: • boom Tk in de lijst mag hoogstens k toppen hebben (voor elke k); • geen enkele boom mag een minor zijn van een boom verderop in de lijst. De stelling van Kruskal impliceert nu dat zo’n lijst nooit oneindig lang kan doorlopen, want dan zijn er twee bomen Ti Tj met i < j in te vinden—in strijd met onze tweede spelregel! Daarnaast betekent de eerste spelregel dat een reglementaire lijst niet arbitrair lang kan zijn. Met andere woorden, voor iedere n is er een langst mogelijke geldige lijst, en de lengte ervan (in functie van n) is per definitie precies TREE(n), ingevoerd door Harvey Friedman in []. Voor n =  kunnen we e´e´n boom met een enkele top tekenen, maar dan is het spel afgelopen, dus TREE() = . Voor n =  kunnen we niet beter dan onderstaande lijst met drie bomen, dus TREE() = . Al bij al nog zeer bescheiden functiewaarden.  

 

Voor n =  is er meer vrijheid, en een mogelijke lijst begint bijvoorbeeld als volgt: 









  





 













 







 

Hoe ver kunnen we zo gaan? Het antwoord luidt: on-voor-stel-baar ver! TREE() explodeert naar een waarde zo onnoemelijk groot dat andere populaire grote getallen, zoals het getal van Graham (zie curiosum ??), nietig lijken in vergelijking. Er bestaan zelfs geen praktische manieren om de grootteorde voor dit getal (laat staan de groei van TREE) te beschrijven. Er geldt bovendien een boeiende veralgemening van de stelling van Kruskal, van toepassing op algemenere ongerichte grafen, weliswaar zonder labels. Neil Robertson en Paul Seymour leverden in een reeks van  artikels, gepubliceerd tussen  en , over  bladzijden, het volgende huzarenstukje dat eenvoudig genoeg te formuleren valt.



⋯

Stelling (Robertson–Seymour). Grafen zijn wel-quasi-geordend onder minoren. Zonder bewijs. De eerste paper uit de reeks van  was [].

∎ Ò

Praktisch betekent dit dat iedere familie grafen die gesloten is onder minoren, bepaald wordt door een eindige set van “verboden” minoren. Dit is een belangrijk resultaat binnen de theoretische informatica, want er zijn algoritmes bekend die herkennen of een graaf een bepaalde graaf als minor heeft in kwadratische tijd. Samen met de stelling van Robertson en Seymour is het dus in principe mogelijk om een heel aantal klassen van grafen effici¨ent te herkennen, al is het bewijs niet-constructief en liggen de verboden minoren niet altijd voor de hand. • De klasse van alle cykelvrije grafen (zonder lussen of dubbele bogen) is gesloten onder minoren. Er is een enkele verboden minor, nameljk de driehoeksgraaf K3 .

• De grafen waarbij iedere twee verschillende cykels hoogstens e´e´n top gemeen hebben, zijn gesloten onder minoren. Zo’n graaf wordt een cactusgraaf genoemd als die samenhangend is. Er is opnieuw een enkele verboden minor, namelijk de diamantgraaf links. Als we ook de vlindergraaf rechts als verboden minor opnemen, bekomen we de klasse van pseudowouden, waarbij elke samenhangscomponent hoogstens e´e´n cykel heeft.

• De klasse van planaire grafen is gesloten onder minoren. Er zijn twee verboden minoren, de complete bipartiete graaf K3,3 en de complete graaf K5 . Dat iedere niet-planaire graaf een van deze twee als minor heeft, heet de stelling van Wagner (niet te verwarren met de sterk gerelateerde stelling van Kuratowski).

[1] M. Fellows, The Robertson–Seymour theorems: a survey of applications. Contemporary Mathematics, vol. 89, 1987, p. 1–18. [2] H. Friedman, Internal finite tree embeddings. Reflections on the Foundations of Mathematics, Lecture Notes in Logic, vol. 15, 2002, p. 60–91. [3] J. Kruskal, Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture. Transactions of the American Mathematical Society, vol. 95, no. 2, 1960, p. 210–225. [4] C. Nash-Williams, On well-quasi-ordering finite trees. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 59, no. 4, 1963, p. 833–835. [5] N. Robertson, P. Seymour, Graph minors. I. Excluding a forest (etc.). Journal of Combinatorial Theory, series B, vol. 35, no. 1, 1983, p. 39–61.



16

Identiteit van Proizvolov

Vyacheslav Proizvolov stelde de volgende mooie eigenschap voor als opgave in de All-Union Soviet Student Olympiads van . Stelling (Proizvolov). Splits de getallen {, , . . . , n} op in twee even grote groepjes. Orden het ene groepje {a1 < a2 < ⋯ < a n } oplopend en het andere {b1 > b2 > ⋯ > b n } aflopend. Dan geldt steeds—onafhankelijk van de gekozen partitionering—dat ∣a1 − b1 ∣ + ∣a2 − b2 ∣ + ⋯ + ∣a n − b n ∣ = n2 . Bewijs. De meest elegante manier om dit aan te tonen steunt op de observatie dat er in ieder paar (a i , b i ) e´e´n getal behoort tot {, . . . , n} en e´e´n getal tot {n+, . . . , n}. Onderstel immers bij wijze van contradictie dat zowel a i ⩽ n als b i ⩽ n, voor zekere index i. Dan zijn de n +  verschillende getallen a1 , . . . , a i en b i , . . . , b n allen hoogstens n; een strijdigheid. Analoog leidt a i > n samen met b i > n tot een strijdigheid. Er volgt inderdaad dat ∣a1 − b1 ∣ + ∣a2 − b2 ∣ + ⋯ + ∣a n − b n ∣ = ((n + ) + (n + ) + ⋯ + n) − ( +  + ⋯ + n) = n2 . ∎ De volgende veralgemening werd opgemerkt door Gr´egoire Nicollier: start met willekeurige getallen {c1 < c2 < ⋯ < c2n } en splits deze op in twee groepjes zoals de originele setting van Proizvolov, dan is de som gelijk aan (c n+1 + ⋯ + c2n ) − (c1 + ⋯ + c n ) en dus in het bijzonder onafhankelijk van de gekozen opdeling. Voor de eerste n kwadraten bijvoorbeeld blijkt het resultaat steeds gelijk aan (n + )n2 . Ook hoeven de ongelijkheden niet strikt te zijn.

[1] S. Savchev, T. Andreescu, Mathematical miniatures. Mathematical Association of America, 2003, p. 66. [2] G. Nicollier, A generalisation of Proizvolov’s identity. The Mathematical Gazette, vol. 99, no. 546, 2015, p. 525–526.



17

Superpermutaties

Een superpermutatie (of een supermutatie) is een sequentie uit n symbolen die elk van de n! mogelijke permutaties als een deelsequentie bevat. Triviale superpermutaties van lengte n ⋅ n! verkrijg je door alle deze permutaties na elkaar te schrijven, maar omdat de vereiste deelsequenties mogen overlappen, is er veel verbetering mogelijk. In het geval n =  bijvoorbeeld zijn er twee permutaties, namelijk 12 en 21, en die komen beide voor in de sequentie 121. Als we met ℓ(n) de lengte bedoelen van de kortste correcte superpermutatie op n symbolen, dan zien we dus dat ℓ() = . Een minimale superpermutatie voor n =  is de sequentie 123121321, met ℓ() =  net half zo lang als de triviale bovengrens. Merk op dat niet elke deelsequentie van lengte n een geldige permutatie moet voorstellen (zoals hier het geval is met 121 centraal) of dat elke permutatie slechts e´e´n keer zou mogen optreden—we eisen niet meer dan dat elke permutatie ergens voorkomt. Voor n =  werkt 123412314231243121342132413214321, met ℓ() = , en een minimale superpermutatie voor n =  heeft al lengte : 123451234152341253412354123145231425314235142315423 124531243512431524312543121345213425134215342135421 324513241532413524132541321453214352143251432154321. Je kunt opmerken dat de waarden ℓ(n) voldoen aan een recursieve betrekking: het lijkt erop dat ℓ(n) = ℓ(n − ) + n!, waaruit expliciet ℓ(n) = ! + ! + ⋯ + n!. Een verklaring voor deze formule wordt gegeven door een algoritme, dat effici¨ent een superpermutatie kan opbouwen met e´e´n symbool extra uit een bestaande superpermutatie. Concreet, gegeven zo’n sequentie uit n −  symbolen, volstaat het om elk van de (n − )! optredende permutaties te vervangen door twee kopie¨en, gescheiden door het nieuwe symbool ertussenin. De superpermutatie voor n =  hierboven werd zo bekomen uit die voor n = . 123121321 123

231

312

213

132

321

1234123

2314231

3124312

2134213

1324132

3214321

123412314231243121342132413214321



Het is niet zo moeilijk te beredeneren dat in de nieuw geconstrueerde sequentie inderdaad elke mogelijke permutatie van de n symbolen zal optreden, en dat diens lengte precies met n! zal toenemen. Minder evident is dat de resulterende sequenties minimale superpermutaties zouden zijn, maar deze constructie bewijst alvast een bovengrens van ℓ(n) ⩽ ! + ! + ⋯ + n! voor algemene n. Anderzijds is het vrij evident dat een minimale superpermutatie minstens lengte n! + n −  moet hebben: er zijn n symbolen nodig voor de eerste permutatie, en dan minstens e´e´n voor elk van de overige n! −  permutaties. Dit argument kan worden verfijnd tot een ondergrens van ℓ(n) ⩾ n! + (n − )! + n − , en steunend op technischere redenen tot een nog betere ondergrens ℓ(n) ⩾ n! + (n − )! + (n − )! + n −  voor algemene n ⩾ . Het is verleidelijk om ervan uit te gaan dat het patroon zich verderzet en gelijkaardige verfijningen uiteindelijk wel zullen leiden tot de voorspelde waarde voor ℓ(n). Tot de grote verbazing van wiskundigen bleek echter het tegendeel waar. In  ondernam Robin Houston een computerzoektocht ([]) naar effici¨entere superpermutaties voor n = , en hij vond een legitieme met lengte , dus precies e´e´n symbool minder dan de voorspelde lengte ! + ! + ⋯ + ! = . Zijn ontdekking was de sequentie 1234561234516234512634512364513264513624513642513645213645123465123415623 4152634152364152346152341652341256341253641253461253416253412653412356412 3546123541623541263541236541326543126453162435162431562431652431625431624 5316425314625314265314256314253614253164523146523145623145263145236145231 6453216453126435126431526431256432156423154623154263154236154231654231564 2135642153624153621453621543621534621354621345621346521346251346215364215 6342165342163542163452163425163421564325164325614325641325643126543216543 2615342613542613452613425613426513426153246513246531246351246315246312546 3215463251463254163254613254631245632145632415632451632456132456312465321 4653241653246153264153261453261543265143625143652143562143526143521643521 4635214365124361524361254361245361243561243651423561423516423514623514263 514236514326541362541365241356241352641352461352416352413654213654123. Hiermee kan men middels het algoritme ook kortere superpermutaties opstellen voor n ⩾ . Wat de lengtes van de kortste geldige superpermutaties dan wel zijn, is nog steeds onbekend. Zelfs voor n =  is het niet geweten of het exemplaar van Houston optimaal is, al heeft hij ondertussen ook duizenden andere met dezelfde lengte gevonden. Voor n =  staat het record op lengte , ontdekt door Robin Houston en Greg Egan in , en te bewonderen op de volgende bladzijde. De records voor n =  en n =  zijn  en , respectievelijk. Deze effici¨ente superpermutaties werden gevonden via heuristieke algoritmen voor instanties van het handelsreizigersprobleem (zie curiosum ??). Beschouw immers de complete gerichte graaf met alle n! mogelijke permutaties als toppen en ken elke boog een gewicht toe dat gelijk is aan de mate van “overlap” tussen de eindtoppen. De superpermutaties komen dan precies overeen met wandelingen doorheen de graaf van maximaal gewicht die elke top bezoeken. Het handelsreizigersprobleem is zeker niet eenvoudig op te lossen (laat staan op n! toppen) maar met enkele technische simplificaties kunnen benaderingsalgoritmen wel aan de slag.



1234567123456172345612734561237456132745613724561374256137452613745621374561234756132475613427561 3472561347526134756213475612345761234516723451627345162374516234751623457162345176234512673451263 7451263475126345712634517263451276345123674512364751236457123645172364512736451237645123467512346 5712346517234651273465124376512436751243657124365172436512743651247365124637512463571246351724635 1274635124763512467351426735146273514672351467325146735216473521674352167345216374521634752163457 2163452716345217643521764532716453276145327641532764513267451326475132645713264517326451372645317 2645371264537216453726145372641537264513276453127645321764523176452137645217365421736524173652147 3652174365217346521736452176345216735421637542163574216354721635427163542176354216735241637524163 5724163527416352471635241763524167352146735124653712465317246531274653124765312467531426753146275 3146725314675231647532164753126475316247531642753164725316475231674532167453126745316274531672453 1674253167452316754231675243167523416752314675321467531246573124651372465132746513247651324671532 4671352467132546712354671253467125436715243671542367154326751432675413267543126754321675432617453 6217453612745361724536174253617452361745326174352617432561743265174236517426351742653174265137426 5173426157342617534216753421765342175634217536421753462175342617354261734526173425617342651743261 5743621574361257431625743126574132657412365741263574126537412657341265743125674132567412356741253 6741256374125673412567431257641325761432576134257613245761325476132574613257641235764125376142537 6124537612543761524376154237615432761543726154376215437612534761253746125376412573641257634125764 3125746312574361527436157243615742361574326175436217543612754361725436175243617542361754326715436 2715436721543671254637125467312547631254736152473615427361547236154732614573621457632147563214765 3214763521476325147632154763214576231457621345762143576214537621457361245736142573614527361457236 1457326147536214753612475361427536147253614752361475326147352614732561473265147236514726351472653 1472651347265143726514732615473621547361254731625473126547132654712365471263547126534712654371625 3471625374162537146253716425371624537162543716524371654237165432716543721654371265473125647132564 7123564712536471256347125643721564372516432756143275641327564312756432175643271564327516432571634 2517634251673425163742516347251634275163425716324517632451673245163724516327451632475163245716325 4716325741632571463275146327154632714563271465327146352714632571643527164357216435712643517264351 2764351267435126473512643751264357162435176243516724351627435162473516243751624357164235176423516 7423516472351642735164237514623751426375142367514237651427365142763514276531427651342765143276514 2375614235761423567143256714352671435627143567214356712435617243561274356124735612437561243576124 3567142356174235614723561427356142375164235716432517643251674325164732516437256143725641372564317 2564371256473125467132456713246571324675132461573246175324617352461732541672354176235471623547612 3547621354762315467231546273154623715462317564231576421356742135647213564271356421735624137562413 5762413567241356274135624713562417356214735621743562173456217354621735642137564213576421537462153 7426153742165374215637421536742153764215736421576342157643215764231567423156472315642731564237156 4231756243157624315672431562743156247315624371562431756234157623415672341562734156237415623471562 3417562314756231745623175463217456321746532174635217463251746321574632175463127546317254631752463 1572463152746315247631524673152463715246317542631574263154726315427631542673154263715426317546231 5746235174623571462357416235746123574621357462315476235147623541726354172365417235641723546172354 1672534176253147625317462531764253176245317625431765243176542317654321765431276543172654317625341 7265341725634172536417253461725341672543167254136725143672513467215347621534726153472165347215634 7215364721534672135467213456721346572136457213654721365742136572413657214365721346752136475213674 5213675421367524136752143765214375621437526143752164375214637251463721546372145637214653721463572 1463752143675213467251364725136742513672451367254163725416732541763254173625147362517436251734625 7136425713624571362547136257413625714362571346275136427513624751362745136275416327541623754126375 4123675412376541327654137265413762514376251347625137462513764251376245137625413765241376542137654 1237564123754613275461372546137524613754261375462137546123754162735412673541276354127365412735641 2735461273541627534126753412765341275634127536412753461275341627543162754136275143627513462715342 6713542671345267134256713426571432657142365714263571426537142657314265713426751342671534276153427 1653427156342715364271534627135462713456271346527136452713654271365247136527413652714365271346257 3146257341625734612573462157346251736425173624517362541732654173256417325461732456173246517324615 3724615327461532476153241675324165732146573216457312645731624573164257316452731654273165247316527 4316527341652731465273164572316547231657423165724316572341657231465723164573216547321657432165734 2165732416537241653274165324716532417653241567321456731245637124563172456312745631247563124576312 4567314256371425631742563147256314275631425763142567314526371452367145326714536271453672145367124 5367142536714523761452371645237146523741652374615234765123476521347652314765234176523471652347615 2346715234617523461572346152734615237465123746521374652317465237145623714526317452631475263145726 3145276314526731456273145672314567321546732156473215674321567342156732415637241563274156324715632 4175632415763241536724153627415362471536241753624157362415376241532674153264715326417532641573264 1523764152367415236471523641752364157236415273641526374152634715263417526341572634152763415267341 5264371526431752643157264315276431526743152647315264137526413572614357261345726135472613574261357 24613572641352761435276134527613542761352476135274613527641352674135264713526417352641.



Nog een amusante anekdote omtrent de vorderingen op dit probleem: er werd een serieuze bijdrage geleverd door een anonieme gebruiker op internetforum chan, nadat een animeliefhebber in  een vraag postte over de animereeks The Melancholy of Haruhi Suzumiya. De  afleveringen van het eerste seizoen omvatten tijdreizen en werden niet-chronologisch uitgezonden, een tweede uitzendschema en een latere dvd-uitgave hadden weer een andere volgorde, dus drong de vraag zich op hoe je het seizoen moet bingewatchen om uiteindelijk alle  afleveringen in elke mogelijke volgorde zo snel mogelijk gezien te hebben. Concreet komt dit neer op het vinden van de kortste superpermutatie voor n = . De exacte lengte werd niet gevonden, maar wel een bewijsvoering voor een algemene (tot op vandaag nog steeds de best gekende) ondergrens ℓ(n) ⩾ n! + (n − )! + (n − )! + n − . Het bewijs werd later gecontroleerd en gepubliceerd als []. Greg Egan kon ook de algemene bovengrens ℓ(n) ⩽ n! + (n − )! + (n − )! + (n − )! + n −  voor n ⩾  aantonen in , hemeltergend dicht bij de bovenstaande ondergrens dus. Vertaald naar het animevraagstuk betekent dit dat de fans minstens  afleveringen na elkaar moeten bekijken, en hoogstens een kleine  miljoen meer.

[1] [anonymous 4chan poster], R. Houston, J. Pantone, V. Vatter, A lower bound on the length of the shortest superpattern. OEIS, 2018. [2] R. Houston, Tackling the minimal superpermutation problem. arXiv:1408.5108, 2014. [3] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A180632.



18

Kirkmans schoolmeisjesprobleem

In  verscheen een beroemde combinatoriekpuzzel in The Lady’s and Gentleman’s Diary, een tijdschrift voor recreatieve wiskunde. Het vraagstuk werd gesteld door Thomas Kirkman en gaat als volgt. Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast. Met andere woorden, partitioneer een verzameling met  elementen op zeven manieren in telkens vijf drietallen, en wel op zo’n manier dat iedere twee elementen samen voorkomen in hoogstens e´e´n drietal. De opgave blijkt best een harde noot: op het herordenen van drietallen of hernoemen van elementen na, zijn er slechts zeven essentieel verschillende oplossingen. Hieronder staat er zo eentje (met de elementen {A, B, . . . , N, O}). maandag {A, B, C} {D, E , F } {G, H, I } { J , K, L } {M, N, O}

dinsdag {A, D, G} {B, E , H} {C , J , M} { F , K, N} { I , L , O}

woensdag {A, E , O} {B, I , J } {C , D, N} { F , H, L } {G, K, M}

donderdag {A, F , J } {B, K, O} {C , G, L } {D, H, M} { E , I , N}

vrijdag {A, H, K} {B, G, N} {C , F , I } {D, J , O} { E , L , M}

zaterdag {A, I , M} {B, D, L } {C , E , K} { F , G, O} {H, J , N}

zondag {A, L , N} {B, F , M} {C , H, O} {D, I , K} { E , G, J }

Ieder van de schoolmeisjes moet op elk van de zeven dagen met twee nieuwe meisjes samen lopen, en omdat er geen koppels dubbel mogen optreden, betekent dit dat elk koppel meisjes moet voorkomen in precies e´e´n drietal. Middels blindelings proberen is de puzzel van Kirkman redelijk hopeloos: er zijn gewoonweg veel te veel mogelijkheden, zelfs na enkele slimme reducties. Een manier om een oplossing te vinden, is gebruikmaken van symmetrische meetkundige structuren. Zo gaf Ellery Davis in  (zie []) een oplossing via een kubus. Beschouw de acht hoekpunten, zes zijvlakken, en de kubus op zijn geheel. Uit deze vijftien objecten halen we  drietallen van de volgende vijf types: a. b. c. d. e.

de volledige kubus samen met twee tegenoverliggende zijvlakken; de volledige kubus samen met twee tegenoverliggende hoekpunten; e´e´n zijvlak samen met twee hoekpunten op een zijde ervan; drie zijvlakken die een hoekpunt gemeenschappelijk hebben; e´e´n zijvlak samen met twee diagonale hoekpunten van het tegenoverliggende zijvlak.

Van type a zijn er drie te vinden, van type b vier. Van type c zijn er in totaal , maar omdat we geen drietallen met twee gemeenschappelijke elementen willen, kunnen we slechts de helft van gebruiken. Ook voor type d zijn maar vier van de acht drietallen bruikbaar. Tot slot zijn er nog twaalf van type e.



Elk drietal van type a kan worden vervolledigd tot een partitie door middel van vier drietallen van type e, en elk drietal van type b met e´e´n van type d en drie van type c, voor een correcte oplossing van het vraagstuk van Kirkman. Hieronder volgt een grafische weergave, waarbij het symbool ⋆ de volledige kubus voorstelt. maandag

dinsdag

⋆

⋆

woensdag donderdag

⋆

vrijdag

zaterdag

zondag

⋆

⋆

⋆

⋆

Giovanni Falcone en Marco Pavone gaven in  (zie []) via een tetra¨eder een alternatieve meetkundige constructie; meer precies diens vier hoekpunten, zes ribben, vier zijvlakken, en de volledige tetra¨eder. Ze gaven er tevens enkele verbanden met projectieve meetkunde. Kirkman zelf besprak in een eerste publicatie [] (drie jaar voor hij de puzzelvorm uitbracht) al een analyse van een algemener probleem: het bepalen van het maximale aantal drietallen uit een verzameling van n elementen zodanig dat geen enkel paar elementen in verschillende drietallen voorkomt. Noem dit maximale aantal K(n). Via een dubbele telling van het aantal paren uit n elementen leren we dat K(n) ⩽ 21 n(n − ), waarbij gelijkheid geldt als en slechts als elk paar elementen optreedt in precies e´e´n drietal. In dat geval treedt elk van de n elementen op in (n − )/ drietallen. We zien dat  ∣ n(n − ) en dat  ∣ n − , wat enkel kan gelden als n ≡  (mod ) of n ≡  (mod ). Bovendien is er in het probleem van Kirkman een extra conditie verscholen: de drietallen moeten kunnen worden opgedeeld in (n − )/ “parallelklassen” met elk n/ onderling disjuncte drietallen, en daartoe moet bovendien  ∣ n. De veralgemeende puzzel van Kirkman voor n elementen heeft dus enkel hoop op een oplossing wanneer n ≡  (mod ).



Omgekeerd is het absoluut niet evident dat er voor iedere n ≡  (mod ) ook een oplossing zou bestaan, maar zoals Dijen Ray-Chaudhuri en Richard Wilson in  aantoonden, is dit wel degelijk zo ([]). Het kleinste geval n =  is triviaal: je kunt drie elementen inderdaad in e´e´n drietal stoppen. Het geval n =  heeft een essentieel unieke oplossing, namelijk de volgende vier partities. {A, B, C} {D, E , F } {G, H, I }

{A, D, G} {B, E , H} {C , F , I }

{A, E , I } {B, F , G} {C , D, H}

{A, F , H} {B, D, I } {C , E , G}

Vervolgens is n =  net het vraagstuk van Kirkman, met zeven oplossingen. Voor hogere n lijkt het aantal oplossingen sterk toe te nemen: het exacte aantal voor n =  is nog steeds niet precies bepaald, maar er zijn er reeds minstens  gekend ([])!

[1] M. Cohen, C. Colbourn, L. Ives, A. Ling, Kirkman triple systems of order  with nontrivial automorphism group. Mathematics of Computation, vol. 71, no. 238, 2002, p. 873–881. [2] E. Davis, A geometric picture of the fifteen school girl problem. The Annals of Mathematics, vol. 11, no. 1–6, p. 156–157. [3] G. Falcone, M. Pavone, Kirkman’s tetrahedron and the fifteen schoolgirl problem. American Mathematical Monthly, vol. 118, no. 10, 2011, p. 887–900. [4] T. Kirkman, On a problem in combinations. The Cambridge and Dublin Mathematical Journal, vol. 2, 1847, p. 191–204. [5] D. Ray-Chaudhuri, R. Wilson, Solution of Kirkman’s schoolgirl problem. Proceedings of Symposia in Pure Mathematics, Combinatorics, vol. 19, 1971, p. 187–203.



18

(todo)

18.1 Designtheorie

18.12 Genererende functies

18.2 Eulerkarakteristiek

18.13 Vierkleurenprobleem, veelvlak van Szilassi, vermoeden van Tait

18.3 Partities 18.4 Gemutileerde schaakbord 18.5 Lemma van Sperner

18.14 Catalangetallen 18.15 Zigzagpermutaties

18.6 Rij van Gijswijt

18.16 Dominantieproblemen

18.7 Gracieuze bomen

18.17 Blokkentorens van Langford

18.8 Jongleerpatronen

18.18 Lemma van Tucker

18.9 Stelling van Erd˝os–Szekeres, Dilworth, Mirsky

18.19 Paardenrondgangen

18.10 Stelling van Ramsey

18.20 Hamiltonpaden en stelling van Grinberg

18.11 Happy ending problem

18.21 Eulerpaden en Koningsbergen



Algebra

19

Gershgorincirkels

Het bepalen van de eigenwaarden van een algemene complexe n × n-matrix is best een pittig probleem, ook (of in het bijzonder) numeriek. Een resultaat van Semyon Gershgorin uit  kan de eigenwaarden helpen lokaliseren en geeft tevens een meetkundige interpretatie. Zij M = (m i j ) een vierkante matrix over C met rang n. Voor elke index  ⩽ i ⩽ n defini¨eren we een Gershgorinschijf in het complexe vlak, met als middelpunt het diagonaalelement m ii en met als straal de som van de moduli van de andere elementen op de i-de rij, ∑∣m i j ∣. j≠i

Per definitie nemen we ook de rand van de schijf mee. Stelling. Iedere eigenwaarde van M ligt in (minstens) e´e´n van diens Gershgorinschijven. Bewijs. Beschouw een eigenwaarde λ van M en kies een bijhorende eigenvector v. Herschaal deze vector tot de in modulus grootste component gelijk is aan de eenheid, zodat v i =  voor een zekere i terwijl ∣v j ∣ ⩽  voor alle j ≠ i. Daar M ⋅ v = λv volgt in de i-de component dat n

λ = λv i = ∑ m i j v j = m ii + ∑ m i j v j j=1

j≠i

en de rest volgt uit de driehoeksongelijkheid: ∣λ − m ii ∣ ⩽ ∑ ∣m i j ∣ ⋅ ∣v j ∣ ⩽ ∑ ∣m i j ∣. j≠i

j≠i

Deze laatste waarde is precies de straal van de i-de Gershgorinschijf.

∎

Pas de stelling toe op de getransponeerde matrix (die uiteraard dezelfde eigenwaarden heeft) om te zien dat we ook de kolommen mogen gebruiken in plaats van de rijen bij het opstellen van de Gershgorincirkels. Beschouw als voorbeeld een matrix van rang drie, −  ⎞ ⎛  M = ⎜i +  −  ⎟ . ⎝    + i⎠ Van twee van de drie Gershgorincirkels in het complexe vlak ligt het centrum op de re¨ele as. √ De eigenwaarden van M blijken gelijk aan  + i en ± φ −  ⋅ (φi − ) (met φ de gulden snede),



en deze liggen wel degelijk binnen de unie van de drie Gershgorinschijven. De eerste figuur toont de cirkels horende bij M, de tweede figuur bij M T .

Merk op dat een van de Gershgorinschijven rechts ontaardt naar een enkel punt. Bovendien zien we links e´e´n cirkel die geen enkele eigenwaarde bevat, dus het is niet noodzakelijk waar dat elke Gershgorinschijf juist e´e´n eigenwaarde zou moeten bevatten. Wel kan men bewijzen dat als een unie van k schijven niet overlapt met de overige n − k, dat er binnen deze unie dan precies k eigenwaarden moeten liggen; een schijf die volledig los staat van alle overige, bevat dus juist e´e´n eigenwaarde. Voor een diagonaalmatrix—waar iedere Gershgorincirkel gereduceerd wordt tot een punt— zijn de eigenwaarden gelijk aan de elementen op de diagonaal. Het ligt dus voor de hand dat een terugkerend achterliggend idee in de numerieke analyse is om een matrix “zo diagonaal mogelijk” te maken. Matrices diagonaliseren is computationeel nog steeds een zware klus, maar er zijn wel effici¨entere technieken die de normen van de elementen buiten de diagonaal kleiner trachten te krijgen. Het resultaat van Gershgorin kan dan handige afschattingen geven op de gemaakte fouten.

¨ [1] S. Gershgorin, Uber die Abgrenzung der Eigenwerte einer Matrix. Izvestija Akademii Nauk SSSR, Serija Matematika, vol. 7, no. 3, 1931, p. 749–754.



20

Sturmketens

Hoe kan men, gegeven een veelterm p met re¨ele co¨effici¨enten en een re¨eel interval, bepalen hoeveel wortels p in dit interval liggen heeft? Onder andere Ren´e Descartes, Michel Rolle, Joseph-Louis Lagrange en Joseph Fourier braken zich het hoofd over dit belangrijke algebra¨ısche probleem. De eerste die een algemene oplossing vond was Augustin-Louis Cauchy, maar op een omslachtige en onpraktische manier; het was Frans wiskundige Charles Sturm die in  als eerste een verrassend eenvoudig algoritme beschreef (in []). De methode van Sturm bouwt een keten van polynomen op waarvan de graden strikt dalen. Elke volgende term is het tegengestelde van de rest bij polynomiale deling van de vorige twee, te beginnen met p en zijn afgeleide veelterm, tot een constante wordt bereikt. p0 = p,

p1 = p′,

p2 = − rem(p, p′ ),

...

p k+1 = − rem(p k−1 , p k ),

...

Aangezien de graden van de polynomen steeds dalen, is de lengte van zo’n Sturmketen van p hoogstens deg p + . Steunend op deze keten definieerde Sturm daarna de functie ν ∶ R → R waarbij elke functiewaarde ν(x) gelijk is aan het aantal tekenwisselingen in de rij p0 (x),

p1 (x),

p2 (x),

...

p k+1 (x),

...

Een tekenwisseling slaat hier op een omslag van een (strikt) positieve waarde naar een (strikt) negatieve waarde of omgekeerd; eventuele nulwaardes tellen niet mee. De bedoeling van deze Sturmketens en de functie ν wordt duidelijk in de volgende stelling. Stelling (Sturm). Zij p een veelterm met uitsluitend enkelvoudige wortels en beschouw twee re¨ele getallen a en b met a < b. Dan is het aantal wortels van p in het halfopen interval ]a, b] gelijk aan ν(a) − ν(b). Bewijs. Zij p0 , p1 , . . . , p ℓ de Sturmketen. Het bewijs steunt op twee observaties: . voor elke wortel x van p0 geldt dat p1 (x) ≠ ; . voor elke wortel x van p k (met  ⩽ k < ℓ) geldt dat p k−1 (x) = −p k+1 (x) ≠ . De eerste observatie volgt direct uit de assumptie dat p = p0 geen meervoudige wortels heeft. De tweede observatie volgt uit de definitie van de Sturmketen, aangezien p k−1 = q k ⋅ p k − p k+1 voor zekere quoti¨entveelterm q k . Bovendien hebben opeenvolgende veeltermen in de keten geen wortels gemeen. Onderstel immers dat p k (x) = p k+1 (x) = , dan zou ook p k−1 (x) = q k (x) ⋅ p k (x) − p k+1 (x) = ,



zodat x ook een wortel van de vorige term p k−1 blijkt, et cetera. Volgens de recursieve definitie zou uiteindelijk ook p(x) = p′ (x) = , in strijd met de eerste observatie. Gewapend met deze twee observaties kunnen we nu het resultaat van Sturm verklaren. Rond een bepaald punt x kan de functiewaarde ν(x) slechts wijzigen indien het teken van een van de beeldwaarden p0 (x), p1 (x), . . . , p ℓ (x) wijzigt. Gezien veeltermen continue functies zijn, kan dit slechts optreden rond een wortel x van een term in de Sturmrij. We zullen aantonen dat een wortel van p0 de waarde van ν met e´e´n doet afnemen, terwijl de wortels van verdere veeltermen de waarde van ν invariant laten. De laatste veelterm p ℓ is per constructie constant en heeft geen wortels, dus zij x een wortel van p k met  ⩽ k < ℓ. De tweede observatie leert dat p k−1 (x) en p k+1 (x) tegengestelde tekens hebben, dus—afhankelijk van welke tekens net en afhankelijk van of p k stijgt of daalt in x— zijn er vier mogelijkheden voor de tekens van (p k−1 , p k , p k+1 ) vlak voor en vlak na x: (− − +) → (− + +),

(− + +) → (− − +),

(+ − −) → (+ + −),

(+ + −) → (+ − −).

In elk van de gevallen blijft het netto aantal tekenwijzigingen constant. Zij x nu een wortel van p0 . De eerste observatie leert dat p0 een constant teken heeft rond x, dus—afhankelijk van welk teken net—zijn er twee mogelijkheden voor de tekens van (p0 , p1 ) vlak voor en vlak na x: (− +) → (+ +), (+ −) → (− −). In elk van de gevallen neemt het netto aantal tekenwijzigingen met e´e´n af. Het verschil ν(a) − ν(b) komt dus overeen met het aantal wortels van p0 tussen a en b.

∎

Er bestaat een uitbreiding naar onbegrensde intervallen door ook op oneindig een notie van teken van een veelterm te defini¨eren. Stel dit teken op +∞ gelijk aan het teken van de leidende co¨effici¨ent, en op −∞ hetzelfde teken voor even graad en het tegengestelde teken voor oneven graad. De stelling van Sturm blijft gelden in deze uitbreiding. Beschouw als voorbeeld de veelterm p(x) = x 5 − x 2 + . Daarvoor wordt de Sturmketen p0 = x 5 − x 2 + ,

p1 = x 4 − x,

p2 = x 2 − ,

p3 = x − ,

en onderstaande tabel geeft de tekens van enkele beeldwaarden in de keten weer. x −∞ − −    ∞



p0 (x) p1 (x) p2 (x) p3 (x) p4 (x) − + + − + − + + − + − +  − + +  − − + − −  + + + + + + + + + + + +

ν(x)       

p4 = 49 ,

In dit voorbeeld kan men zo al drie wortels van de veelterm beginnen localiseren: er ligt er eentje tussen − en , eentje tussen  en , eentje tussen  en , en bovendien leren de waarden ν(−∞) en ν(+∞) op oneindig dat p geen andere re¨ele wortels meer heeft. De methode zoals nu beschreven werkt slechts voor veeltermen waarvan a priori geweten is dat alle wortels enkelvoudig zijn. Er bestaat een methode om ook met algemene veeltermen om te gaan, door eerst een quoti¨ent met de afgeleide veelterm te bepalen, maar we verwijzen naar de literatuur (bijvoorbeeld hoofdstuk  in []) voor details. Liouville sprak vol lof over de vondst van Sturm ([]): “Par cette d´ecouverte capitale, M. Sturm a tout a` la fois simplifi´e et perfectionn´e, en les enrichissant de r´esultats nouveaux, les e´l´ements d’alg`ebre.” Ook Hermite had lovende woorden ([]), en noemde het resultaat “un exemple rare de simplicit´e et d’´el´egance, qui ouvre l’`ere nouvelle de l’alg`ebre moderne.” Sturmketens vormden een sleutelstuk in Emil Artins oplossing van Hilberts de probleem in , en in Alfred Tarski’s gevierde resultaat uit  dat de elementaire theorie van re¨eel gesloten velden compleet is. Ook praktisch is het isoleren van wortels in de computeralgebra van fundamenteel belang. Desondanks is de stelling vandaag wat in de vergetelheid geraakt, omdat alternatieve methodes, gebaseerd op de tekenregel van Descartes (zie curiosum ??), computationeel effici¨enter blijken.

[1] H. Benis-Sinaceur, Deux moments dans l’histoire du th´eor`eme d’alg`ebre de Ch. F. Sturm. Revue d’histoire des sciences, vol. 41, no. 2, 1988, p. 99–132. [2] H. D¨orrie,  great problems of elementary mathematics: their history and solution. Dover Publications, 1965. [3] E. Prouhet, Notice sur la vie et les travaux de M. Ch. Sturm. Nouvelles Annales Math´ematiques, vol. 15, 1856, p. 72–89. [4] J. Sturm, M´emoire sur la r´esolution des e´quations num´eriques. Bulletin des Sciences de F´erussac, vol. 11, 1829, p. 419–425. [5] J. Thomas, Sturm’s theorem for multiple roots. National Mathematics Magazine, vol. 15, no. 8, 1941, p. 391–394.



21

Formules van Vieta

Franc¸ois Vi`ete, beter gekend onder de latinisering Franciscus Vieta, doorzag in de de eeuw als eerste een handige wetmatigheid tussen de co¨effici¨enten en de wortels van veeltermen. Stelling (formules van Vieta). Een algemene complexe veelterm van graad n, p(x) = a n x n + a n−1 x n−1 + ⋯ + a1 x + a0 met a n ≠ , heeft precies n (niet noodzakelijk verschillende) complexe wortels x1 , x2 , . . . , x n volgens de hoofdstelling van de algebra. Voor elke k ∈ {, , . . . , n} geldt dan dat ∑ x i1 ⋅ x i2 ⋯ x i k = (−)k ⋅

a n−k , an

waarbij de som loopt over alle k-tupels van indices  ⩽ i1 < i2 < ⋯ < i k ⩽ n. In het bijzonder is de som van alle wortels gelijk aan −a n−1 /a n (voor k = ) en is het product van alle wortels gelijk aan (−)n a0 /a n (voor k = n).

Bewijs. Kennis van de wortels geeft een factorisatie van de veelterm in lineaire factoren: p(x) = a n x n + a n−1 x n−1 + ⋯ + a1 x + a0 = a n (x − x1 ) ⋅ (x − x2 ) ⋯ (x − x n ). Door deze factorisatie distributief uit te werken en de co¨effici¨enten links en rechts gelijk te stellen, volgen de formules van Vieta. ∎ De formules zijn het best bekend voor tweedegraadsveeltermen. Daar kan men uit de veelterm a2 x 2 + a1 x + a0 meteen aflezen dat er twee wortels zijn met −a1 /a2 als som en met a0 /a2 als product, wat soms handig is om de wortels op het zicht te vinden. De sommaties ∑ x i1 ⋅ x i2 ⋯ x i k over alle indices  ⩽ i1 < i2 < ⋯ < i k ⩽ n zijn de zogenaamde elementaire symmetrische veeltermen in de variabelen x1 , x2 , . . . , x n . Deze heten symmetrisch omdat een permutatie van de variabelen de veelterm invariant laat. Men kan aantonen dat elk zo’n symmetrische veelterm te schrijven is als een polynomiale uitdrukking van deze elementaire veeltermen, en de formules van Vieta laten dan ook toe om elke symmetrische veelterm in de wortels te berekenen uit de co¨effici¨enten (zonder deze expliciet te moeten kennen). Eigenlijk had Franc¸ois Vi`ete deze naar hem vernoemde identiteiten zelf slechts ontdekt voor positieve re¨ele getallen als wortels; de formules in volle algemeenheid zouden voor het eerst begrepen zijn door Albert Girard in de de eeuw.



Ook al zijn Vieta’s formules niet bijzonder ingewikkeld, vormen ze geregeld de basis voor best pittige olympiadevragen en -technieken. Het volgende resultaat was een vraag op de beruchte William Lowell Putnam Mathematical Competition in  ([]). Stelling. De enige monische veeltermen met uitsluitend co¨effici¨enten ± en met uitsluitend re¨ele wortels, zijn x + ,

x − ,

x 2 + x − ,

x 2 − x − ,

x 3 + x 2 − x − ,

x 3 − x 2 − x + .

Bewijs. Het geval n =  is duidelijk, dus stel dat n ⩾ . Zij p(x) = x n + a n−1 x n−1 + ⋯ + a1 x + a0 zo’n veelterm met re¨ele wortels x1 , x2 , . . . , x n . Merk nu op dat 2

 ⩽ ∑ x i2 = ( ∑ x i ) −  ∑ x i x j = a 2n−1 − a n−2 =  − a n−2 ⩽  i

1⩽i⩽n

1⩽i< j⩽n

dankzij de formules van Vieta, en dit legt a n−2 = − vast. Ook is (x1 x2 ⋯ x n )2 =  en volgt uit de ongelijkheid tussen het rekenkundig en meetkundig gemiddelde (zie curiosum ) dat √  n 2 x ⩾ (x1 x2 ⋯ x n )2 = , ∑ n 1⩽i⩽n i zodat n ⩽ ∑ x i2 = . Eenmaal deze bovengrens op de graad van p(x) gevonden, volstaat het om de resterende kandidaat-veeltermen te verifi¨eren. ∎ Een andere illustratie is een olympiadetechniek die bekendstaat onder de naam Vieta jumping of root flipping. Het idee hier is om uit een potenti¨ele oplossing of tegenvoorbeeld een nieuwe te construeren al steunend op Vieta’s identiteiten, en aan te tonen dat deze in een zekere zin kleiner is dan de vorige. Door Fermats principe van oneindige afdaling, of door een minimale oplossing te veronderstellen, vinden we dan een strijdigheid. Het eerste opduiken van deze techniek was op de International Mathematical Olympiad in , in de opgave die hieronder vermeld staat. Arthur Engel schrijft in []: Nobody of the six members of the Australian problem committee could solve it. Two of the members were Georges Szekeres and his wife, both famous problem solvers and problem posers. Because it was a number theory problem, it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the 29th IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.



Stelling. Zij a en b twee natuurlijke getallen. Als ook het quoti¨ent a2 + b2 =k ab +  een geheel getal is, dan is k een volkomen kwadraat. Bewijs. We pakken het probleem omgekeerd aan: we fixeren k en laten (a, b) vari¨eren over alle koppels natuurlijke getallen die voldoen aan a2 + b2 = k, ab +  dus we beschouwen de verzameling S = {(a, b) ∈ N × N ∣

a2 + b2 = k} . ab + 

De opgave stelt dat deze verzameling niet-ledig is, en aldus ook een (niet noodzakelijk uniek) koppel (a, b) bevat dat de som a + b minimaliseert; noem dit koppel (A, B). Via symmetrie mogen we aannemen dat A ⩽ B. Merk op dat als A =  er meteen volgt dat k = B2 inderdaad een volkomen kwadraat is. Voor de rest van het argument mogen we dus A ≠  onderstellen. Beschouw nu de vergelijking

A2 + x 2 =k Ax +  in e´e´n variabele x, die equivalent is met de vierkantsvergelijking x 2 − Ak ⋅ x + (A2 − k) = . We weten reeds dat x1 = B een wortel is van deze vergelijking. De formules van Vieta geven x2 = Ak − B = B1 (A2 − k) als tweede wortel, wat betekent dat ook x2 een geheel getal is. Merk opnieuw op dat als x2 =  er meteen volgt dat k = A2 een volkomen kwadraat is; we mogen dus onderstellen dat x2 ≠ . Tot slot kan x2 niet negatief zijn, want dan zou x22 − Ak ⋅ x2 + (A2 − k) ⩾ x22 + k + (A2 − k) > , een duidelijke strijdigheid omdat x2 een wortel is. Dankzij Vieta’s formules hebben we uit (A, B = x1 ) ∈ S dus een tweede koppel (A, C = x2 ) ∈ S kunnen opstellen. Bovendien, aangezien A ⩽ B geldt er dat C = B1 (A2 − k) < B,



waaruit A + C < A + B, in strijd met de minimaliteit van A + B! Een minimaliserend koppel moet met andere woorden wel van de vorm (A, ) of (, B) zijn, en in de beide gevallen is k een volkomen kwadraat. ∎

[1] A. Engel, Problem-solving strategies. Springer-Verlag, 1998. [2] J. McKay, The William Lowell Putnam Mathematical Competition. American Mathematical Monthly, vol. 76, no. 8, 1969, p. 909–915.



22

Stelling van Marden

Een welbekende stelling van Gauss–Lucas noemt een meetkundig verband tussen de wortels van een complexe veelterm p en de afgeleide veelterm p′. Volgens de stelling zijn alle wortels van p′ bevat binnen de convexe omhullende van de wortels van p in het complex vlak, d.w.z. binnen de kleinste convexe veelhoek die deze wortels van p bevat. Specifiek voor derdegraadsveeltermen geeft de stelling van Marden meer precieze informatie over de locatie van deze wortels. De nulpunten van p bepalen (over het algemeen) drie hoekpunten van een driehoek in het complex vlak. Er bestaat een unieke ellips die de drie zijden van de driehoek juist in hun middelpunt raakt, de ingeschreven ellips van Steiner genoemd, en volgens de stelling van Marden komen de twee nulpunten van p′ dan precies overeen met de twee brandpunten van deze ellips!

De ellips van Steiner voldoet aan nog enkele bijzondere eigenschappen. Zo√ is die de grootste ingeschreven ellips binnen de driehoek, met een oppervlakte gelijk aan π/  keer dat van de driehoek zelf. Ook is het de enige ingeschreven ellips waarvan het middelpunt samenvalt met het zwaartepunt van de driehoek. Merk op dat dit zwaartepunt dan precies de wortel is van de lineaire veelterm p′′. Ook al ontdekte J¨org Siebeck het resultaat eigenlijk al zo’n  jaar eerder dan Morris Marden erover schreef, vernoemde Dan Kalman [] dit juweeltje naar laatstnoemde, met als motivatie “I call this Marden’s theorem because I first read it in M. Marden’s wonderful book []. But this material appeared previously in Marden’s earlier paper. In both sources Marden attributes the theorem to Siebeck, citing a paper from 1864 [].” Ben-Zion Linfeld gaf in  een boeiende veralgemening met betrekking tot veeltermen p(z) = (z − a)i (z − b) j (z − c)k. Naast de meervoudige wortels a, b en c, heeft p′ in dit geval ook wortels op de brandpunten van een bepaalde ellips ingeschreven aan de driehoek bepaald door a, b en c. Hier verdelen de raakpunten de zijden echter volgens verhoudingen i ∶ j, j ∶ k en k ∶ i.



[1] D. Kalman, An elementary proof of Marden’s theorem. American Mathematical Monthly, vol. 115, no. 4, 2008, p. 330–338. [2] B.-Z. Linfield, On the relation of the roots and poles of a rational function to the roots of its derivative. Bulletin of the American Mathematical Society, vol. 27, no. 1, 1920, p. 17–21. [3] M. Marden, Geometry of polynomials. American Mathematical Society, Mathematical Surveys, no. 3, 1966. ¨ [4] J. Siebeck, Uber eine neue analytische Behandlungweise der Brennpunkte. Journal f¨ur die reine und angewandte Mathematik, vol. 64, 1864, p. 175–182.



22

(todo)

22.1 Descartes’ tekenregel 22.2 Littlewoodveeltermen 22.3 Elliptische krommen 22.4 Transcendente getallen 22.5 Stelling van Mason–Stothers 22.6 Wortelverdubbeling van Gr¨affe 22.7 Karatsubavermenigvuldiging 22.8 Cyclotomische veeltermen 22.9 Strook- en behangpatroongroepen 22.10 Schilderijenpuzzels 22.11 Stelling van Abel–Ruffini 22.12 Classificatie van de eindige enkelvoudige groepen



23

Solitaire



Analyse

24

Formule van Wallis

De formule van Wallis, een hoogst elegante formule die π uitdrukt als een oneindig product, werd door John Wallis in  afgeleid ([]) uit een analyse van de integralen π

n ∫0 sin x dx

voor even en oneven n. Toentertijd stond de analyse weliswaar nog te zeer in kinderschoenen om de convergentie overtuigend hard te maken, maar zelfs dan was het resultaat van Wallis een indrukwekkende prestatie. Stelling (Wallis). ∞

∏ n=1

n n            π ⋅ = ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋯ = . n −  n +             

Bewijs. Beschouw de integralen I(n) = ∫

0

π

sinn x dx.

Met behulp van parti¨ele integratie (voor n ⩾ ) is I(n) = (n − ) ∫

π 0

π

cos2 x sinn−2 x dx = (n − ) ∫ ( − sin2 x) sinn−2 x dx, 0

wat na herschikken leidt tot de recursieformule I(n) =

n− ⋅ I(n − ). n

Samen met de eenvoudig te berekenen integralen I() = π en I() =  volgt dan recursief I(n) =

n −  n −   ⋅ ⋯ ⋅ π, n n −  

I(n + ) =

n n −   ⋅ ⋯ ⋅ . n +  n −  

De integralen I(n) vormen een niet-stijgende rij getallen, zodat n +  I(n − ) I(n) I(n + ) = ⩽ ⩽ = , n I(n + ) I(n + ) I(n + )



en ten slotte kunnen we hier de sandwichstelling op toepassen aangezien het linkerlid naar  convergeert in de limiet n → ∞. Er volgt dat ook π ∞ n −  n +  I(n) = ⋅∏ ⋅ . n→∞ I(n + )  n=1 n n

 = lim

∎

Grappig genoeg convergeert het product naar een volledig andere waarde als we alle factoren voor even n eruit laten! Het blijkt dat ∞

∏ n=1

√ n −  n −        ⋅ = ⋅ ⋅ ⋅ ⋅ ⋅ ⋯ = . n −  n −       

In een gevierd werk uit  ([]) ontdekte Leonhard Euler de volgende straffe veralgemening; de formule van Wallis verkrijg je door x = / in te vullen. sin πx ∞  − x  + x =∏ ⋅ πx n n=1 n Behalve variaties op het analytische bewijs van Wallis werden ondertussen meer elementaire (maar ook breedvoerige) bewijzen gevonden. In  ontdekten natuurkundigen Carl Hagen en Tamar Friedmann ook een verrassend optreden van de formule in kwantummechanische berekeningen van energieniveaus van het waterstofatoom ([]).

[1] L. Euler, De summis serierum reciprocarum. Commentarii Academiae Scientiarum Imperialis Petropolitanae, vol. 7, 1735, p. 123–134. [2] T. Friedmann, C. Hagen, Quantum mechanical derivation of the Wallis formula for π. Journal of Mathematical Physics, vol. 56, no. 11, 2015. [3] J. Wallis, Arithmetica Infinitorum. Oxford, 1655.



25

Integraal van Gauss

De integraal van Gauss is een bijzonder belangrijke integraal die gevarieerde applicaties kent in o.a. de statistiek en de kwantummechanica. Concreet gaat het om de bepaalde integraal +∞ 2 ∫ exp(−x ) dx. −∞

Men kan bewijzen dat de onbepaalde integraal niet uitgedrukt kan worden door middel van elementaire functies, dus zo eenvoudig valt die niet te kraken. Een standaardmethode volgt een idee van Sim´eon Denis Poisson en maakt gebruik van poolco¨ordinaten. Hier geven we een magisch alternatief argument, terug te vinden in []. Stelling. De bepaalde integraal ∫−∞ exp(−x 2 ) dx van Gauss is gelijk aan +∞

√

π.

Bewijs. Het geheim zit ’m in het op twee manieren evalueren van de dubbelintegraal +∞ +∞

Φ = ∫ ∫ x exp(−x 2 (y2 + )) dx dy. 0

0

Enerzijds geeft eerst integreren naar x als resultaat +∞

+∞

− exp(−x 2 (y 2 + )) π    +∞ Φ=∫ [ dy = [ arctan(y)]0 = . ] dy = ∫ 2 2    (y + ) y + 0 +∞

0

0

Anderzijds geeft eerst integreren naar y, via de substitutie t = x y en dt = x dy, als resultaat +∞ +∞

+∞

+∞

A2 Φ = ∫ ∫ exp(−t − x ) dt dx = ∫ exp(−t ) dt ⋅ ∫ exp(−x 2 ) dx = ,  2

0

0

2

2

0

0

met A de gezochte integraal. Stel beide uitdrukkingen gelijk en er volgt dat A =

√

π.

∎

De integraal van Gauss is nodig om de normalisatiefactor van de normaalverdeling te vinden; zie curiosum ?? voor toepassingen in de statistiek.

[1] H. Iwasawa, Gaussian integral puzzle. The Mathematical Intelligencer, vol. 31, no. 3, 2009, p. 38–41.



26

Stelling van Sharkovsky

Beschouw een continue afbeelding f ∶ I → I op een interval I ⊆ R. We noemen een punt x0 periodiek indien f k (x0 ) = x0 voor een zekere k (met f k = f ○ f ○ ⋯ ○ f , k keer ge¨ıtereerd), en de minimale k met deze eigenschap noemen we dan de periode van x0 . Merk op dat punten met periode k =  per definitie niets meer zijn dan fixpunten van f . Laat ons bijvoorbeeld kijken naar de afbeelding f ∶ R → R ∶ x ↦ x 2 − . De twee fixpunten √ x0 = − en x0 =  zijn snel gevonden, en een eenvoudige controle wijst uit dat x0 = (  − )/ (het kleine broertje van de gulden snede) een punt is met periode twee. Er blijkt ook een punt met periode drie te bestaan, π x0 =  cos ( ),  en een punt met periode vier, √ √ √  −   +  +  . x0 =  Het is niet moeilijk om voor algemene continue f aan te tonen dat het bestaan van een punt x0 met periode twee ook het bestaan van een fixpunt impliceert. Definieer immers de continue afbeelding g ∶ I → I ∶ x ↦ f (x) − x, en merk op dat g( f (x0 )) = x0 − f (x0 ) = −g(x0 ). De functiewaarden van x0 en f (x0 ) onder g verschillen van nul en hebben tegengesteld teken. De tussenwaardestelling leert dan dat g een nulpunt moet hebben, of met andere woorden f een fixpunt, ergens tussen x0 en f (x0 ). Met wat extra moeite impliceren punten met periode n+1 ook punten met periode n , . . . , 2 , ,  (via volledige inductie op n, en de functie f 2 ). Oekra¨ıens wiskundige Oleksandr Sharkovsky vond een verrassend algemener resultaat. Eerst defini¨eren we een zonderlinge ordening op de natuurlijke getallen; we stellen r ⋅ p s ⋅ q (met p en q oneven) indien ofwel r < s en p > , ofwel r = s en p < q, ofwel r > s en p = q = .     ⋯  ⋅   ⋅   ⋅  ⋯ 2 ⋅  2 ⋅  ⋯ 3 ⋅  ⋯ 3 2  . Dit legt een totale orde op N0 vast: eerst komen alle oneven getallen in oplopende volgorde, dan de tweevouden van de oneven getallen, de viervouden van de oneven getallen, enzovoort, tot alle machten van twee in aflopende volgorde de ordening afsluiten. Stelling (Sharkovsky). Zij f ∶ I → I continu. Als m n in de Sharkovsky-ordening en als f een periodiek punt met periode m heeft, dan heeft f ook een periodiek punt met periode n.



∎ Ò

Zonder bewijs. Zie bijvoorbeeld [].

In het bijzonder heeft een functie met punten van periode drie (zoals het voorbeeld hogerop) meteen punten van eender welke periode! Daarnaast volgt dat als een functie slechts eindig veel periodes heeft, al deze periodes noodzakelijk machten van twee zijn. Het originele bewijs van Sharkovsky uit  ([]) gebruikt geen geavanceerdere wiskundige machinerie dan herhaaldelijk de tussenwaardestelling, maar was vrij laborieus en verscheen in het Russisch. Daardoor bleef het resultaat onopgemerkt, tot Tien-Yien Li en James Yorke zo’n tien jaar later het speciale gevolg voor periode--cykels herontdekten ([]). Zij bewezen daarenboven weliswaar dat een punt met periode drie ook het bestaan van overaftelbaar veel chaotische punten impliceert, die onder f -iteratie nooit naar een cykel convergeren. Behalve een introductie van het concept “chaos” zorgde het artikel van Li en Yorke tot een erkenning van Sharkovsky’s werk, waarvoor sindsdien meerdere vereenvoudigingen gevonden zijn. Het resultaat van Sharkovsky geldt eveneens in de omgekeerde richting: voor iedere m n kan men functies construeren met periode-n-punten maar zonder periode-m-punten. De continu¨ıteitsvoorwaarde op f is wel degelijk van groot belang. Voor de volgende functie, die slechts e´e´n discontinu¨ıteit heeft, is namelijk ieder punt periodiek met periode drie! f ∶ R ∖ {} → R ∶ x ↦

 −x

Ook uitbreidingen naar meerdimensionale functies zijn niet zo evident: de afbeelding die R2 over π/ radialen rond de oorsprong roteert, heeft behalve de oorsprong ook enkel punten met periode drie.

[1] K. Burns, B. Hasselblatt, The Sharkovsky theorem: a natural direct proof. American Mathematical Monthly, vol. 118, no. 3, 2011, p. 229–244. [2] T.-Y. Li, J. Yorke, Period three implies chaos. American Mathematical Monthly, vol. 82, no. 10, 1975, p. 985–992. [3] A. Sharkovsky, Co-existence of cycles of a continuous mapping of the line into itself. Ukrainian Mathematical Journal, vol. 16, no. 3, 1964, p. 61–71.



27

Gemiddelden

In volle algemeenheid is een gemiddelde een functie M ∶ I n → I voor een interval I ⊆ R, die voor al zijn invoerwaarden voldoet aan de volgende vier eigenschappen: • M(x, x, . . . , x) = x voor alle x ∈ I (behoud van waarde); • M(sx1 , sx2 , . . . , sx n ) = s ⋅ M(x1 , x2 , . . . , x n ) (homogeniteit); • M(x1 , x2 , . . . , x n ) = M(x σ(1) , x σ(2) , . . . , x σ(n) ) voor elke permutatie σ (symmetrie); • min(x1 , x2 , . . . , x n ) ⩽ M(x1 , x2 , . . . , x n ) ⩽ max(x1 , x2 , . . . , x n ) (middeling). Het klassieke voorbeeld van een gemiddelde, dat standaard zelfs gewoonweg h´et gemiddelde genoemd wordt, is het rekenkundig gemiddelde (voor I = R), A(x1 , x2 , . . . , x n ) =

x1 + x2 + ⋯ + x n . n

Pythagoras, zijn volgelingen en latere Griekse wiskundigen bestudeerden ook enkele andere voorbeelden, zoals het meetkundig gemiddelde (voor I = R+ ), √ G(x1 , x2 , . . . , x n ) = n x1 ⋅ x2 ⋯ x n , en het harmonisch gemiddelde (voor I = R+0 ), H(x1 , x2 , . . . , x n ) =

1 x1

+

1 x2

n +⋯+

1 xn

.

Nog een voorbeeld is het kwadratisch gemiddelde (voor I = R+ ), √ x12 + x22 + ⋯ + x n2 Q(x1 , x2 , . . . , x n ) = . n Ook het minimum en maximum van een n-tupel voldoen aan de vier eigenschappen en vormen dus twee extreme (ontaarde) voorbeelden van gemiddelden. Merk op dat het rekenkundig en het harmonisch gemiddelde aan een soort dualiteit voldoen, in de zin dat A(x1−1 , x2−1 , . . . , x n−1 ) net gelijk is aan H(x1 , x2 , . . . , x n )−1 en vice versa. Minimum en maximum vervullen dezelfde dualiteit; het meetkundig gemiddelde is gelijk aan zijn duale. De pythagoree¨ers waren niet zonder reden ge¨ınteresseerd in de gemiddelden A, G en H, die nu bekendstaan als de Pythagorische gemiddelden; Pythagoras zelf hechtte namelijk zekere mystieke krachten toe aan (verhoudingen tussen) getallen en deze gemiddelden speelden een belangrijke rol in zijn theorie¨en. Zo stelde hij op basis van de rekenkundige, meetkundige en harmonische gemiddelden van eenvoudige getallen, uitvoerige systemen op voor de muziek.



Voor het geval n =  bestaat er bovendien een boeiende meetkundige interpretatie:

A Q

H

x1

G

A = A(x1 , x2 ) G = G(x1 , x2 ) H = H(x1 , x2 ) Q = Q(x1 , x2 )

x2

Zoals deze tekening reeds suggereert, voldoen de vier beschreven gemiddelden aan een heel praktisch verband (dat opgaat voor algemene n) dat voor vele ongelijkheden zijn nut bewijst. Er geldt namelijk voor willekeurige x⃗ ∈ I n dat min(x⃗) ⩽ H(x⃗) ⩽ G(x⃗) ⩽ A(x⃗) ⩽ Q(x⃗) ⩽ max(x⃗),

(.)

en gelijkheid treedt slechts op als alle componenten van x⃗ gelijk zijn. Bewijs voor n = . E´en mogelijkheid om deze ongelijkheden aan te tonen (voor twee getallen) maakt gebruik van Pythagorische drietallen (a, b, c), positieve getallen waarvoor a2 + b 2 = c 2 zodat in het bijzonder a < c en b < c. Reken zelf na dat volgende drietallen Pythagorisch zijn voor alle  < x1 < x2 : √ x − x1 , H(x⃗), G(x⃗)), ( x1 x2 ⋅ 2 y2 + x1

(

x2 − x1 , G(x⃗), A(x⃗)), 

(

x2 − x1 , A(x⃗), Q(x⃗)). ∎ 

Elk van deze concrete voorbeelden is een speciaal geval van het algemene machtsgemiddelde of H¨oldergemiddelde (naar Otto H¨older), als volgt gedefinieerd voor willekeurige p ≠ : √ p p p p x1 + x2 + ⋯ + x n M p (x1 , x2 , . . . , x n ) = . n Voor welgekozen p vinden we de vertrouwde gemiddelden terug: lim M p = min,

p→−∞

M−1 = H,

lim M p = G, p→0

M1 = A,

M2 = Q,

lim M p = max.

p→∞

De ongelijkheden in (.) veralgemenen naar het machtsgemiddelde. Stelling. Voor alle parameters p < q en alle positieve x1 , . . . , x n geldt dat M p (x⃗) ⩽ Mq (x⃗), met gelijkheid als en slechts als x1 = x2 = ⋯ = x n .



Bewijs. Er zijn drie mogelijkheden: p < q < , p <  < q, of  < p < q. Beschouwen we voor het gemak deze laatste situatie (de rest verloopt analoog). Definieer de functie f (x) = x q/p en bemerk dat f ′′ (x) >  voor x > , zodat f strikt convex is. De ongelijkheid van Jensen (met gewichten w i ) leert dan dat n

p

x (∑ i ) i=1 n

q/p

p

p

q

n f (x ) n x x i = f (∑ i ) ⩽ ∑ =∑ i . n i=1 n i=1 i=1 n n

Beide leden tot de macht /q verheffen (wat de ongelijkheid bewaart, aangezien /q positief is) geeft de gezochte ongelijkheid: n

p

1/p

x M p (x1 , . . . , x n ) = (∑ i ) i=1 n

n

⩽ (∑ i=1

q

xi ) n

1/q

= Mq (x1 , . . . , x n ).

∎

Er kan nog een verdere veralgemening gemaakt worden, door voor een willekeurige continue injectieve functie ϕ ∶ I → R, de afbeelding Mϕ (x1 , x2 , . . . , x n ) = ϕ−1 (

ϕ(x1 ) + ϕ(x2 ) + ⋯ + ϕ(x n ) ) n

te stellen. Voor arbitraire ϕ voldoet Mϕ echter niet langer aan de homogeniteitsvoorwaarde, tenzij voor het algemene machtsgemiddelde (met ϕ(x) = x p ) of het meetkundig gemiddelde (met ϕ(x) = log(x)); zie [] voor een bewijs.

[1] G. Hardy, J. Littlewood, G. P´olya, Inequalities. Cambridge University Press, 2de editie, 1952.



27

(todo)

27.1 Sophomore’s dream 27.2 Gammafunctie

27.8 Tussenwaardestelling en 13-functie van Conway

27.3 Probleem van Basel

27.9 Stelling van McMullin

27.4 Formule van Stirling

27.10 Monster van Weierstrass

27.5 Integralen van Borwein

27.11 Stelling van de universele koorden

27.6 Harmonische reeks en varianten

27.12 Fixpuntstelling van Brouwer (lemma van Sperner)

27.7 Hoorn van Gabri¨el



Kansrekening

28

Parkeerprobleem van R´eyni

We beschrijven een stochastisch proces waarbij een aantal ge¨ıdealiseerde auto’s met eenheidslengte parkeren langs een straat met lengte x. Zolang er ruimte is, parkeert de volgende auto op een (uniform verdeelde) willekeurige onbezette positie. Het parkeerprobleem van Alfr´ed R´enyi vraagt dan naar het verwachte aantal auto’s in functie van x. Deze verwachtingswaarde zullen we met M(x) aanduiden; de gemiddelde dichtheid van de auto’s is dan M(x)/x. Voor x <  geldt uiteraard dat M(x) = . Beschouw een straat met lengte x +, die we kunnen modelleren als het interval [, x + ]. Onderstel dat de eerste auto parkeert op [t, t + ], met t uniform verdeeld tussen  en x, dan blijven er voor de tweede auto twee kleinere intervallen met lengtes t en x − t over. Het verwachte aantal conditioneel op de positie t van de eerste auto wordt dus gegeven door  + M(t) + M(x − t). Door t weg te integreren vinden we zo een recursieformule geldig voor alle x ⩾ : M(x + ) =

x x   ( + M(t) + M(x − t)) dt =  + ∫ M(t) dt. ∫ x 0 x 0

Deze differentiaalvergelijking laat toe om het domein van een expliciete vorm voor M stapsgewijze uit te breiden, te beginnen met ⎧  voor  ⩽ x < , ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ voor  ⩽ x < , ⎪ M(x) = ⎨ ⎪ (x − )/(x − ) voor  ⩽ x < , ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩(x −  log(x − ) − )/(x − ) voor  ⩽ x < , maar daarna wordt de integratie te ingewikkeld om expliciet uit te voeren. Een grafiek van M suggereert dat de gemiddelde dichtheid van de auto’s snel naar een constante convergeert.

grafiek in orde maken



Door middel van berekeningen op de Laplacetransformatie van M kon R´enyi deze constante (de parkeerconstante van R´enyi) expliciet bepalen als ∞ x  − exp(−t) M(x) = ∫ exp (− ∫ dt) dx ≈ . . . . x→∞ x t 0 0

m = lim

en concreet bewees hij dat, voor alle n ⩾ , M(x) = m(x + ) −  + O(x −n ). Gemiddeld wordt dus een kleine driekwart van de straat gevuld (mits die voldoende lang is). Voor een analogon van het parkeerprobleem in twee dimensies vermoedde Ilona Pal´asti dat de gemiddelde dichtheid (in de limiet) wordt gegeven door m2 . Dit is tot op vandaag bewezen noch weerlegd, al suggereren computersimulaties dat de dichtheid ietwat hoger kan liggen. Het parkeerprobleem, hogerdimensionale versies en discrete varianten kennen toepassingen in verscheidene disciplines: modellen van vloeistofstructuur in de fysica, molecuulbindingen in de chemie, optimale plaatsing van data op een cd en analyse van hashing in de informatica, en zelfs de lingu¨ıstiek en sociologie gebruiken modellen gebaseerd op dezelfde idee¨en.

[1] A. Dvoretzky, H. Robbins, On the “parking” problem. Publications of the Math. Institute of the Hungarian Academy of Sciences, vol. 9, 1964, p. 209–226. [2] S. Finch, Mathematical constants. Cambridge University Press, 2003. [3] A. R´enyi, On a one-dimensional problem concerning random space-filling. Publications of the Math. Institute of the Hungarian Academy of Sciences, vol. 3, 1958, p. 109–127. [4] H. Solomon, H. Weiner, A review of the packing problem. Communication in Statistics—Theory and Methods, vol. 15, no. 9, 1986, p. 2571–2607.



29

Kwartet van Anscombe

Francis Anscombe publiceerde in  een vurig pleidooi ([]) om tijdens het analyseren van datasets niet blindelings te vertrouwen op numerieke parameters—al dan niet berekend met de computer—maar de data ook te plotten in een grafiek. Om zijn punt kracht bij te zetten, beschreef Anscombe vier kleine hypothetische datasets van elf punten waarvoor de klassieke beschrijvende statistieken (zoals het gemiddelde en de variantie) nagenoeg hetzelfde blijken. Desondanks zien de data er op een grafiek volledig anders uit! De opzet van Anscombe was om de wijdverspreid heersende opinie “numerical calculations are exact, but graphs are rough” onder statistici tegen te gaan. Uit []: Most kinds of statistical calculation rest on assumptions about the behavior of the data. Those assumptions may be false, and then the calculations may be misleading. We ought always to try to check whether the assumptions are reasonably correct; and if they are wrong, we ought to be able to perceive in what ways they are wrong. Graphs are very valuable for these purposes. Anscombes vier illustratieve datasets zijn de volgende. D1 10 8.04 8 6.95 13 7.58 9 8.81 11 8.33 14 9.96 6 7.24 4 4.26 12 10.84 7 4.82 5 5.68

10 8 13 9 11 14 6 4 12 7 5

D2 9.14 8.14 8.74 8.77 9.26 8.10 6.13 3.10 9.13 7.26 4.74

D3 D4 10 7.46 8 6.58 8 6.77 8 5.76 13 12.74 8 7.71 9 7.11 8 8.84 11 7.81 8 8.47 14 8.84 8 7.04 6 6.08 8 5.25 4 5.39 19 12.50 12 8.15 8 5.56 7 6.42 8 7.91 5 5.73 8 6.89

Als we op deze vier datasets een lineaire regressie loslaten, geven de berekeningen identieke resultaten, samengevat in onderstaande tabel. 9.00 7.50 11.00 4.125 0.816 y = 0.500x + 3.00

Steekproefgemiddelde van x Steekproefgemiddelde van y Steekproefvariantie van x Steekproefvariantie van y Correlatieco¨effici¨ent Lineaire regressie



Bij de eerste dataset vertoont de plot geen verrassingen; dit lijkt een klassiek lineair verband tussen twee gecorreleerde variabelen met normaal verdeelde afwijkingen. In deze situatie is de regressieanalyse heel goed toepasbaar en zouden de resultaten betrouwbaar moeten zijn. De plot in de tweede situatie suggereert met klem dat de data aan een andere relatie voldoen: we merken een kwadratisch verband, en een lineaire regressie heeft maar weinig zin.

D1

D2

Bij de derde situatie is een lineaire regressie wel weer aangewezen, maar blijkt e´e´n uitschieter voldoende om de regressielijn aanzienlijk scheef te trekken. Hier had een robuuste regressie de feitelijke lijn y = 0.346x + 4.00 aan het licht moeten brengen. In de vierde dataset is x een binaire variabele. Een lineaire regressie is hier nog steeds zinvol, maar opnieuw is er een onbevredigende kwestie: de helling van de regressielijn wordt bepaald door e´e´n enkele observatie. Dit ene datapunt verwijderen levert een volledig ander beeld op, wat in de eerste situatie helemaal niet zo was. Hier zou een analyse zeker moeten vermelden dat een enkele observatie een cruciale rol speelt.

D3

D4

De moraal van het kwartet van Anscombe is duidelijk: naast de samenvattende statistieken zijn ook visualisaties van data veelzeggend, en kunnen deze helpen om verklaringen te vinden en foute analyses te voorkomen.

[1] F. Anscombe, Graphs in statistical analysis. The American Statistician, vol. 27, no. 1, 1973, p. 17–21.



30

Paradox van Bertrand

Joseph Bertrand introduceerde deze klassieke paradox in zijn Calcul des probabilit´es in . Beschouw het volgende probleem, dat onschuldig genoeg schijnt: wat is de kans dat een lukrake koorde van een cirkel langer is dan de zijde van een ingeschreven gelijkzijdige driehoek? Er zijn verschillende manieren om dit probleem op te lossen, allen schijnbaar even correct, terwijl hun uitkomsten verschillend zijn. Een eerste manier om een willekeurige koorde te bepalen bestaat erin om eerst een straal van de cirkel te kiezen, en daarna een punt op deze straal. Door dit punt gaat een unieke koorde die loodrecht staat op deze straal, die langer is dan de zijde precies wanneer het voetpunt op de binnenste helft van de straal werd gekozen, zodat de gezochte kans gelijk blijkt aan /.

De middenste figuur toont een verdeling van  aldus gekozen koorden; de rechterfiguur een verdeling van  middelpunten van zo’n koorden. Een andere mogelijkheid bestaat erin om twee willekeurige punten op de cirkel te kiezen en die te verbinden. Roteren we de gelijkzijdige driehoek zodanig dat e´e´n van diens hoekpunten samenvalt met een eindpunt van deze koorde, dan is duidelijk dat de koorde langer zal zijn dan de zijde precies wanneer het andere eindpunt op de tegenoverliggende cirkelboog ligt (tussen de andere twee hoekpunten). Daar de lengte van deze boog een derde van de omtrek van de cirkel bedraagt, moet de gezochte kans gelijk zijn aan /.

Nog een andere mogelijkheid: kies meteen een lukraak punt binnen de cirkel, en beschouw de unieke koorde met dat punt als middelpunt. Deze gekozen koorde is langer dan de zijde



precies wanneer het punt binnen de ingeschreven cirkel van de driehoek valt, en diens straal is half zo groot als die van de originele cirkel. Zo blijkt de gezochte kans /.

Zoals ook de verdelingen aangeven, favoriseert de derde methode koorden aan de buitenkant van de cirkel (met kortere lengtes), terwijl de koorden in de eerste methode veel uniformer verdeeld lijken. De middelpunten zijn dan weer duidelijk dichter bij het centrum geconcentreerd in de eerste methode dan in de derde. De tweede methode schuilt ergens tussenin. De paradox valt niet moeilijk te verklaren—er is eenvoudigweg geen eenduidige manier om te spreken over een “willekeurige” koorde! Zonder erbij te specifi¨eren via welk mechanisme willekeurige elementen worden gekozen, zijn ook bijhorende kansen niet goed gedefinieerd, of zoals Bertrand het zelf verwoordde in [], “Aucune des trois n’est fausse, aucune n’est exacte, la question est mal pos´ee.”

[1] J. Bertrand, Calcul des probabilit´es. Gauthier-Villars, 1889.



30

(todo)

30.1 Intransitieve dobbelstenen

30.4 Dobbelprobleem van Chevalier de M´er´e

30.2 probleem van Monty Hall

30.5 Wet van Benford

30.3 Percolatietheorie?

30.6 Stokjes breken



Meetkunde

31

Hyperbolische meetkunde

De wortels van de hyperbolische meetkunde liggen eigenlijk al in het oude Griekenland, en meer bepaald bij de Elementen (Στοιχεια) van Euclides, daterend van omstreeks  v.Chr. Dit monumentale werk omvat in totaal dertien delen met definities, constructies, stellingen en bewijzen over vlakke meetkunde, ruimtemeetkunde en elementaire getaltheorie. Euclides’ systematische aanpak maakten zijn Elementen tot een bijzonder invloedrijk werk, zowel op wiskundig als op algemener wetenschappelijk vlak. De bedoeling van Euclides was de gekende meetkunde volledig te funderen op vijf axioma’s of postulaten, om van daaruit de rest van de meetkunde op te bouwen. Deze vijf axioma’s— naar moderne maatstaven weliswaar verre van voldoende rigoreus—luidden als volgt. . Elke twee punten kunnen worden verbonden met e´e´n en juist e´e´n lijnstuk. . Elk lijnstuk kan in beide richtingen arbitrair ver worden verlengd in een rechte. . Er bestaat juist e´e´n cirkel met een gegeven straal en een gegeven middelpunt. . Alle rechte hoeken zijn congruent (d.i. op elkaar af te beelden via translaties en rotaties). . Als een rechte twee rechten zodanig snijdt dat de twee binnenhoeken aan eenzelfde kant samen kleiner zijn dan twee rechte hoeken, dan moeten deze twee rechten elkaar snijden aan deze kant (mits voldoende verlengd). Het laatste axioma, het parallellenpostulaat, klinkt beduidend ingewikkelder dan de overige. Ook Euclides trachtte om het gebruik van het vijfde postulaat zo lang mogelijk uit te stellen en bewees de eerste  proposities in zijn Elementen erzonder. Veel onderzoekers koesterden sindsdien de hoop dat het parallellelpostulaat af te leiden zou kunnen zijn uit de eerste vier, en deze dus in feite overbodig zou zijn. Net als voor de cirkelkwadratuur (zie curiosum ??) zijn doorheen de geschiedenis ontzettend veel vruchteloze pogingen ondernomen geweest, met “bewijzen” die nergens op sloegen of in het beste geval impliciet steunden op aannames evenwaardig met het parallellenpostulaat. Een sluitend bewijs werd nooit ontdekt, maar wel een hele lijst equivalente eigenschappen. Wellicht de bekendste is het axioma van Playfair. . Door elk gegeven punt p niet op een gegeven rechte ℓ gaat er e´e´n en juist e´e´n rechte die deze oorspronkelijke rechte ℓ niet snijdt. Een heel aantal van de pogingen steunde op reductio ad absurdum: door te vertrekken vanuit de negatie van het parallellenpostulaat hoopte men een strijdigheid te vinden. Pas doorheen de de eeuw groeide het besef dat ook deze negatie (samen met de eerste vier axioma’s) tot een volledig autonome en consistente vorm van meetkunde leidt! Onafhankelijk onderzoek van de Russische wiskundige Nikolai Lobachevsky in  en de Hongaarse wiskundige J´anos Bolyai in  legde de basis voor de theorie der niet-Euclidische meetkunde. Carl Friedrich



Gauss maakte eerder ook al observaties maar achtte deze te onafgewerkt en onconventioneel voor publicatie. In de meetkunde van Bolyai en Lobachevsky, ook hyperbolische meetkunde genoemd, wordt het parallellenpostulaat vervangen door de volgende variant op het axioma van Playfair. ′. Door elk gegeven punt p niet op een gegeven rechte ℓ gaan er minstens twee rechten die deze oorspronkelijke rechte ℓ niet snijden. Een eerste concretere fundering van de nieuwe meetkunde werd eigenlijk pas gelegd in , toen Eugenio Beltrami enkele modellen beschreef waarmee hij kon aantonen dat de hyperbolische meetkunde even consistent is als de Euclidische meetkunde. Het meest eenvoudige model staat tegenwoordig bekend onder de naam van Beltrami–Klein. De “punten” worden hier voorgesteld door punten binnen een (Euclidische) eenheidsschijf, waarvan de rand punten op oneindig voorstelt. De “rechten” zijn de koorden van deze cirkel. Men kan ook noties van hyperbolische afstanden en hoeken defini¨eren, maar dan blijkt dat het model niet hoekgetrouw is: hoe verder van het centrum van de schijf, hoe meer de hoeken vervormd lijken (ten opzichte van de Euclidische kijk op de zaak). Een variant van dit model—tegenwoordig bekend als het schijfmodel van Poincar´e—gebruikt dezelfde punten binnen de eenheidsschijf, maar werkt met alternatieve rechten. Een hyperbolische “rechte” is hier een diameter of een cirkelboog die de eenheidscirkel loodrecht snijdt. Dit model lijkt wat ingewikkelder, maar heeft het voordeel dat hoeken w´el bewaard blijven: hyperbolische hoeken zijn dezelfde als Euclidische hoeken.

Deze illustraties tonen een hyperbolische rechte ℓ en een punt p met een heel aantal rechten door p die ℓ niet snijden, in zowel het model van Beltrami–Klein als dat van Poincar´e. Er zijn twee speciale rechten die ℓ steeds dichter benaderen en die asymptotisch parallel aan ℓ heten. De andere rechten heten ultraparallel. Deze hebben steeds een uniek punt dat op minimale afstand van de rechte ℓ ligt en divergeren dan langs beide kanten ervan weg. Een eigenschap die in de hyperbolische meetkunde overeind blijft, is dat er steeds een unieke hyperbolische rechte bestaat die loodrecht staat op twee gegeven ultraparallelle rechten.



Een eenvoudige transformatie (de Cayleytransformatie) zet het schijfmodel van Poincar´e om naar het halfvlakmodel, waarin hyperbolische punten worden voorgesteld door Euclidische punten met strikt positieve y-co¨ordinaat. De “rechten” zijn hier de halfrechten en halfcirkels loodrecht op de x-as, die zelf de rol speelt van rechte op oneindig.

Nog een andere visualisatie is het hyperbolo¨ıdemodel, vaak vernoemd naar Hendrik Lorentz of Hermann Minkowski, dat gebruik maakt van e´e´n blad van de tweebladige hyperbolo¨ıde met vergelijking x 2 + y 2 − z 2 = −. Hyperbolische rechten zijn doorsnedes met vlakken door de oorsprong. Dit model wordt vaak gebruikt in de relativiteitstheorie daar de hyperbolo¨ıde op een natuurlijke manier ingebed zit in de Minkowski-ruimtetijd, waar heel wat concepten uit de hyperbolische meetkunde een natuurlijke fysische interpretatie krijgen. Orthogonale projectie van het hyperbolo¨ıdemodel leidt tot het model van David Gans ([]). Zo worden hyperbolische rechten voorgesteld door takken van hyperbolen met de oorsprong als centrum of door rechten door de oorsprong.



Deze vijf modellen zijn voorstellingen van dezelfde intrinsieke hyperbolische meetkunde, en zijn dan ook helemaal niet onderling ongerelateerd. In feite bestaan er zelfs best eenvoudige transformaties tussen. Deze worden het eenvoudigst beschreven door de halve eenheidssfeer met vergelijking x 2 + y 2 + z 2 =  en z >  als een soort intermediair model te zien. • De stereografische projectie vanuit het punt (, , −) op het vlak z =  geeft het schijfmodel van Poincar´e; • stereografische projectie vanuit het punt (, , −) op de hyperbolo¨ıde x 2 + y2 − z 2 = − geeft het hyperbolo¨ıdemodel; • stereografische projectie vanuit het punt (−, , ) op het vlak x =  geeft het halfvlakmodel van Poincar´e; • orthogonale projectie op het vlak z =  geeft het schijfmodel van Beltrami–Klein; • projectie vanuit het centrum van de sfeer op het vlak z =  geeft het Gansmodel. Deze transformaties zetten hyperbolische rechten in de modellen opnieuw om in rechten en bewaren metrische informatie zoals afstanden en hoeken. Halfvlakmodel (Poincar´e)

Hyperbolo¨ıde

Schijfmodel (Beltrami–Klein)

Gansmodel

Schijfmodel (Poincar´e)

(−, , )

(, , )

(, , )

(, , −) De tekening hierboven, een doorsnede van het xz-vlak, toont enkele onderlinge verbanden.



William Thurston stelde in [] een papieren speelgoedmodel voor. Daina Taimina zag tijdens een workshop in  zo’n fragiel papieren knutselwerk, en zij besloot om deze na te maken in een duurzamer haakwerk. Haar visualisaties werden bijzonder succesvol en Taimina schreef een toegankelijk boek [] over haken en hyperbolische meetkunde voor een breed publiek.

Welke eigenschappen gelden nu zoal in deze hyperbolische meetkunde? Het grootste verschil met de vertrouwdere meetkunde is dat er, in een zekere precieze zin, meer ruimte rondom hyperbolische punten zit dan rondom Euclidische. De visualisaties van Thurston en Taimina geven dit heel goed weer. Ietwat nauwkeuriger kan men zeggen dat een hyperbolische ruimte negatief gekromd is (zie curiosum ). Deze kromming zorgt bij hyperbolische driehoeken voor best opmerkelijke eigenschappen: zo is bijvoorbeeld de som van de hoeken niet langer constant, maar strikt kleiner dan ○. Een driehoek met drie onderling asymptotisch parallelle zijden en hoekpunten op oneindig heeft zelfs drie nulhoeken! Een verrassende eigenschap—die de hyperbolische meetkunde dan weer makkelijker maakt dan de Euclidische—is dat elke twee gelijkvormige driehoeken (met drie gelijke hoeken) ook meteen congruent zijn. Daarnaast kan men de oppervlakte van een driehoek heel eenvoudig uitdrukken in functie van de drie hoeken, in radialen: na een geschikte standaardisering van de kromming is deze oppervlakte namelijk precies gelijk aan π − α − β − γ. Nog een curiositeit is dat iedere hyperbolische driehoek steeds een ingeschreven cirkel heeft, maar niet noodzakelijk een omgeschreven cirkel. Het kan namelijk gebeuren dat twee zijden asymptotisch parallel zijn zodat er een hoekpunt op oneindig ligt, of dat de drie hoekpunten op een zogenaamde hypercykel of een horocykel liggen. Een hypercykel is een curve waarvan alle punten even ver liggen van dezelfde gegeven rechte. Een horocykel is een curve waarvan alle normaallijnen naar hetzelfde punt op oneindig convergeren. In het Euclidisch vlak zijn de beide objecten niet meer dan klassieke rechten, maar



in het hyperbolisch vlak zijn ze iets ingewikkelder: een hypercykel ziet er in het schijfmodel van Poincar´e uit als een cirkelboog of een koorde niet loodrecht op de eenheidscirkel (links), en een horocykel als een cirkel rakend aan de eenheidscirkel (rechts).

Elke rechte ℓ en punt p ∉ ℓ bepalen een unieke hypercykel. Indien we het punt p vasthouden en de rechte ℓ naar oneindig laten gaan, dan benaderen deze hypercykels een horocykel. Zoals de voorbeelden illustreren, wordt de studie van hyperbolische driehoeken best subtiel. Desalniettemin is men erin geslaagd om een hele theorie van hyperbolische goniometrie uit te bouwen, met analoga van de Euclidische formules. Een driehoek met hoekpunten A, B, C, en tegenoverliggende zijden a, b, c, voldoet bijvoorbeeld aan deze cosinusregel en zijn duale (opnieuw na standaardisering van de kromming): ̂ cosh c = cosh a ⋅ cosh b − sinh a ⋅ sinh b ⋅ cos C, { ̂ ̂ ̂ ̂ ̂ cos C = − cos A ⋅ cos B + sin A ⋅ sin B ⋅ cosh c. ̂ = ○ Een speciaal geval is de hyperbolische stelling van Pythagoras; voor een driehoek met C geldt dan gewoon dat cosh c = cosh a ⋅ cosh b. Er bestaat ook een hyperbolische sinusregel: sin β sin γ sin α = = . sinh a sinh b sinh c Hierbij zijn de hyperbolische sinus en cosinus (voor hoeken in radialen) gedefinieerd als sinh x = 21 ( exp(x) − exp(−x)),

cosh x = 21 ( exp(x) + exp(−x)),

Uit hun definitie volgt bijvoorbeeld meteen dat de sinus hyperbolicus een oneven functie is, en de cosinus hyperbolicus even. Ook kan eenvoudig de verdubbelingsformules narekenen, die een vertrouwde vorm aannemen: {



sinh(x + y) = sinh x ⋅ cosh y + cosh x ⋅ sinh y, cosh(x + y) = cosh x ⋅ cosh y + sinh x ⋅ sinh y.

Eigenlijk is er zelfs een universele vuistregel om goniometrische identiteiten te vertalen naar hyperbolische identiteiten, de regel van Osborn ([]): herschrijf alles tot enkel cosinussen en sinussen, vervang die door hun hyperbolische tegenhangers, en keer tot slot voor elke twee hyperbolische sinussen in een term het teken om. Het verwantschap tussen de klassieke en hyperbolische goniometrische functies is niet zomaar toevallig: over de complexe getallen legt de formule exp(ix) = cos x + i sin x van Euler direct een verband. Zo blijkt bijvoorbeeld in de complexe uitbreiding dat sinh x = −i sin(ix),

cosh x = cos(ix),

sinh(ix) = i sin x,

cosh(ix) = cos(x).

Naast toepassingen in bijvoorbeeld relativiteitstheorie komt hyperbolische meetkunde ook aan bod in artistieke contexten. Enkele beroemde werken van de kunstenaar Maurits Escher zijn immers ontsproten uit een briefwisseling met de meetkundige Harold Coxeter: de reeks van vier houtgravures die bekendstaan onder de naam Cirkellimiet. Ieder van deze gravures toont in feite een betegeling van het hyperbolisch vlak, gevisualiseerd in het schijfmodel van Poincar´e. Cirkellimiet II gebruikt bijvoorbeeld kruisvormige betegelende figuren, waarvan de assen bestaan uit segmenten van hyperbolische rechten en de randen uit hypercykels.



[1] J. Cannon, W. Floyd, R. Kenyon, W. Parry, Hyperbolic geometry. Flavors of Geometry, MSRI Publications, vol. 31, 1997, p. 59–115. [2] L. Corry, The influence of David Hilbert and Hermann Minkowski on Einstein’s views over the interrelation between physics and mathematics. Endeavour, vol. 22, no. 3, 1998, p. 95–97. [3] D. Gans, A new model of the hyperbolic plane. The American Mathematical Monthly, vol. 73, no. 3, 1966, p. 291–295. [4] D. Henderson, D. Taimina, Crocheting the hyperbolic plane. Mathematical Intelligencer, vol. 23, no. 2, 2001, p. 17–28. [5] G. Osborn, Mnemonic for hyperbolic formulae. The Mathematical Gazette, vol. 2, no. 34, 1902, p. 189. [6] D. Schattschneider, The mathematical side of M. C. Escher. Notices of the American Mathematical society, vol. 57, no. 6, 2010, p. 706–718. [7] D. Taimina, Crocheting adventures with hyperbolic planes. A.K. Peters, 2009. [8] W. Thurston, Three-dimensional geometry and topology (vol. ). Princeton University Press, 1997. [9] H. Wolfe, Introduction to non-Euclidean geometry. Mill Press, 2008.



32

Schoenveterformule

Er is een handige wijze om de oppervlakte van een veelhoek te vinden, hoe ingewikkeld ook, als enkel de co¨ordinaten van diens hoekpunten gekend zijn. Deze formule werd beschreven door Albrecht Meister in  ([]) en wordt ook aan Carl Friedrich Gauss toegekend. Stelling. Zij (x1 , y1 ), (x2 , y2 ), . . . , (x n , y n ) de co¨ordinaten van de hoekpunten van een n-hoek in het vlak, in tegenwijzerzin overlopen. De oppervlakte van deze veelhoek is dan precies  ⋅ ((x1 y2 + x2 y3 + ⋯ + x n−1 y n + x n y1 ) − (x1 y n + x2 y1 + ⋯ + x n−1 y n−2 + x n y n−1 )).  Schrijf voor een grafische weergave van deze formule de co¨ordinaten in twee rijen, en verbind de paren getallen die dienen te worden vermenigvuldigd. Het resultaat heeft wel wat weg van een schoenveterpatroon. x1

x2

x3

y1

y2

y3

⋯

xn

x1

yn

y1

Merk op dat de formule ook geschreven kan worden als een halve som van determinanten  x x x x x x x x ⋅ (∣ 1 2 ∣ + ∣ 2 3 ∣ + ⋯ + ∣ n−1 n ∣ + ∣ n 1 ∣) . y n y1 y y y y y y  n−1 n 2 3 1 2 Bewijs. We bewijzen dit via inductie op n en starten met de inductiebasis n = . Zij (x1 , y1 ), (x2 , y2 ) en (x3 , y3 ) de drie hoekpunten. Na een translatie van het eerste punt naar de oorsprong (waarbij de oppervlakte uiteraard niet wijzigt) worden de nieuwe co¨ordinaten (, ), (x2 − x1 , y2 − y1 ) en (x3 − x1 , y3 − y1 ). Men kan de oppervlakte van deze driehoek op verschillende manieren bepalen; laat ons hier gebruikmaken van het kruisproduct in R3 . Beschouw in R3 de vectoren u = (x2 − x1 , y2 − y1 , ) en v = (x3 − x1 , y3 − y1 , ). Per definitie van het kruisproduct is de norm van u × v gelijk aan de oppervlakte van het parallellogram opgespannen door u en v, en de gezochte oppervlakte van de driehoek dus   ⋅ ∥u × v∥ = ⋅ ∥(, , (x2 − x1 ) ⋅ (y3 − y1 ) − (y2 − y1 ) ⋅ (x3 − x1 ))∥,   wat precies vereenvoudigt tot de gezochte formule  ⋅ ((x1 y2 + x2 y3 + x3 y1 ) − (x1 y3 + x2 y1 + x3 y2 )). 



Onderstel de formule bewezen voor n-hoeken en beschouw een veelhoek met n +  punten. Verwijder het laatste hoekpunt (x n+1 , y n+1 ), pas de schoenveterformule toe op deze n-hoek, en tel daar de oppervlakte van de driehoek met hoekpunten (x n , y n ), (x n+1 , y n+1 ) en (x1 , y1 ) bij op. Het resultaat is  ⋅ ((x1 y2 + x2 y3 + ⋯ + x n y1 ) − (x1 y n + x2 y1 + ⋯ + x n y n−1 ))   + ⋅ ((x n y n+1 + x n+1 y1 + x1 y n ) − (x n y1 + x n+1 y n + x1 y n+1 )),  wat inderdaad vereenvoudigt tot de gewenste formule voor een (n + )-hoek.

∎

De schoenveterformule kan worden opgevat als een speciaal geval van de stelling van Green, die een verband uitdrukt tussen lijnintegralen over een kromme en dubbelintegralen over de oppervlakte die deze kromme begrenst. Onder bepaalde voorwaarden op de twee functies f en g (in twee variabelen) en het gebied D beweert de stelling van Green dat ∂g ∂ f ∮∂D ( f (x, y) dx + g(x, y) dy) = ∬D ( ∂x − ∂y ) dx dy. Toegepast met D een veelhoekig gebied, g(x, y) = x/ en f (x, y) = −y/, leert dit verband dat de oppervlakte van D wordt gegeven door de lijnintegraal  (x dy − y dx)  ∮∂D langs de rand van D. Men kan vervolgens de schoenveterformule op een alternatieve manier afleiden uit de stelling van Green door deze lijnintegraal op te splitsen over de zijden van D, en deze lijnstukken correct te parametriseren.

[1] B. Braden, The surveyor’s area formula. College Mathematics Journal, vol. 17, no. 4, 1986, p. 326–337. [2] A. Meister, Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus. Novi Commentarii Societatis Reglae Scientiarum Gottingensis, vol. 1, 1769, p. 144–180.



33

Haberdasherpuzzel

Henry Dudeney was een Britse puzzelontwerper met een uitgesproken voorliefde voor wiskundige en logische puzzels en spelletjes. Tot zijn grootste vondsten behoort de zogenaamde Haberdasherpuzzel, die hij eerst publiceerde in de Weekly Dispatch in  en daarna in zijn magnum opus The Canterbury Puzzles ([]) in . De opgave van de Haberdasherpuzzel is best eenvoudig: verknip een gelijkzijdige driehoek in vier stukken en herschik die tot een perfect vierkant. In de woorden van Dudeney zelf, the curious point of the puzzle is that I have found that the feat may really be performed in so few as four pieces, and without turning over any piece when placing them together. The method of doing this is subtle, but I think the reader will find the problem a most interesting one. De oplossing is verre van vanzelfsprekend en voldoet aan een mooie bijkomstige eigenschap: de vier puzzelstukken van de dissectie kunnen aan elkaar gescharnierd worden, zodanig dat ze de ene kant op draaien resulteert in de driehoek, en de andere kant in het vierkant!

Een passer-en-liniaalconstructie vinden is haast een puzzel op zich! . Start met een gelijkzijdige driehoek ABC. . Construeer het middelpunt D van zijde [AC] en het middelpunt E van zijde [BC]. . Verleng [AE] en pas F af zodat ∣CE∣ = ∣EF∣. . Construeer de halfcirkel met [AF] als diameter. . Verleng [BC] en noem het snijpunt met de zonet geconstrueerde cirkelboog, G. . Construeer de cirkel met centrum E en straal ∣EG∣; noem het snijpunt met [AB], H. . Meet I af op zijde [AB] zodat ∣HI∣ = ∣AD∣. . Verbind E met H en construeer vanuit D en I de loodrechten op EH.



G C F

D

A

H

E

I

B

De exacte verhouding tussen de drie lijnsegmenten in de onderste zijde blijkt √ √ √ √ ∣AH∣ ∶ ∣HI∣ ∶ ∣IB∣ =  −   −  ∶  ∶   −  − . In [] toonden de auteurs aan dat de Haberdasherdissectie in zekere zin niet zo bijzonder is: voor elke twee veelhoeken met een gelijke oppervlakte bestaat er een gescharnierde dissectie zoals deze van Dudeney, die in de twee richtingen tot de twee gewenste veelhoeken roteert. Met slechts vier stukken blijft de constructie van Dudeney echter nog steeds een van de meest elegante dissecties in zijn soort.

[1] T. Abbott, Z. Abel, D. Charlton, E. Demaine, M. Demaine, S. Kominers, Hinged dissections exist. Discrete & Computational Geometry, vol. 47, no. 1, 2012, p. 150–186. [2] H. Dudeney, The Canterbury puzzles and other curious problems. 1907. [3] G. Frederickson, Hinged dissections: swinging and twisting. Cambridge University Press, 2002.



34

Voderbergbetegelingen

In  formuleerde Karl Reinhardt het vermoeden dat twee congruente (noodzakelijkerwijs niet-convexe) veelhoeken nooit op zodanige manier aan elkaar gelegd kunnen worden dat er een gat tussen zit dat opgevuld kan worden met congruente kopie¨en van dezelfde veelhoek. Klinkt misschien aannemelijk, maar het antwoord is desalniettemin negatief: twee jaar later ontdekte Heinz Voderberg een tegenvoorbeeld, met negen zijden. Q2 Q1

P1

P2 Q3

Q4

R P4 P3 Om te voldoen aan de opgave van Reinhardt, moet hier voor de zijdelengtes van de veelhoek van Voderberg gelden dat ∣RP1 ∣ = ∣P1 P2 ∣ = ∣P3 P4 ∣ = ∣RQ1 ∣ = ∣Q1 Q2 ∣ = ∣Q3 Q4 ∣ = ∣P4 Q4 ∣,

∣P2 P3 ∣ = ∣Q2 Q3 ∣,

en voor de hoeken dat ∡RQ1 Q2 = ∡Q4 P4 P3 = ∡P2 P1 R,

∡Q1 Q2 Q3 = ∡Q2 Q3 P4 = ∡P3 P2 P1 = ∡P4 P3 P2 .

Met deze relaties is de negenhoek nog niet eenduidig bepaald, maar omdat de figuur zichzelf niet mag snijden is er desondanks niet zo heel veel keuzevrijheid. In de afgebeelde veelhoek bedraagt ∡P1 RQ1 = ○ . Inderdaad, we kunnen twee zo’n Voderbergtegels nu z´o aan elkaar leggen dat er net een derde tussenin past. Het is zelfs mogelijk om er twee tegels ineens in te puzzelen.

Zoals hieronder ge¨ıllustreerd kunnen deze veelhoeken in stroken aaneengesloten worden om het vlak te betegelen, weliswaar op een nogal saaie manier. ⋯

⋯



De tegels van Voderberg passen echter ook ineen in de spectaculaire spiraalvorm hieronder! Een lichte wijziging aan dit patroon geeft een variant met vier armen; op gelijkaardige wijze zijn spiralen met eender welk even aantal armen mogelijk.



De twee armen in de originele spiraal worden opgebouwd uit halve cirkels van twaalf clusters van tegels. De centrale halve omwenteling bestaat uit twaalf losse tegels, in dezelfde ori¨entatie. In de volgende halve omwenteling volgen twaalf clusters van telkens drie tegels, alternerend in ori¨entatie. Daarna volgens telkens vijf tegels, daarna zeven, negen, enzoverder. Merk op dat de grootte van de smalle hoek ∡P1 RQ1 hier wel van belang is, aangezien  ⋅ ○ = ○ .

Het feit dat deze tegels in een spiraalvorm (die Voderberg in zijn originele artikel al weergaf) ineenpassen, is geen essentieel gevolg van de eigenschap een derde tegel te kunnen omsluiten met twee andere. Michael Goldberg zag in  dat zo’n spiralen ook uit algemenere radiale betegelingen ontstaan, door deze op een geschikte manier in twee helften te verdelen en die wat op te schuiven.

Deze methode van Goldberg ([]) genereert wegens symmetrieoverwegingen steeds spiralen met een even aantal armen; in recenter werk publiceerden Daniel Stock en Brian Wichmann ook een aangepaste constructie voor een oneven aantal armen ([]), mits geschikte tegels.



[1] M. Goldberg, Central tessellations. Scripta Mathematica, vol. 21, 1955, p. 253–260. [2] D. Stock, B. Wichmann, Odd spiral tilings. Mathematics Magazine, vol. 73, no. 5, 2000, p. 339–346. [3] H. Voderberg, Zur Zerlegung der Umgebung eines ebenen Bereiches in kongruente. Jahresbericht der Deutschen Mathematiker-Vereinigung, vol. 46, 1936, p. 229–231.



35

G¨omb¨ocs

Iedereen kent wel de speelgoedjes die steeds uit zichzelf terug rechtop rollen, ongeacht vanuit welke positie. Zo’n tuimelaars zijn eenvoudig te construeren door hun bolvormige onderkant te verzwaren of de binnenkant uit te hollen.

Beide constructiemethodes leiden weliswaar tot een object met juist e´e´n stabiel evenwichtspunt en e´e´n instabiel evenwichtspunt, maar voelen toch aan als valsspelen. Vladimir Arnold stelde in  de vraag of er ook een eerlijke wiskundige tuimelaar bestaat—een homogeen en convex lichaam met slechts twee equilibria, dus zonder gaten of verzwaarde elementen. Het was in die tijd al langer gekend dat in een dimensie lager iedere vlakke kromme evenveel stabiele als onstabiele evenwichtspunten heeft, en minstens twee van elke soort. Toentertijd was de gangbare overtuiging dat in drie dimensies een gelijkaardige ondergrens zou gelden, ook al wordt het probleem daar veel subtieler door het bestaan van zadelpunten. Arnold zelf was niet zo overtuigd. Op het International Congress on Industrial and Applied Mathematics te Hamburg, , ontmoette hij G´abor Domokos en discussieerden ze kort over het bestaan van zo’n lichaam van minimale stabiliteit, met e´e´n stabiel en e´e´n instabiel equilibrium. Dit betekende voor Domokos de start van een jarenlange jacht op dit mysterieuze object. Zo bestudeerde hij samen met zijn vrouw tijdens een vakantie naar het Griekse Rodos de vorm van  kiezelstenen. Geen enkele steen bleek aan de gedroomde eigenschappen te voldoen, maar Domokos kwam er wel tot een cruciaal besef: het gezochte object kan niet te “plat” zijn (of er bestaan minstens twee stabiele equilibria, e´e´n aan iedere kant), maar ook niet te “dun” (of er bestaan minstens twee instabiele equilibria, e´e´n aan ieder uiteinde). In collaboratie met P´eter V`arkonyi maakte Domokos deze intu¨ıtie wiskundig rigoureus door twee karakteristieke re¨ele parameters te defini¨eren: een flatness ρ F ⩾  en een thinness ρ T ⩾ . De auteurs bewijzen in hun artikel [] dat een lichaam juist e´e´n stabiel evenwichtspunt heeft als en slechts als ρ F = . Analoog bepaalt de duale parameter ρ T het aantal instabiele punten. De definities zijn vrij onpraktisch om concreet uit te rekenen voor generieke lichamen zoals kiezelstenen, maar bleken wel een belangrijk theoretisch hulpmiddel. In termen van flatness en thinness is een lichaam met ρ F = ρ T =  het meest bolvormige lichaam, en daarvan stamt de naam g¨omb¨oc af—een Hongaars woord dat zoveel betekent als “bolletje”. De existentie van een waarachtige g¨omb¨oc werd pas in  aangetoond, via een analytische formule met twee parameters die een hele familie van gladde lichamen oplevert. Domokos



en V`arkonyi bewezen in [] dat inderdaad ρ F = ρ T =  voor goedgekozen parameterwaarden, aldus het vermoeden van Arnold theoretisch bevestigend. De convexiteitseis legt echter zo’n strenge voorwaarden op de parameters op dat de uiteindelijke vorm niet te onderscheiden is van een perfecte bol. Later konden de onderzoekers ook een praktische (visueel herkenbare en fysiek controleerbare) g¨omb¨oc defini¨eren door ook randen toe te laten, en bekwamen ze een figuur met de volgende karakteristieke vorm.

Ook deze versie is extreem foutgevoelig: zelfs een minieme afwijking kan de waarden van ρ F en ρ T al be¨ınvloeden en extra evenwichtspunten doen ontstaan. Een nauwkeurige g¨omb¨oc zal echter vanuit eender welke positie naar dezelfde ori¨entatie terugrollen. Domokos en V`arkonyi observeerden later dat bepaalde schildpadden, zoals de Indische sterschildpad (Geochelone elegans), een schild hebben met een gelijkaardige vorm. Uiteraard zijn schildpadden verre van homogeen en convex, maar deze vorm maakt het voor het dier nog steeds mogelijk om zonder veel moeite terug rechtop te geraken, in tegenstelling tot soorten met een platter schild. Hun bevindingen werden gerapporteerd in [].

Winnaars van de Stephen Smale Prize, driejaarlijks uitgereikt ter erkenning van doorbraken in de interactie tussen zuivere wiskunde, toegepaste wiskunde en computerwetenschappen, ontvangen een gegraveerde g¨omb¨oc als trofee. We eindigen met een argumentering waarom tweedimensionale g¨omb¨ocs niet bestaan. Stelling. Een convexe en homogene tweedimensionale vorm heeft minstens twee stabiele en twee instabiele equilibria.



Bewijs. [] G

∎

[1] M. Freiberger, The story of the G¨omb¨oc. Plus, https://plus.maths.org/content/story-goumlmboumlc, 2009. [2] G. Domokos, P. V`arkonyi, Static equilibria of rigid bodies: dice, pebbles and the Poincar´e–Hopf theorem. Journal of Nonlinear Science, vol. 16, no. 3, 2006, p. 255–281. [3] G. Domokos, P. V`arkonyi, Mono-monostatic bodies: the answer to Arnold’s question. The Mathematical Intelligencer, vol. 28, no. 4, 2006, p. 34–38. [4] G. Domokos, P. V`arkonyi, Geometry and self-righting of turtles. Proceedings of the Royal Society B, vol. 275, 2008, p. 11–17. [5] Robert Osserman, The four-or-more vertex theorem. American Mathematical Monthly, vol. 92, no. 5, 1985, p. 332–337.



36

Cirkel van Conway

Nog een schattige vondst van John Conway. Stelling. Verleng iedere zijde van een willekeurige driehoek aan beide kanten met een lengte gelijk aan de tegenoverliggende zijde. De zes verkregen punten liggen steeds op een cirkel, waarvan het centrum bovendien samenvalt met dat van de ingeschreven cirkel.

b a

c

b a

a

c

b c

Bewijs. Observeer dat de constructie tot drie gelijkbenige driehoeken leidt:

Voor elke cirkel door twee punten ligt het centrum op de middelloodlijn tussen deze punten. Deze lijnen zijn precies de bissectrices van de tophoeken van de drie gelijkbenige driehoeken. Het enige punt dat dus middelpunt kan zijn van een cirkel door de zes geconstrueerde punten, is het middelpunt van de ingeschreven cirkel. Het feit dat de zes punten allen effectief even ver liggen van dit centrale punt valt eenvoudig



in te zien: gebruik de congruentiekenmerken zijde–hoek–zijde om te besluiten dat de paren aangeduide lengtes in beide onderstaande figuren (en in de analoge gevallen) gelijk zijn.

De zes punten liggen dus op gelijke afstand van het centrum van de ingeschreven cirkel. ∎ Men kan aantonen dat de straal van de cirkel van Conway gegeven wordt door √ a2 b + a 2 c + b2 c + abc + ab2 + ac 2 + bc 2 . a+b+c

[1] D. Grinberg, E. Weisstein, Conway circle. http://mathworld.wolfram.com/ConwayCircle.html.



37

Mirakel van Morley

In  ontdekte Frank Morley dit wonderbaarlijke resultaat uit de Euclidische meetkunde, zo verrassend dat deze sindsdien tot de wiskundige folklore behoort als Morley’s miracle. Stelling. Vertrek van een willekeurige driehoek en deel diens hoeken in drie. De snijpunten van de aanliggende trisectrices bepalen steeds een gelijkzijdige driehoek, ongeacht de vorm van de originele driehoek.

Morleys jongste zoon schetst een levendig portret in het manuscript [], over de geschiedenis van dit juweel: “I was a schoolboy when my father, who was almost 40 years older than I was, sketched for me, free-hand, a pencilled diagram of the simplest form of the above-discussed theorem in plane geometry. I tested it at once with my own drawing instruments. No matter what the shape of the original triangle I started with, there in its midriff was an equilateral triangle, picked out by the trisectors. It was wizard, it was weird—and it was true!” Het mirakel van Morley is ook befaamd als een stelling die zeer eenvoudig te beschrijven valt, maar zeer moeilijk te bewijzen. Morley stuitte op zijn vondst in een studie van meetkundige plaatsen bepaald door cardio¨ıden, maar heeft deze nooit afzonderlijk gepubliceerd of rechtstreeks geverifieerd. De eerste op zich staande bewijzen steunden op delicate goniometrische manipulaties, die leren dat een zijdelengte van het centrale driehoekje gegeven wordt door de symmetrische uitdrukking r sin α sin β sin γ, waarin α, β en γ de hoekgroottes van de originele driehoek voorstellen, en r de straal van de omgeschreven cirkel. Het afleiden van deze formule blijkt echter een klein titanenwerk. Later zijn er volledig elementaire bewijzen gevonden, die weliswaar omgekeerd te werk gaan; het bewijs verderop is de eerste van deze soort, afkomstig van John Conway.



Wat de stelling extra bijzonder maakt, is dat er geen voor de hand liggende veralgemeningen naar willekeurige veelhoeken of hogere dimensies lijken te bestaan. Er is wel een uitbreiding te vinden door ook de trisectrices van de buitenhoeken erbij te betrekken; zo vinden we vier extra gelijkzijdige driehoeken, met zijden evenwijdig aan de centrale driehoek van Morley.

We geven nu het beloofde achterwaartse bewijs voor de stelling van Morley. Bewijs. Veronderstel dat de driehoek hoekgroottes α, β en γ heeft, zodat α + β + γ = π/ (in radialen). De bedoeling van dit bewijs is te vertrekken vanuit een gelijkzijdige driehoek, en er zes driehoeken rond te construeren die samen precies de originele driehoek vormen. De notatie van Conway volgend, schrijven we x ∗ voor de hoek x + π/. Start met een gelijkzijdige driehoek met zijden van eenheidslengte, en definieer driehoeken met de volgende hoeken (merk op dat deze inderdaad in de zes gevallen sommeren tot π): {α ∗ , β ∗ , γ}, {α ∗∗ , β, γ},

{α ∗ , β, γ∗ }, {α, β∗∗ , γ},

{α, β ∗ , γ ∗ }, {α, β, γ∗∗ }.

We hebben met deze voorschriften enkel de vorm van de driehoeken vastgelegd, en nog niet de precieze afmetingen, maar uiteindelijk zullen de zeven puzzelstukken net in elkaar passen



als volgt: α

α

α

∗ β∗ γ

β ∗∗

γ∗∗ α∗ α

∗

β

γ

β∗

γ∗

γ

α ∗∗

β β

γ

Merk op dat de hoeken rond elk van de drie inwendige toppen alvast sommeren tot π. Voor de eerste driehoeken liggen de precieze afmetingen voor de hand: herschaal {α ∗ , β ∗ , γ} tot de zijde tussen de hoeken α ∗ en β∗ eenheidslengte heeft. De andere drie zijn iets lastiger: construeer voor {α ∗∗ , β, γ} vanuit hoekpunt α ∗∗ twee lijnen die de tegenoverliggende zijde onder een hoek α ∗ snijden, zodat daar een gelijkbenige driehoek ontstaat, en herschaal tot deze twee lijnstukken van eenheidslengte zijn. Analoog voor de andere driehoeken. Als de hoek α stomp is, zijn de twee hoeken α ∗ buitenhoeken van de gevormde gelijkbenige driehoek in plaats van binnenhoeken, zonder dat dit de geldigheid van het bewijs schaadt. Beschouw nu in onderstaande figuur de aangeduide driehoeken. Wegens de constructie zijn deze congruent; ze hebben immers identieke hoeken en e´e´n identieke overeenkomstige zijde. Dit betekent dat ook hun gemeenschappelijke zijden even groot zijn. Herhalen we dit overal, dan zien we dat de zeven puzzelstukken inderdaad precies aaneensluiten.

Deze grote driehoek heeft hoeken van α, β en γ en is aldus gelijkvormig aan de originele. Bovendien volgt uit de constructie meteen dat die voldoet aan de stelling van Morley. ∎



We voorzien tot slot—voor de sport—nog een meer rechttoe-rechtaan, goniometrisch bewijs van de hand van Leon Bankoff, met dezelfde notaties als in het bewijs van Conway. Bewijs. We onderstellen opnieuw dat de hoeken van de originele driehoek α, β en γ zijn. Dan zijn ∡BPC = α ∗∗ , ∡AQC = β ∗∗ en ∡ARB = γ∗∗ , met hoekpunten zoals op de figuur. A

Q R P B

C

We gaan allereerst na dat voor willekeurige hoeken de formule sin x =  sin x sin x ∗ sin x ∗∗ geldt, steunend op enkele klassieke goniometrische identiteiten zoals de somformules voor sinus en cosinus; sin x = sin x cos x + cos x sin x = ( sin x cos x) cos x + (cos2 x − sin2 x) sin x =  sin x( − sin2 x) + ( −  sin2 x) sin x =  sin x −  sin3 x, zodat verder, na ontbinding in factoren, √ =  sin x [( /)2 − sin2 x] =  sin x [sin π/ + sin x][sin π/ − sin x] = − sin x [ sin 21 (x + π/) cos 21 (x − π/)][ sin 21 (x − π/) cos 21 (x + π/)] = − sin x sin (x + π/) sin (x − π/) =  sin x sin x ∗ sin x ∗∗ . De sinusregel, toegepast in ∆ AQC en ∆ ABC, leert dat ∣AQ∣ ∣AC∣ = sin γ sin β ∗∗

en

∣AC∣ = r, sin β

met r de straal van de omgeschreven cirkel van ∆ ABC. Samen geeft dit sin β ∗∗ ∣AQ∣ = r sin γ sin β, en dankzij voorgaand goniometrisch rekenwerk kunnen we dit herschrijven tot ∣AQ∣ = r sin γ sin β sin β ∗ .



Op dezelfde manier is ∣AR∣ = r sin β sin γ sin γ ∗ , zodat samen met de sinusregel sin γ∗ sin γ ∗ ∣AR∣ sin(∡AQR) sin(∡AQR) = = = . ∗ ∗ = sin(π − α − γ ) sin β ∣AQ∣ sin(∡ARQ) sin(π − α − ∡AQR) Een eenvoudig functieonderzoek wijst uit dat de functie sin x/ sin(π − α − x) strikt stijgend is over het gebied  < x < π − α. Aangezien zowel γ ∗ als ∡AQR begrensd worden door π − α, betekent dit dat ∡AQR = γ ∗ en ∡ARQ = β∗ . Analoog voor de overige hoeken. Hieruit volgt finaal dat ∡PQR = ∡QRP = ∡RPQ = π/, of alternatief, door nog eenmaal de sinusregel toe te passen, dat sin α ∣AQ∣ = r sin α sin β sin γ. ∣QR∣ = sin β ∗ Hoe dan ook blijkt ∆ PQR inderdaad gelijkzijdig.

∎

Op de website [] zijn nog meer bewijzen met gevarieerde ingredi¨enten verzameld.

[1] A. Bogomolny, Morley’s miracle. http://www.cut-the-knot.org/triangle/Morley. [2] J. Conway, On Morley’s trisector theorem. The Mathematical Intelligencer, vol. 36, no. 3, 2014, p. 3. [3] C. Oakley, J. Baker, The Morley trisector theorem. The American Mathematical Monthly, vol. 85, no. 9, 1978, p. 737–745.



38

Stelling van Erd˝os–Anning

Een onderhoudend resultaat van problem-solvers Paul Erd˝os en Norman Anning: Stelling (Erd˝os–Anning). Als de onderlinge afstanden van oneindig veel punten in het vlak allen gehele getallen zijn, dan liggen al deze punten op een enkele rechte. Bewijs. Zij A, B en C drie niet-collineaire punten op gehele afstanden, en zij δ = max{d(A, B), d(B, C), d(A, C)}. We zullen aantonen dat een geldige configuratie die A, B en C bevat, uit hoogstens (δ + )2 punten kan bestaan. Voor elk punt X in zo’n configuratie geeft de driehoeksongelijkheid dat  ⩽ ∣d(A, X) − d(B, X)∣ ⩽ δ, en bovendien is dit per assumptie een geheel getal. Voor elk van de δ +  mogelijke waarden k is de meetkundige plaats van de punten X waarvoor ∣d(A, X) − d(B, X)∣ = k een hyperbool met brandpunten A en B; elk punt uit de configuratie ligt op een van deze δ +  hyperbolen. Volledig analoog ligt elke X ook op een van δ+ hyperbolen met brandpunten B en C. Omdat elk paar hyperbolen in hoogstens vier punten snijdt, behoren er hoogstens (δ + )2 punten tot de configuratie (A, B en C inbegrepen). ∎ Erd˝os en Anning bewezen dit in  ([]). Ze gaven tevens een constructie van oneindig veel niet-collineaire punten op uitsluitend rationale afstanden, zodat er ook configuraties bestaan met willekeurig veel punten op gehele afstanden (na een geschikte herschaling). Alle punten in hun constructie liggen op de eenheidscirkel; een nog open probleem van Erd˝os en Ulam vraagt of er een verzameling punten bestaat op rationale afstanden die dicht is in het vlak. Deze stelling motiveert de definitie van een Erd˝os–Diophantische configuratie: een maximale verzameling roosterpunten op onderling gehele afstanden. De volgende bladzijde toont een aantal voorbeelden; geen enkel roosterpunt kan worden toegevoegd zonder een niet-gehele afstand te introduceren. Verrassend minder evident om te vinden zijn Erd˝os–Diophantische configuraties met exact drie punten. In [] berichten de auteurs dat er maar zeven zo’n driehoeken met gehele lengtes begrensd door  te vinden zijn; de allerkleinste heeft zijdelengtes ,  en .



(, )

(−, )

(, )

(, )

(, −)

(, ) (, )

(, )

(, )

(, )

(, )

[1] N. Anning, P. Erd˝os, Integral distances. Bulletin of the American Mathematical Society, vol. 51, 1945, p. 598–600. [2] A. Kohnert, S. Kurz, A note on Erd˝os–Diophantine graphs and diophantine carpets. Mathematica Balkanica, vol. 21, no. 1–2, 2007, p. 1–5.



39

Kaartprojecties

Cartografie is de millennia-oude studie van het aanschouwelijk maken van ruimtelijke data, die zowel fysiek kan zijn (denk aan bijvoorbeeld landmassa’s) of abstract (bijvoorbeeld landgrenzen). Er zijn vele factoren die deze studie bemoeilijken. Om te beginnen wordt de aarde vaak voorgesteld als een bol, terwijl onze planeet door diens rotatie eigenlijk licht afgeplat is tot de vorm van een sfero¨ıde, op grote schaal. Daarnaast zorgt het feit dat de landmassa niet uniform verdeeld is ook tot gravitationele effecten op kleinere schaal; de zogenaamde geo¨ıde is een oneffen maar realistischer model dat deze in rekening brengt. Echter, zelfs los van de precieze vorm van de aarde is het probleem voor een ge¨ıdealiseerde bol nog steeds helemaal niet eenvoudig. Er zijn vele praktische argumenten waarom een vlakke voorstelling op een kaart handiger is dan een globe. Daarvoor heeft men een wiskundige transformatie nodig van de co¨ordinaten op een boloppervlak naar vlakke co¨ordinaten. Idealiter zou zo’n projectie ook meetkundige eigenschappen moeten bewaren zoals de vorm en oppervlakte van regio’s op de bol, hoeken tussen rechten, afstanden tussen punten. . . Een transformatie die al deze meetkundige data bewaart, wordt een isometrie genoemd. Een conceptueel eenvoudige transformatie is de orthografische projectie, waarbij een hemisfeer loodrecht geprojecteerd wordt op een raakvlak aan de bol. Deze projectie geeft weer hoe de aarde eruitziet vanuit de ruimte.

De grijze markeringen op deze afbeelding zijn eigenlijk fictieve cirkels op het aardoppervlak met een uniforme straal (van  kilometer), die helpen visualiseren in welke mate de kaart



een vertekend beeld geeft. Voor de orthografische projectie worden de cirkels steeds smaller naar de rand toe, zodat noch de vorm, noch de afstand, noch de oppervlakte bewaard blijft; deze projectie is dus helemaal geen isometrie. Zo’n visualisatie via cirkels heet een indicatrix van Tissot, vernoemd naar cartograaf Nicolas Auguste Tissot. In feite had hij kaartprojecties geanalyseerd via infinitesimaal kleine cirkels; Tissot bewees dat die onder een projectie infinitesimale ellipsen worden, waarvan de assen overeenkomen met hoofdkrommingen op het oppervlak en schaalwijzigingen op de kaart. Een alternatieve eenvoudige transformatie is de stereografische projectie, die het gehele boloppervlak vanuit een punt projecteert op het raakvlak aan het antipodale punt. Deze projectie brengt weliswaar het volledige oppervlak in kaart, behalve het originele projectiepunt, doch heeft als nadeel dat het uiteindelijke beeld ook het onbeperkte vlak in beslag neemt.

De lengte- en breedtecirkels blijven hier onderling loodrecht staan en de indicatrix van Tissot blijft cirkelvormig, wat illustreert dat de stereografische projectie hoek- en vormbewarend is. Helaas wordt de oppervlakte gigantisch ontwricht; verder van het centrum neemt de oppervlakte van een geprojecteerd gebied steeds meer toe, cf. de grootte van de cirkels. Een conforme transformatie is er een die lokale hoekgroottes bewaart, en bewaart ook lokaal de vorm. Een oppervlaktegetrouwe transformatie wordt soms wel eens authalisch genoemd. Een historisch belangrijker voorbeeld van een conforme kaartprojectie werd ontworpen door de Vlaming Geert de Kremer in de de eeuw, beter gekend onder diens gelatiniseerde naam Gerardus Mercator. De Mercatorprojectie heeft enkele handige bijkomende eigenschappen.



Zo is deze cylindrisch; meridianen worden voorgesteld als gelijk gespreide verticale rechten en parallellen als horizontale rechten. Het belangrijkste voordeel echter heeft te maken met de andere rechten op de kaart, die precies overeenkomen met loxodromen op de bol; dit zijn krommen die de meridianen snijden onder een constante hoek en spiraleren tussen de twee polen. Als je op een (ge¨ıdealiseerde) aardbol een vaste koers op een kompas volgt, verkrijg je juist zo’n loxodroom. Merk op dat een loxodroom tussen twee algemene punten op een bol niet de kortst mogelijke afstand ertussen geeft—dat doet een grootcirkel—maar dus wel zeer eenvoudig te navigeren valt middels een kompas. Het feit dat loxodromen corresponderen met rechten op de kaart van Mercator, maakt deze bijzonder geschikt voor scheepvaart.

Volgens de indicatrix lijdt de projectie van Mercator duidelijk hetzelfde nadeel als de stereografische projectie: een explosie van oppervlakte rondom de polen. Afrika lijkt bijvoorbeeld vergelijkbaar met Groenland qua grootte, maar is in realiteit bijna  keer zo groot! Bovendien worden de polen zelf eigenlijk oneindig ver van de evenaar geprojecteerd. Ook het feit dat algemene rechten op de Mercatorkaart geen kortste weg voorstellen op het voorsteltboloppervlak, is misleidend. Kaarten die wel de eigenschap hebben dat ze richtingen vanuit een centraal punt bewaren, heten azimutaal; bij dit soort kaarten komen grootcirkels door een centraal punt P dus w´el overeen met rechten door dat punt op de kaart, en blijven cirkels op het boloppervlak met centrum P ook cirkels na projectie. Voor een oppervlaktegetrouwe azimutale kaart kan men bijvoorbeeld als volgt te werk gaan. Beschouw het raakvlak door een centraal punt P op de bol. Elke parallel wordt geprojecteerd



op de cirkel in dat vlak met centrum P en straal gelijk aan de driedimensionale afstand tot P. Het resultaat heet de azimutale projectie van Lambert (), vernoemd naar de wiskundige Johann Heinrich Lambert, en ziet er met P de noordpool uit zoals hieronder.

Om alle oppervlaktes te bewaren, moeten de afstanden tot het centrum P worden vervormd. De equidistante azimutale projectie is een variant die wel (verhoudingen tussen) afstanden tot het centrale punt behoudt, met als nadelen dat de oppervlakte toeneemt naar buiten toe en dat enkel lengtes op rechten door het centrum correct zijn: een kleine cirkel op de kaart net rond het centrum en een grote cirkel net binnen de rand stellen op de aardbol even grote cirkels rond de polen voor.

De cirkels van Tissot worden in de beide kaarten scheefgetrokken, dus die zijn niet conform. Deze equidistante azimutale projectie wordt gebruikt in het logo van de Verenigde Naties. Alle tot hier toe besproken kaarten vertonen imperfecties en geven een vertekend beeld van hoeken, oppervlaktes of afstanden. Daar is een goede reden voor: Carl Friedrich Gauss vond een differentiaalmeetkundig argument waarom een perfecte kaart niet kan bestaan!



Om het resultaat van Gauss te kunnen begrijpen, hebben we enkele differentiaalmeetkundige begrippen nodig. We defini¨eren allereerst de kromming κ van een cirkel als de omgekeerde van de straal, in overeenstemming met de intu¨ıtie dat een boog van een grotere cirkel minder krom lijkt. Voor een algemene (voldoende gladde) kromme kunnen we dan in elk van haar punten de “best passende” cirkel zoeken die er raakt, de zogenaamde osculerende cirkel, en de kromming in dat punt defini¨eren als de kromming van die cirkel. Beschouw vervolgens een punt P op een algemeen (voldoende glad) oppervlak. Dan bestaat er een vector uit dat punt die loodrecht staat op het oppervlak; de vlakken door deze vector snijden het oppervlak telkens lokaal in een kromme door P. Beschouw al hun krommingen in het punt P en geef die een positief of een negatief teken afhankelijk van aan welke kant de osculerende cirkel ligt. Uiteindelijk noemen we het minimum κ1 en het maximum κ2 van al deze krommingen de hoofdkrommingen in P en hun product κ1 ⋅ κ2 de Gausskromming. Voor een punt op een bol met straal r zijn de osculerende cirkels niets meer dan grootcirkels, zodat met andere woorden κ1 = κ2 = ±/r. De Gausskromming is overal gelijk aan /r 2 en dus overal positief. Voor een punt op een cilinder is juist e´e´n van de hoofdkrommingen nul en dus ook de Gausskromming. Rond een hyperbolisch punt hebben de hoofdkrommingen verschillende tekens en is de Gausskromming negatief. De precieze waarden van de hoofdkrommingen hangen af van hoe het oppervlak ingebed zit in de ruimte; bij bijvoorbeeld een platgedruktde cilinder zal de hoofdkromming die verschilt van nul bij bepaalde punten groter zijn geworden en bij andere punten kleiner. Desondanks, zo ontdekte Gauss, blijkt de Gausskromming w´el een intrinsieke grootheid, die niet afhangt van de inbedding van het oppervlak. Met andere woorden, de Gausskromming in een punt op een oppervlak wordt volledig bepaald door lokale meetkundige data (zoals afstanden en hoeken), en blijft dan ook invariant onder lokale isometrie¨en (die die data bewaren). Gauss vond dit zo opmerkelijk dat hij dit zijn theorema egregium of “wonderlijke stelling” noemde, en schreef in het Latijn ([]): Formula itaque art. praec. sponte perducit ad egregium Theorema: si superficies curva in quamcunque aliam superficias explicatur, mensura curvaturas in singulis punctis invarianta manet. Als praktisch gevolg kan er van geen enkel gebied op aarde, ongeacht hoe klein, een perfecte vlakke kaart bestaan. In tegenstelling tot een vlak heeft een bol immers een strikt positieve Gausskromming, dus een kaartafbeelding moet wel meetkundige informatie scheeftrekken. Dit rudimentaire besef gaat eigenlijk best ver terug in de cartografie. Mercator had wel door dat zijn meest beroemde projectie zeer ongeschikt is voor oppervlaktevergelijkingen; hij was een van de ontwerpers van de oppervlaktegetrouwe sinuso¨ıdale kaart hieronder, de eeuw. Parallellen zijn er gelijkmatig gespreide horizontale lijnen en meridianen worden voorgesteld als halve sinusgolven met gelijkmatig gespreide toppen. De indicatrix van Tissot wijst uit dat de noodzakelijke vervorming het grootst is aan de polen en aan de rand. Een mogelijkheid om deze vervorming globaal minder extreem te maken, is de projectie op te delen in “maantjes”



en die terug rechtop te trekken—zie de tweede kaart hieronder.

Een alternatieve populaire oppervlaktegetrouwe kaart is die van Karl Mollweide uit , die vergelijkbaar is met de sinuso¨ıdale kaart maar ellipsen gebruikt in plaats van sinusgolven.

De kaart van Mollweide staat ook bekend als de homolografische projectie en kan eveneens worden opgesplitst in maantjes.



John Goode experimenteerde met deze en gerelateerde kaarten op zoek naar een esthetische kaart die een duidelijk overzicht biedt over alle continenten heen. Hij bekwam uiteindelijk het onderstaande model in  ([]) door de sinuso¨ıdale projectie tussen ○ ′ .′′ noorderen zuiderbreedte samen te stellen met de Mollweideprojectie en die op goedgekozen punten open te breken. Het resultaat is nog steeds oppervlaktebewarend. Goode noemde zijn kaart de homolosine, een samentrekking van homolografisch en sinuso¨ıdaal.

Er is een technische reden waarom precies op die breedtegraden: op deze parallellen komen de schaalfuncties van de homolografische en de sinuso¨ıdale kaart precies overeen. De Bonneprojectie, naar Rigobert Bonne, is een veralgemening van de sinuso¨ıdale projectie die eveneens oppervlaktes correct blijft weergeven.



Ze wordt opgebouwd rond een verticaal lijnstuk als nulmeridiaan, waarrond de parallellen worden uitgetekend als concentrische cirkelbogen op een zodanige manier dat de schaal op de nulmeridiaan en langs elke parallel constant is. De constructie heeft e´e´n vrije parameter: de kromming van de boog die de evenaar voorstelt. Zonder kromming reduceert deze kaart juist tot de sinuso¨ıdale projectie, maar men kan die vari¨eren om de vorm langs een specifieke parallel correct weer te geven; zo wordt op de afbeelding de vorm uitstekend behouden rond de parallel op ○ noorderbreedte. Helaas betekent het theorema egregium dat de vorm snel serieus scheeftrekt indien verder van deze parallel en nulmeridiaan verwijderd. Er bestaat een familie kaartprojecties met nog een andere filosofie. Aangezien het hoe dan ook onmogelijk is alle metrische eigenschappen in een vlakke kaart te bewaren, kan men trachten om een gulden middenweg te zoeken in de vervorming van hoeken e´n oppervlaktes tegelijk. Zulke compromisprojecties zien er globaal soms beter uit dan kaarten die e´e´n meetkundig aspect precies weergeven. Een voorbeeld van zo een projectie is de Winkel Tripel van Oswald Winkel uit , verkregen vanuit de gemiddelde co¨ordinaten van twee verschillende kaarten. De indicatrix van Tissot illustreert duidelijk hoe de poolgebieden het meest te lijden hebben onder zowel een hoekals oppervlaktevervorming, maar over het algemeen zijn de fouten relatief beperkt.

Zoals de maantjes in de sinuso¨ıdale kaart al illustreerden, kan het nuttig zijn de aardbol niet op e´e´n convex gebied te projecteren maar op verscheidene aaneengeplakte convexe stukjes. Het voordeel is de vervorming dan lokaal blijft, het nadeel dat het lastig is een globaal beeld te krijgen bij grote opgesplitste landmassa’s. Er is een algemene techniek om een compromisprojectie met dat idee op te stellen: plaats de aarde binnen een veelvlak dat een bol benadert, projecteer de punten op het aardoppervlak vanuit het centrum op dat veelvlak, en ontvouw het resultaat. Voorbeelden in die categorie zijn de Dymaxion van Buckminster Fuller uit  en onderstaande vlinder van Steve Waterman uit  die een afgeknotte octa¨eder gebruikt. De precieze vorm van dit veelvlak verkreeg Waterman uit een studie van bolpakkingen (zie



curiosum .).

De volgende is de orthoapsidale kaart van Erwin Raisz uit , bijgenaamd de “armadillo”. De meridianen en parallellen worden er voorgesteld als ellipsbogen. De zuidelijke gebieden zijn hier moeiljk te onderscheiden, en in het bijzonder is het zuidpoolgebied onzichtbaar.

De polyconische projectie, opgesteld in de jaren  van de negentiende eeuw, geeft dan weer een mooi evenwichtig beeld rond een centraal gekozen meridiaan—ook in de poolgebieden. De rond Amerika gecentreerde versie was een lange tijd erg in trek in de Verenigde Staten. De projectie wordt als volgt opgebouwd. Vertrek vanuit een verticaal lijnstuk dat de gekozen meridiaan voorstelt. Beschouw de familie van alle kegels die de aardbol raken in een parallel. Snijd elk van deze kegels langs de tegenoverliggende meridiaan, rol die vlak open, en zet het beeld van de rakende parallel uit op de overeenkomstige positie op de getekende meridiaan. De parallellen worden afgebeeld op niet-concentrische cirkelbogen; enkel de evenaar geeft een cilinder als (ontaarde) kegel en wordt afgebeeld op een horizontaal lijnstuk. Elke parallel



bepaalt een andere kegel in de constructie; vandaar de naam “polyconisch”.

Het komt hier ter sprake dat een projectie niet noodzakelijk moet vertrekken uit de evenaar en nulmeridiaan als referentiekader; op een generieke bol bestaat er niet eens een goedgedefinieerde evenaar. Het is heel goed mogelijk om het referentiekader eerst te roteren alvorens te projecteren om een beter beeld te krijgen van een specifieke regio op aarde. Bijvoorbeeld, bij de projectie van Bonne zag het gebied rond de nulmeridiaan en een vrij te kiezen parallel er meer dan behoorlijk uit; middels een rotatie kan de projectie gebruikt worden om eender welke T-vormige regio behoorlijk op kaart te krijgen. Een transversale kaart roteert de aarde juist over ○ zodat de symmetrieas van de kaart loodrecht staat op de aardas. Het nadeel is dat het netwerk van meridianen en parallellen wat onoverzichtelijk kan worden; beschouw bijvoorbeeld de equirectangulaire projectie (of plate carr´ee).



Conceptueel is deze equirectangulaire projectie zeer eenvoudig: meridiaan- en parallellijnen worden afgebeeld op gelijk gespreide verticale en horizontale lijnstukken. We zien opnieuw dat er problemen opduiken rond de poolgebieden (op elk aspect). Het resultaat van dezelfde projectie, maar na een rotatie die de nulmeridiaan op de evenaar stuurt, ziet er als volgt uit.

Deze transversale kaart staat gekend als de projectie van Cassini (naar C´esar-Franc¸ois Cassini de Thury, midden de eeuw).



Het moge duidelijk zijn dat er niet iets bestaat als d´e universele perfecte kaartprojectie, maar dat verscheidene doelen om verscheidene projecties vragen. Voor kaarten van relatief kleine gebieden is de precieze keuze van projectie weinig significant. Voor grote gebieden wordt het weliswaar belangrijk te beseffen dat bepaalde verhoudingen en/of vormen niet meer kloppen of dat de schaal niet overal gelijk is, maar daarom zijn kaarten nog niet compleet nutteloos. Zo doet de Mercatorkaart uitstekend dienst bij navigatie, maken globale kaarten in atlassen over het algemeen gebruik van projecties die een compromis sluiten, en zijn volledig oppervlaktegetrouwe projecties ideaal voor thematische kaarten. We bespreken nog een paar van de honderden andere exotische projecties die elk hun eigen voor- en nadelen hebben. Herinner je de azimutale projecties op blz. , die alle richtingen vanuit een vast punt naar alle punten op de kaart correct weergeven. Het omgekeerde is een retroazimutale projectie, die de richting vanuit elk punt op de kaart naar een vast punt toe correct weergeeft. Met andere woorden, verbind een punt op de kaart met het centrum en meet de hoek met de verticalen; de grootcirkel tussen de punten op de aardbol maakt diezelfde hoek met de meridianen. Een voorbeeld is de retroazimutale projectie van Ernst von Hammer, gekarakteriseerd door de extra eigenschap dat alle afstanden tot het centrum verhoudingsgewijze kloppen. Met het centrum op de nulmeridiaan op ○ noorderbreedte geeft dat het volgende bizarre resultaat.



Een alternatief is de retroazimutale projectie van Joseph von Littrow uit , die bovendien conform is, maar slechts de aardbol gedeeltelijk kan weergeven zonder overlap. Meridianen worden er afgebeeld op takken van hyperbolen, parallellen op ellipsen.

De andere karakteristieke eigenschap van de equidistante azimutale projectie was het correct weergeven van afstanden tot het centrum. Beschouw nu eens de volgende kaart.



Deze complexere projectie werd geconstrueerd door Hans Maurer in . Ze is niet langer azimutaal, maar geeft wel de afstanden tot twee punten correct weer—op de kaart enerzijds het kruispunt van nulmeridiaan en evenaar, anderzijds het punt op ○ noorderbreedte en ○ oosterlengte. De constructie werkt als volgt. Teken eerst de referentiepunten Q1 en Q2 . Bereken vervolgens voor elk punt P op de aardbol de afstanden ∣PQ1 ∣ en ∣PQ2 ∣ langs de bol, en teken cirkels rond Q1 en Q2 met deze afstanden als respectievelijke stralen, in verhouding met de afstand ∣Q1 Q2 ∣. Het gezochte overeenkomstige punt op de kaart wordt verkregen als een doorsnede van deze cirkels. De kaart van Maurer is populair voor kaarten van het Aziatische continent, weliswaar eerder omwille van de beperkte vervorming bij twee goedgekozen referentiepunten en niet zozeer omwille van de afstandsbewarende eigenschap. In  ontwikkelde Wellman Chamberlin een uitbreiding naar drie punten. Verhoudingen tussen afstanden tot drie referentiepunten kunnen niet langer precies weergegeven worden, omdat de drie overeenkomstige cirkels in Maurers constructie niet langer in een uniek punt snijden maar in drie kandidaatpunten. De constructie van Chamberlin gebruikt het middelpunt van de bekomen driehoek. Het resultaat is noch oppervlakte- noch afstand- noch hoekgetrouw, maar geeft een uitstekend beeld van de regio tussen en rond de referentiepunten en wordt dan ook frequent gebruikt in kaarten van gehele continenten. Ten slotte wordt er in de fotografie wel eens gebruik gemaakt van de quincunciale projectie van Charles Peirce om sferische panorama’s esthetisch weer te geven.



...

...

...

Deze projectie beeldt in essentie een hemisfeer van de bol af op een vierkant (via elliptische functies), waarbij de meridiaan op de zijden komt te liggen, en dit lukt bijna overal conform: enkel op de hoekpunten van het vierkant gaat de hoekgetrouwheid verloren. Vervolgens deed Peirce hetzelfde met de antipodale hemisfeer, verdeelde hij dat vierkant via de diagonalen in vier stukken, en puzzelde hij de vijf delen—vandaar de naam—ineen tot e´e´n groot vierkant. Het resultaat is een bijna overal conforme kaart die het vlak in alle richtingen kan betegelen.

...

...

...

...

...

...

...

...

...

[1] C. F. Gauss, Disquisitiones generales circa superficies curvas. Typis Dieterichianis, 1828. [2] J. Goode, The homolosine projection—a new device for portraying the Earth’s surface entire. Annals of the Association of American Geographers, vol. 15, no. 3, 1925, p. 119–125. [3] T. Jung, Compare map projections. https://map-projections.net. [4] J. Snyder, P. Voxland, An album of map projections. U.S. Government Printing Office, 1989.



39

(todo)

39.1 Stelling van Cross

39.17 Penrosebetegelingen

39.2 Betegelende vijfhoeken

39.18 Punten van Brocard

39.3 Driehoek van Calabi

39.19 Probleem van Malfatti

39.4 Regelmatige zeventienhoek

39.20 Stellingen van Napoleon en Van Aubel

39.5 Stelling van Monsky

39.21 Stelling van Ptolemaeus

39.6 Stelling van Routh

39.22 Stelling van Laisant

39.7 Dissectie van Duijvestijn 39.8 Archimedes’ arbelos

39.23 Passer-en-liniaalconstructies, luciferconstructies

39.9 Formule van Pick

39.24 Vermoeden van Toeplitz

39.10 Museumprobleem van Chv´atal

39.25 Stelling van Viviani

39.11 Wijnrekwonder

39.26 Stelling van Sylvester–Gallai

39.12 Formule van Pick

39.27 Vierdegraadskromme van Klein

39.13 Stelling van Jung

39.28 Veelhoeken effenen

39.14 Stelling van Holditch

39.29 Kakeyaverzamelingen

39.15 Probleem van prins Rubert

39.30 Weaire–Phelanschuim

39.16 Dissectie van Blanche

39.31 Japanse cirkelstelling



L o gica

39

(todo)

39.33 Lambdacalculus

39.37 Ackermannfunctie

39.34 Cantors diagonaalargument 39.38 Halting problem 39.35 Het hotel van Hilbert 39.36 Keuzeaxioma

39.39 Paradox van Banach–Tarski



Varia

40

Lindenmayersystemen

Lindenmayersystemen of L-systemen werden in  ontwikkeld door Aristid Lindenmayer, Hongaars bioloog en botanist aan de universiteit van Utrecht. Zijn modellen waren origineel bedoeld om de groei van schimmels en planten te beschrijven, maar vormen ook een nuttige manier om heel wat fractalen te genereren. Zo’n Lindenmayersysteem bestaat uit een alfabet met een aantal symbolen, een startreeks of axioma, en een aantal herschrijfregels die bepalen hoe symbolen om te zetten zijn in langere reeksen. Een voorbeeld van Lindenmayer zelf gebruikt het alfabet {A, B}, de startreeks B, en de twee herschrijfregels A → AB en B → A. Telkens elke A en B vervangen leidt tot de reeks B → A → AB → ABA → ABAAB → ABAABABA → ABAABABAABAAB → ⋯ De lengtes van de opeenvolgende tussenstappen zijn hier precies de Fibonaccigetallen. Om een Lindenmayersysteem grafisch weer te geven, associ¨eren we elk symbool in het alfabet met een bepaalde grafische handeling. We stellen de volgende interpretaties voorop. F

betekent een eenheid vooruit tekenen vanuit de huidige positie;

+

betekent over een vastgekozen hoek δ naar links roteren;

−

betekent over een vastgekozen hoek δ naar rechts roteren;

[

betekent de huidige positie en ori¨entatie opslaan (push);

]

betekent terugkeren naar de laatst opgeslagen positie en ori¨entatie (pop).

Vaak worden nog extra symbolen gebruikt om de evolutie van de fractaal te dirigeren, zonder dat deze enige grafische interpretatie krijgen. Een illustratief voorbeeld is de volgende sneeuwvlokfractaal, vernoemd naar Tam´as Vicsek. Beschouw het alfabet {F, +, −}, het axioma F−F−F−F, de herschrijfregel F → F−F+F+F−F, samen met de bovenstaande interpretaties met δ = ○ . Grafisch (en in elke stap herschaald) leidt dit tot de volgende, steeds fijnere figuren.

⋯



Pas de herschrijfregel aan tot F → F−F++F−FF en het resultaat ziet er al helemaal anders uit.

⋯

De herschrijfregel F → F+F−F−FF+F+F−F geeft dan weer het eiland van Koch:

⋯

Hetzelfde alfabet maar met het axioma F, herschrijfregel F → −F++F− en δ = ○ resulteert in de zogenaamde kromme van L´evy, die er na  iteraties als volgt uitziet.

Bill Gosper kon via een Lindenmayersysteem een mooie vlakvullende kromme construeren, ook wel de flowsnake genoemd. Hier is het alfabet {F, G, +, −}, het axioma F, de herschrijfregels F → F−G−−G+F++FF+G− en G → +F−GG−−G−F++F+G, en de parameter δ = ○ ([]). We laten zowel F als G een eenheid vooruit tekenen.

⋯



Ook enkele bekende fractalen zijn eenvoudig te formaliseren via een Lindenmayersysteem. Door de twee herschrijfregels van de kromme van Gosper aan te passen tot F → G+F+G en G → F−G−F benadert het resultaat de driehoek van Sierpi´nski. Het resultaat na zeven iteraties staat hieronder links.

Een alternatieve constructie hierboven rechts werkt met het alfabet {F, X, +, −}, axioma F en herschrijfregels X → F+X+F en F → X−F−X. Het symbool X krijgt geen grafische betekenis. Vandaag worden Lindenmayersystemen en varianten daarvan (zoals stochastische systemen) heel concreet gebruikt om softwarematig realistische bomen en planten te genereren—juist waarvoor ze oorspronkelijk bedoeld waren! Onder andere de game- en filmindustrie maken dankbaar gebruik van dergelijke software, zoals SpeedTree.

F → FF−[−F+F+F]+[+F−F−F]

F → F[+F]F[−F][F]

F → F[+F]F[−F]F

Ter illustratie waartoe Lindenmayersystemen met een push- en pop-instructie in staat zijn, volgen hier enkele voorbeelden van heel eenvoudige (deterministische) systemen met slechts e´e´n herschrijfregel.



X → F+F[[X]−X]−F[−FX]+X, F → FF

X → F[+X][−X]FX, F → FF

X → F[+X]F[−X]+X, F → FF

Extra symbolen geven alleen maar meer variatie!

[1] M. Gardner, Mathematical games: in which “monster” curves force redefinition of the word “curve”. Scientific American, vol. 235, no. 6, 1976, p. 124–133. [2] A. Lindenmayer, Mathematical models for cellular interaction in development. Journal of Theoretical Biology, vol. 18, no. 3, 1968, p. 280–315. [3] P. Prusinkiewicz, Graphical applications of L-systems. Proceedings of Graphics Interface and Vision Interface, 1986, p. 247–253. [4] P. Prusinkiewicz, A. Lindenmayer, The algorithmic beauty of plants. Springer, 1996. [5] SpeedTree, https://store.speedtree.com/.



41

Lexicodes

Lexicografische codes, of lexicodes zoals John Conway ze meestal afkortte, zijn eenvoudig te defini¨eren codes met desalniettemin een verrassend rijke structuur. Ze worden bepaald door een alfabet waarover we de codewoorden zullen defini¨eren en een parameter d die een soort afstand tussen de codewoorden zal voorstellen. Gebruiken we de verzameling N als alfabet, dan is een woord in deze context een oneindige reeks van natuurlijke getallen waar slechts op een eindig aantal posities een getal verschillend van nul voorkomt. Concreet is een woord van de vorm a = (⋯ 0 0 0 a n ⋯ a2 a1 a0 ), met elke a i een natuurlijk getal (mogelijks met meerdere cijfers!). Zo’n woorden worden voorzien van een natuurlijke lexicografische ordening: we stellen a < b als en slechts als a k < b k voor een zekere index k, terwijl a i = b i voor alle indices i > k. Zonder voorloopnullen geeft dat de ordening 0 < 1 < 2 < ⋯ < 10 < 11 < 12 < ⋯ < 20 < 21 < 22 < ⋯ < 100 < 101 < 102 < ⋯ De lexicode met parameter d wordt nu inductief verkregen uit het nulwoord 0, door telkens het lexicografisch kleinste woord erbij te voegen dat in minstens d posities verschilt van alle reeds gekende codewoorden. Voor d =  geeft dit proces bijvoorbeeld de codewoorden (⋯ 0 0 0 0 0 0), (⋯ 0 0 0 1 1 1), (⋯ 0 0 0 2 2 2), (⋯ 0 0 0 3 3 3), ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ (⋯ 0 0 1 0 1 2), (⋯ 0 0 1 1 0 3), (⋯ 0 0 1 2 3 0), (⋯ 0 0 1 3 2 1), (⋯ 0 0 1 4 5 6), ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ (⋯ 0 0 2 0 2 3), (⋯ 0 0 2 1 3 2), ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ (⋯ 0 0 3 0 3 1), ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ (⋯ 0 1 0 0 1 3), ⋮ ⋮ ⋮ ⋮ ⋮ ⋮



Nu kunnen we de magische lexicodestelling van Conway aankondigen: de codewoorden van de lexicode met parameter d hebben onder termsgewijze optelling en scalaire vermenigvuldiging de structuur van een vectorruimte. Een eerste probleem hiermee is dat de natuurlijke getallen niet eens een veld vormen. De optelling en vermenigvuldiging die deze stelling doen opgaan, zijn echter niet de bewerkingen zoals we ze kennen! In feite worden de nieuwe bewerkingen op N—die we hier met ⊕ en ⊙ zullen noteren—juist vastgelegd door de lexicodestelling. Als we verlangen dat de som van twee lexicodewoorden opnieuw een codewoord is, dan kunnen we beginnen met de som (⋯ 0 0 0 0 0) ⊕ (⋯ 0 0 0 0 0) = (⋯ z z z z z), waar elk symbool z gelijk is aan 0 ⊕ 0. Aangezien slechts eindig veel posities in een lexicodewoord mogen verschillen van nul, moet dus alvast 0 ⊕ 0 = 0. De vergelijking x ⊕ x = x heeft in een veld enkel het nulelement als optelling, dus ook voor de lexicografische som speelt 0 wel degelijk de rol van nulelement. In het bijzonder is x ⊕ 0 = 0 ⊕ x = x voor elk getal x. Beschouw vervolgens de som van de twee lexicodewoorden (⋯ 0 0 1 1 1) ⊕ (⋯ 0 1 0 1 2) = (⋯ 0 1 1 x y), met x = 1 ⊕ 1 en y = 1 ⊕ 2. Het unieke codewoord van deze vorm is het woord (⋯ 0 1 1 0 3), wat betekent dat 1⊕1 = 0 (of, iets technischer, het veld heeft karakteristiek twee) en 1⊕2 = 3. Daarna kan berekenen dat ⎧ ⎪ ⎪1 ⊕ 3 = 1 ⊕ (1 ⊕ 2) = (1 ⊕ 1) ⊕ 2 = 0 ⊕ 2 = 2, ⎨ ⎪ ⎪ ⎩2 ⊕ 3 = 2 ⊕ (2 ⊕ 1) = (2 ⊕ 2) ⊕ 1 = 0 ⊕ 1 = 1. Beschouw vervolgens de lexicode met d = . Die bevat onder meer de codewoorden (⋯ 0 0 0 0 0), (⋯ 1 0 1 2 3), Dan moet

(⋯ 0 1 1 1 1), (⋯ 1 1 0 3 2),

(⋯ 0 2 2 2 2), (⋯ 1 2 3 0 1),

(⋯ 0 3 3 3 3), (⋯ 1 3 2 1 0),

(⋯ 0 4 4 4 4), (⋯ 1 4 5 6 7).

(⋯ 0 4 4 4 4) ⊕ (⋯ 1 0 1 2 3) = (⋯ 1 4 5 6 7),

dus 4 ⊕ 0, 4 ⊕ 1, 4 ⊕ 2 en 4 ⊕ 3 geven precies hetzelfde resultaat als de klassieke optelling. Dit kan veralgemeend worden: Conway toonde in [] aan dat voor elke m een macht van twee, er geldt dat m ⊕ n = m + n voor alle n < m, terwijl m ⊕ m = 0. Uit deze observatie kan men eenvoudig de lexicografische som van willekeurige getallen afleiden door deze uit te schrijven in sommen van machten van twee, of met andere woorden, in hun binaire vorm. Deze som is immers gelijk aan de lexicografische som. Machten van twee die in beide termen optreden vallen weg, en de resterende machten sommeren opnieuw tot de lexicografische som. Zo is 3 ⊕ 5 = (1 + 2) ⊕ (1 + 4) = (1 ⊕ 2) ⊕ (1 ⊕ 4) = 1 ⊕ 1 ⊕ 2 ⊕ 4 = 2 ⊕ 4 = 2 + 4 = 6. In feite komt dit neer op het optellen van de binaire representaties, maar zonder overdragen van sommen 1 ⊕ 1 naar de volgende positie—deze termen geven gewoon 0. Dit hoofdstuk wordt verderop afgesloten met een concrete opteltabel voor de getallen tot en met 15.



Vermenigvuldiging is lastiger. Aangezien 0 het nulelement is, moet alvast x ⊙ 0 = 0 ⊙ x = 0 voor elk getal x. De vermenigvuldiging blijkt slechts bepaald op een constante factor na, en het houdt steek om het getal 1 als eenheid te kiezen, zodat x ⊙ 1 = 1 ⊙ x = x voor elk getal x. Met deze keuze volgt in de lexicode met d =  dat 2 ⊙ (⋯ 0 1 0 1 2) = (⋯ 0 2 0 2 x), waarin x = 2 ⊙ 2. Het unieke codewoord van deze vorm in deze lexicode is (⋯ 0 2 0 2 3), wat betekent dat 2 ⊙ 2 = 3! Gebruik makend van de vereiste eigenschappen van de veldoperaties (zoals distributiviteit van ⊙ t.o.v. ⊕) kan men daarna berekenen dat ⎧ ⎪ ⎪2 ⊙ 3 = 2 ⊙ (2 ⊕ 1) = (2 ⊙ 2) ⊕ (2 ⊙ 1) = 3 ⊕ 2 = 1, ⎨ ⎪ ⎪ ⎩3 ⊙ 3 = (2 ⊕ 1) ⊙ 3 = (2 ⊙ 3) ⊕ (1 ⊙ 3) = 1 ⊕ 3 = 2. Vervolgens blijken 4 ⊙ 0, 4 ⊙ 1, 4 ⊙ 2 en 4 ⊙ 3 opnieuw net dezelfde resultaten te geven als de klassieke vermenigvuldiging. Ook hier geldt er een algemeen achterliggend patroon ([]): k voor m van de vorm 2 geldt dat m ⊙ n = m ⋅ n voor alle n < m, terwijl m ⊙ m = / ⋅ m. En ook dit resultaat volstaat om algemene lexicografische producten uit te rekenen, zij het met wat meer knutselwerk, door steeds te herleiden naar specifieke machten van twee. Zo blijkt 7 ⊙ 9 = (1 ⊕ 2 ⊕ 4) ⊙ (1 ⊕ 8) = (1 ⊙ 1) ⊕ (2 ⊙ 1) ⊕ (4 ⊙ 1) ⊕ (1 ⊙ 8) ⊕ (2 ⊙ 8) ⊕ (4 ⊙ 8) = 1 ⊕ 2 ⊕ 4 ⊕ 8 ⊕ (2 ⊙ (2 ⋅ 4)) ⊕ (4 ⊙ (2 ⋅ 4)) = 15 ⊕ (2 ⊙ 2 ⊙ 4) ⊕ (4 ⊙ 2 ⊙ 4) = 15 ⊕ (3 ⊙ 4) ⊕ (2 ⊙ 6) = 15 ⊕ (3 ⋅ 4) ⊕ (2 ⊙ (2 ⊕ 4)) = 15 ⊕ 12 ⊕ (2 ⊙ 2) ⊕ (2 ⊙ 4) = 15 ⊕ 12 ⊕ 3 ⊕ 8 = 8. Verderop staat de vermenigvuldigingstabel voor de getallen tot en met 15. John Conway en Neil Sloane bestudeerden in [] een uitgebreidere klasse van lexicodes, over bijvoorbeeld ook eindige alfabetten of met andere afstandsnoties, en beschrijven hoe heel wat bekende codes opduiken als lexicografische codes met geschikte parameters.

[1] J. Conway, Integral lexicographic codes. Discrete Mathematics, vol. 83, no. 2–3, 1990, p. 219–235. [2] J. Conway, On numbers and games. AK Peters, 2000. [3] J. Conway, N. Sloane, Lexicographic codes: error-correcting codes from game theory. IEEE Transactions on Information Theory, vol. 32, no. 3, 1986, p. 337–348.



⊕ 0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

0

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

1

1

0

3

2

5

4

7

6

9

8 11 10 13 12 15 14

2

2

3

0

1

6

7

4

5 10 11 8

9 14 15 12 13

3

3

2

1

0

7

6

5

4 11 10 9

8 15 14 13 12

4

4

5

6

7

0

1

2

3 12 13 14 15 8

9 10 11

5

5

4

7

6

1

0

3

2 13 12 15 14 9

8 11 10

6

6

7

4

5

2

3

0

1 14 15 12 13 10 11 8

9

7

7

6

5

4

3

2

1

0 15 14 13 12 11 10 9

8

8

8

9 10 11 12 13 14 15 0

1

2

3

4

5

6

7

9

9

8 11 10 13 12 15 14 1

0

3

2

5

4

7

6

10 10 11 8

9 14 15 12 13 2

3

0

1

6

7

4

5

11 11 10 9

8 15 14 13 12 3

2

1

0

7

6

5

4

12 12 13 14 15 8

9 10 11 4

5

6

7

0

1

2

3

13 13 12 15 14 9

8 11 10 5

4

7

6

1

0

3

2

14 14 15 12 13 10 11 8

9

6

7

4

5

2

3

0

1

15 15 14 13 12 11 10 9

8

7

6

5

4

3

2

1

0

⊙ 0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15

2

0

2

3

1

8 10 11 9 12 14 15 13 4

3

0

3

1

2 12 15 13 14 4

4

0

4

8 12 6

5

0

5 10 15 2

6

0

6 11 13 14 8

7

0

7

8

0

9

0

7

0

5

2 14 10 11 15 3 7

0

6

0

0 6

0 7

7 13 9

5

1 12 10 9 15 2

9 14 10 13 3

9 12 1

5

6

7

5

8 11 9 10

8 13 3 3

0

1

4 11 14 4

4 15 8

6

1

5

8 12 4 11 3

7 15 13 5

1

9

6 14 10 2

9 14 7 15 6

1

8

10 0 10 15 5

3

11 0 11 13 6

7 12 10 1

12 0 12 4

8 13 1

13 0 13 6 11 9 14 0 14 7

9 12 6

9

9

5

2 12 11

5 12 11 2 10 3 1 11 14 4 9

2

2

4 13

8 13 7

4 15 14 5

3

8

6 10 2 14 11 7 15 3

4 15 2 14 3

8

5

7 10 1 12

5 11 2 12 10 4 13 3 15 1

15 0 15 5 10 1 14 4 11 2 13 7

8

8

6

3 12 6

9

42

Conways soldaten

John Conway analyseerde in  een interessante variant van het alom bekende solitairespel (zie curiosum ??). Het speelbord is hier een oneindig rooster dat door een horizontale lijn in twee gedeeld wordt, met een arbitraire eindige opstelling van pionnen of “soldaten” onder de lijn als startconfiguratie. Het doel is om via de reglementaire solitairezetten zo ver mogelijk over de lijn te geraken. Uiteraard kun je de eerste rij boven de lijn bereiken vanuit een opstelling met twee soldaten. Een optimale opstelling voor de tweede rij bestaat uit vier soldaten. Voor de derde rij zijn al acht soldaten nodig, en het blijkt dat de vierde rij niet met minder dan  soldaten lukt.

×

×

×

×

Hoeveel soldaten zijn er nodig voor de vijfde rij? Verrassend genoeg blijkt deze opgave plots niet langer realiseerbaar: hoe je de startconfiguratie ook kiest, met hoeveel pionnen je ook start, de soldaten kunnen nooit doordringen tot de vijfde rij! Dit resultaat valt heel elegant hard te maken door middel van een goedgekozen scorefunctie, die iedere positie een bepaald label toekent. De totaalsom van alle labels in een configuratie noemen we diens score. De scorefunctie moet zodanig opgesteld worden dat de totale score niet kan verhogen na een legitieme zet. Stelling. Het is onmogelijk om in het spel van Conway verder te geraken dan de vierde rij. Bewijs. Kies een doel op de vijfde rij. We labelen elke cel van het schaakbord met een macht √ van φ = (  − )/, het kleine broertje van de gulden snede. Merk op dat  < φ <  en dat φ2 + φ = . Label de centrale cel op de vijfde rij met φ0 = , en de rest zoals hieronder. Onder deze labeling kan een reglementaire solitairezet de score onmogelijk omhoog krijgen: ofwel springt een pion met label φ k over φ k+1 naar φ k+2 en daalt de score (φ k+2 < φ k + φ k+1 ), ofwel over φ k−1 naar φ k−2 en blijft de score onveranderd (φ k−2 = φ k + φ k−1 ).



 ... φ ... . . . φ3 φ2 φ3 . . . . . . φ5 φ4 φ3 φ4 φ5 . . . . . . φ7 φ6 φ5 . . . φ8 φ7 φ6 . . . φ9 φ8 φ7 . . . φ10 φ9 φ8 . . . . .. .. .. ..

φ4 φ5 φ6 φ7 . . . φ5 φ6 φ7 φ8 . . . φ6 φ7 φ8 φ9 . . . φ7 φ8 φ9 φ10 . . . .. .. .. .. .. . . . . .

In iedere kolom vormen de labels een meetkundige rij. We kunnen narekenen dat alle labels onder de startlijn precies sommeren tot , gebruikmakend van de somformule voor meetkundige reeksen, door de getallen kolom per kolom samen te tellen: ∞

∞ ∞

j=0

i=0 j=0

∑ φ5+ j +  ∑ ∑ φ6+i+ j =

∞ ∞ φ5 φ6+i φ3 φ4 + ∑ = φ3 +  ∑ φ4+i = + = φ + φ2 = . −φ  − φ  − φ  − φ i=0 i=0

Volgens deze berekening moet de score van een (eindige) startconfiguratie strikt kleiner zijn dan . Het is dus onmogelijk om een eindscore van  of meer—in het bijzonder het beoogde doel op de vijfde rij—te bereiken. ∎ In dit bewijs blijkt de totale score van het volledige halfvlak onder de lijn precies gelijk aan . Simon Tatham en Gareth Taylor vonden een methode die startend met alle soldaten effectief de vijfde rij bereikt via een oneindige reeks zetten ([]). Ook blijkt het probleem oplosbaar met een eindige configuratie zodra e´e´n soldaat, hoe ver ook, een kompaan op zijn schouders mag dragen aan de start ([]). Alternatief kunnen we ook diagonale zetten toelaten, en dan geraken de soldaten zelfs tot en met de achtste lijn, maar niet verder.

[1] G. Bell, D. Hirschberg, P. Guerrero, The minimum size required of a solitaire army. Integers Electronic Journal of Combinatorial Number Theory, vol. 7, 2007, G7. [2] E. Berlekamp, J. Conway, R. Guy, Winning ways for your mathematical plays (volume ). A.K. Peters, 2004. [3] B. Cs´ak´any, R. Juh´asz, The solitaire army reinspected. Mathematics Magazine, vol. 73, no. 5, 2000, p. 354–362. [4] S. Tatham, G. Taylor, Reaching row five in solitaire army. http://www.chiark.greenend.org.uk/~sgtatham/solarmy/, 2007.



43

Arrows onmogelijkheidsstelling

Kenneth Arrow was een Amerikaans econoom, die een verrassend resultaat met betrekking tot kiessystemen ontdekte. Om zijn resultaat te schetsen, analyseren we een fictief voorbeeld; laat ons veronderstellen dat  kiezers in een verkiezing kunnen stemmen op vijf kandidaten (A, B, C, D en E), en dat de volgende voorkeursordeningen uit de bus komen. De eerste kolom bevat het aantal kiezers die de overeenkomstige ordening prefereren. 

A>D>E>C>B



B>E>D>C>A



C>B>E>D>A



D>C>E>B>A



E>B>D>C>A



E>C>D>B>A

Wie heeft deze verkiezing gewonnen? Er zijn verschillende mogelijkheden denkbaar om een winnaar te associ¨eren aan zo’n verkiezingsuitslag. Het meest voor de hand liggende voorstel is rangschikking via meerderheid: de kandidaat met de meeste stemmen op de eerste plaats, wint. Bij gelijkspel wordt gekeken naar het aantal stemmen op de tweede plaats, enzoverder. In dit geval gaat A met de eer lopen, want  kiezers stemmen A op de eerste plaats. Het run-offprincipe kan ook omgekeerd toegepast worden, door iteratief de kandidaat met de minste voorkeursstemmen te elimineren. Initieel geniet kandidaat E van slechts zes stemmen op de eerste plaats, en wordt deze uit de ranking verwijderd. Vervolgens blijkt D met negen stemmen het minst populair. In de volgende stap wordt B ge¨elimineerd, en dan is het duidelijk dat C de uiteindelijke winnaar wordt in dit systeem.

⋯

→



A>D>C>B



B>D>C>A



C>B>D>A



D>C>B>A



C>D>B>A

→



C>B>A



A>C>B



B>C>A

→



C>A



A>C

Nog een andere manier is de Bordatelling, vernoemd naar de wiskundige en politicoloog JeanCharles de Borda. Elke kandidaat krijgt per stem een aantal punten, afhankelijk van de positie in de ordening: een eerste plaats levert  punten op, een tweede plaats , een derde plaats , een vierde plaats  en een vijfde plaats in de ranglijst nog slechts  punt. Hier berekenen we  punten voor A,  voor B,  voor C,  voor D en  voor E, zodat kandidaat D wint!



We voeren nog een laatste methode in, de Condorcetmethode, die niet altijd een winnaar oplevert. Een Condorcetwinnaar is diegene die wint bij vergelijking met alle andere kandidaten in een e´e´n-tegen-´ee´nconfrontatie. Het is echter niet onmogelijk dat kiezers terzelfdertijd een kandidaat X verkiezen boven Y e´n Y boven Z e´n Z boven X. Toch, in ons voorbeeld blijkt E de Condorcetwinnaar; er zijn namelijk  kiezers met een voorkeur voor E > A naast slechts  voor A > E, en analoog halen de opties E > B, E > C en E > D het met een meerderheid. Deze vijf alternatieve kiessystemen lijken allen niet oneerlijk, maar leiden desondanks tot vijf verschillende winnaars! Een voor de hand liggende vraag is dus welk systeem aangewezen is. Een ideale methode zou moeten voldoen aan de volgende natuurlijke eisen of axioma’s. . Unanimiteit: als iedere individuele kiezer een bepaalde optie verkiest boven een andere, dan moet ook de uitslag dit weerspiegelen; . Geen dictator: de uitkomst moet de stemmen van meerdere kiezers in rekening brengen en bijvoorbeeld niet zomaar de voorkeur van e´e´n kiezer overnemen; . Onafhankelijkheid van irrelevante alternatieven: de onderlinge ordening van de keuzeopties in de uitslag mag niet wijzigen door extra opties toe te voegen. Arrow kon echter wiskundig bewijzen dat, bij minstens twee kiezers en minstens drie opties, geen enkel kiessysteem aan deze drie redelijke vereisten kan voldoen! Voor een wiskundige omschrijving noteren we de mogelijke uitkomsten als X = {x1 , . . . , x k } en de verzameling van volledige lineaire ordeningen van X als L(X). Als er n kiezers zijn, is een kiessysteem dan een functie f ∶ L(X)n → L(X), die n lineaire ordeningen samenvoegt tot e´e´n ordening. De drie gewenste eigenschappen laten zich als volgt wiskundig vertalen. . Unanimiteit: als in iedere component van (R1 , . . . , R n ) ∈ L(X)n geldt dat x a > xb , dan moet ook in de finale ordening f (R1 , . . . , R n ) gelden dat x a > xb . . Geen dictator: voor geen enkele index k is het zo dat voor iedere (R1 , . . . , R n ) ∈ L(X)n geldt dat x a > xb in f (R1 , . . . , R n ) telkens als x a > xb in R k . . Onafhankelijkheid van irrelevante alternatieven: voor elke (R1 , . . . , R n ) en (R1′ , . . . , R ′n ) waar opties x a en xb in alle overeenkomstige paren R i en R ′i gelijk geordend worden, moeten x a en xb ook in f (R1 , . . . , R n ) en f (R1′ , . . . , R ′n ) gelijk geordend worden. De stelling van Arrow beweert dat zo’n functie f ∶ L(X)n → L(X) niet aan alledrie de voorwaarden kan voldoen zodra ∣X∣ ⩾  en n ⩾ . In [] worden hier drie bewijzen voor gegeven. In de praktijk blijft de implicatie van dit resultaat beperkt. Arrow gaf zelf toe: “Most systems are not going to work badly all of the time. All I proved is that all can work badly at times.”

[1] K. Arrow, A difficulty in the concept of social welfare. Journal of Political Economy, vol. 58, no. 4, 1950, p. 328–346. [2] J. Geanakoplos, Three brief proofs of Arrow’s impossibility theorem. Economic Theory, vol. 26, no. 1, 2005, p. 211–215.



44

Paradox van Braess

Overvolle wegen en files vormen een wereldwijd probleem, ter dagelijkse ergernis van velen. Een voor de hand liggende suggestie om dit aan te pakken, is het aanleggen van nieuwe wegen tussen centraal liggende steden. Vreemd genoeg kan dit een contraproductief effect hebben: zoals Dietrich Braess zich in  realiseerde, is het mogelijk dat extra capaciteit toevoegen aan een netwerk juist leidt tot een daling van de globale prestatie. We werken een speelgoedmodel uit. Hieronder staan vier steden A, B, X en Y weergegeven. Onderstel dat vierhonderd reizigers van stad A tot in stad B moeten geraken, en dat de enige mogelijke opties de routes A → X → B en A → Y → B zijn. De twee routes A → Y en X → B zijn modernere snelwegen die zes minuten in beslag nemen, ongeacht het aantal pendelaars. Aan de andere kant zijn de routes A → X en Y → B lokale wegen waar de reistijd wel afhangt van de verkeersintensiteit: een minuut voor elke honderd reizigers op de weg.  A

x 

Y

y  B

X



Als x pendelaars de route via X volgen en y pendelaars via Y (waarbij x + y = ), dan kost de eerste route  + x/ minuten en de tweede  + y/ minuten. Als een van deze routes korter was dan de andere, dan zou een rationele bestuurder overschakelen naar deze kortere route. Het systeem is in evenwicht wanneer  + x/ =  + y/, dus wanneer x = y = , in welk geval beide routes acht minuten kosten. Onderstel nu dat er een nieuwe eenrichtingsweg wordt aangelegd vanuit stad X naar stad Y die in slechts e´e´n minuut af te leggen valt. Wat verandert er voor de  reizigers? Sowieso passeert elke route naar B nog steeds langs een van de twee centrale steden. Als e´e´n pendelaar gebruikmaakt van de nieuwe weg en zijn route A → X → B wijzigt naar A → X → Y → B, dan doet hij er nu / +  + / ≈  minuten over, een besparing van drie minuten!  A

Y 

x 

X

y  B 

Uiteraard blijft het daar niet bij: elke reiziger kan opmerken dat de rechtstreekse route A → Y met zes minuten sowieso trager gaat dan A → X → Y, die in het slechtste geval vijf minuten



duurt (voor x = ). Op dezelfde manier valt X → Y → B steeds te verkiezen boven X → B. Iedereen zal dus geneigd zijn om het nieuwe traject A → X → Y → B af te leggen, die nu echter / +  + / =  minuten kost! Bovendien wil niemand de originele routes gebruiken, die / +  =  minuten kosten in deze situatie. Met andere woorden, het toevoegen van een effici¨ente verbinding tussen X en Y resulteert in een globale vertraging van het netwerk. Alle reizigers kunnen een minuut winst maken door af te spreken deze nieuwe weg X → Y niet te gebruiken, maar dan haalt ieder er persoonlijk voordeel uit deze afspraak te schenden; de optimale evenwichtssituatie is dus niet stabiel. Het paradoxale effect van Braess werd wel degelijk ook al vastgesteld in realistische situaties. Zo verliep de verkeersstroom rond Seoul vlotter toen een snelweg werd afgesloten voor restauratiewerken, in Stuttgart ging het verkeer er ondanks investeringen in het wegennet niet op vooruit totdat de nieuw aangelegde weg opnieuw deels werd afgesloten, en de verkeersopstoppingen in New York City namen af na het sluiten van een straat. Ook bij het ontwerp van elektriciteits- of datanetwerken kan de paradox zich voordoen. Om optimistisch af te sluiten, het is geweten ([]) dat het aanleggen van een extra weg in een wegennetwerk de globale reistijd met hoogstens een factor / kan doen achteruitgaan, onder de assumptie dat de reistijd in elke weg lineair is in het aantal weggebruikers (een assumptie die in de praktijk redelijk blijkt).

¨ [1] D. Braess, Uber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, vol. 12, 1969, p. 258–268. ´ Tardos, How bad is selfish routing? [2] T. Roughgarden, E. Journal of the ACM, vol. 49, no. 2, 2002, p. 236–259.



45

Tropische wiskunde

Tropische wiskunde is een exotische en jeugdige theorie, die start vanuit een eenvoudig idee: een herdefini¨eren van optelling en vermenigvuldiging op de re¨ele getallen naar een zwakkere structuur van een zogenaamde semiring. De benaming was oorspronkelijk een eerbetoon van een aantal Franse wiskundigen aan hun Braziliaanse collega Imre Simon, pionier van dit vakgebied. De eerste definities komen ongetwijfeld bizar over, maar er zijn wel degelijk boeiende toepassingen die het geheel motiveren, zowel binnen de zuivere wiskunde als daarbuiten. Zo heeft econoom Paul Klemperer gebaseerd op tropische meetkunde een model voor veilingen opgesteld ([]) dat de Bank of England uit de financi¨ele crisis in  geholpen heeft. De semiring waar deze theorie op steunt is niets meer dan de verzameling R ∪ {∞}, uitgerust met een “tropische optelling” ⊕ en een “tropische vermenigvuldiging” ⊙ als volgt: x ⊕ y = min(x, y),

x ⊙ y = x + y.

Vele vertrouwde eigenschappen van de rekenkunde blijven gelden in deze tropische variant. Zo zijn tropische optelling en vermenigvuldiging nog steeds commutatief en associatief, x ⊕ y = y ⊕ x, x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z,

x ⊙ y = y ⊙ x, x ⊙ (y ⊙ z) = (x ⊙ y) ⊙ z,

en bovendien geldt de distributieve rekenregel x ⊙ (y ⊕ z) = (x ⊙ y) ⊕ (x ⊙ z). De beide bewerkingen hebben een neutraal element. Voor de optelling is dat het element ∞, en—verwarrend genoeg—vervult  de rol van neutraal element voor de vermenigvuldiging. x ⊕ ∞ = x,

x ⊙  = x.

De vermenigvuldiging is inverteerbaar; defini¨eren we de tropische deling x ⊘ y als x − y, dan is  ⊘ y een inverse van y (in de zin dat y ⊙ ( ⊘ y) = ). Optellen echter is een idempotente bewerking (in de zin dat x ⊕ x = x) en is niet langer inverteerbaar; er is bijvoorbeeld geen x die we “drie min e´e´n” kunnen noemen, want de vergelijking x ⊕  =  heeft geen oplossingen! Machten defini¨eren en noteren we op dezelfde manier als in de klassieke rekenkunde. Bemerk dat hier de freshman’s dream (x ⊕ y)n = x n ⊕ y n opgaat, omdat n ⋅ min(x, y) = min(nx, ny). Het wordt pas echt boeiend als we bekijken wat er gebeurt met veeltermen en hun grafieken. Allereerst is een monoom een uitdrukking van de vorm c ⊙ x1n1 ⊙ x2n2 ⊙ ⋯ ⊙ x kn k



die overeenkomt met de klassieke lineaire functie Rk → R ∶ (x1 , x2 , . . . , x k ) ↦ n1 x1 + n2 x2 + ⋯ + n k x k + c.

Een volwaardige veelterm is dan een tropische som van monomen, en betekent zoveel als een minimum van een eindige collectie lineaire functies. Beschouw als voorbeeld een algemene tropische tweedegraadsveelterm in e´e´n veranderlijke, p(x) = a ⊙ x 2 ⊕ b ⊙ x ⊕ c = min(x + a, x + b, c). De grafiek van deze functie bestaat dan hetzij uit twee, hetzij uit drie lineaire componenten (naargelang b − a groter is dan c − b of niet) en heeft dan ook e´e´n of twee “knikpunten”.

b−a c−b

(c − a)/

Uit de grafiek valt een soort gefactoriseerde vorm van p(x) af te lezen; ⎧ ⎪ ⎪ a ⊙ (x ⊕ (b − a)) ⊙ (x ⊕ (c − b)) als b < a + c, p(x) = a ⊙ x ⊕ b ⊙ x ⊕ c = ⎨ 2 ⎪ als b ⩾ a + c. ⎪ ⎩ a ⊙ (x ⊕ (c − a)/) 2

Het is belangrijk om op te merken dat deze factorisatie in lineaire factoren als functie geldt, niet noodzakelijk als polynoom; het product uitwerken via distributiviteit kan tot een andere veelterm leiden, die weliswaar dezelfde functie voorstelt—een fenomeen dat niet optreedt bij klassieke veeltermen. In het tweede geval hierboven kan de parameter b bijvoorbeeld groter gemaakt worden zonder effect op de grafiek, terwijl de veelterm zelf wel wijzigt. In feite geldt een interessant iets algemener resultaat, een equivalent van de hoofdstelling van de algebra voor de tropische wiskunde: elke tropische veelterm van graad n in e´e´n variabele, factoriseert (als functie) op unieke manier in een tropisch product van n lineaire veeltermen en een constante. In meerdere variabelen gaat deze unieke factorisatie niet langer op, want bijvoorbeeld (x ⊕ ) ⊙ (y ⊕ ) ⊙ (x ⊙ y ⊕ ) = (x ⊙ y ⊕ x ⊕ ) ⊙ (x ⊙ y ⊕ y ⊕ ) blijken essentieel verschillende ontbindingen van dezelfde functie in irreduciebele factoren. Desondanks blijven de “knikpunten” in de grafiek cruciaal, en dit motiveert een algemenere



multivariate definitie. We noemen de tropische kromme T (p) geassocieerd aan de veelterm p de verzameling van alle originele punten waar de functie niet lineair is, of equivalent, waar het minimum op minstens twee termen tegelijk bereikt wordt. Deze krommen bestaan zelf ook uit lineaire segmenten, zowel begrensde als onbegrensde. Voor bijvoorbeeld de veelterm p(x, y) = a ⊙ x 2 ⊕ b ⊙ x ⊙ y ⊕ c ⊙ y 2 ⊕ d ⊙ x ⊕ e ⊙ y ⊕ f

(a, b, c, d, e, f ⩾ )

ziet deze kromme T (p) (die we een tropische kegelsnede kunnen noemen) er als volgt uit. Ook hier kunnen bepaalde delen van deze algemene grafiek ineenzakken als de co¨effici¨enten niet aan bepaalde ongelijkheden (b ⩽ a + c, d ⩽ a + f , e ⩽ c + f ) voldoen.

a ⊙ x2

f

d⊙x

e⊙y b⊙x⊙y c ⊙ y2

Terwijl tweedegraadsveeltermen met twee variabelen kegelsneden in het vlak R2 voorstellen, worden rechten beschreven door eerstegraadsveeltermen. Voor de algemene veelterm p(x, y) = a ⊙ x ⊕ b ⊙ y ⊕ c

(a, b, c ⩾ )

ziet de corresponderende rechte eruit zoals hieronder links, met drie halfrechten rondom het centrale punt (c − a, c − b). Merk op dat elke twee generieke punten in het vlak een unieke tropische rechte bepalen, net als in de klassieke meetkunde!

De meetkunde hier is weliswaar subtieler, want twee (tropische) rechten snijden niet noodzakelijk in een uniek punt maar mogelijks in een (Euclidische) halfrechte, wat niet eens een tropische vari¨eteit voorstelt. Dit is tevens de reden waarom twee punten niet automatisch een unieke rechte bepalen. Ondanks deze subtiliteiten is de studie van tropische krommen in R2 best goed ontwikkeld en werden er reeds tropische versies van verscheidene klassieke stellingen tot stand gebracht,



zoals Pappus’ zeshoekstelling, de stelling van B´ezout, de optelwet op elliptische krommen (zie curiosum ??). . . De stelling van B´ezout stelt dat twee krommen van graad d1 en d2 in hoogstens d1 ⋅ d2 punten snijden, en dat de bovengrens in feite bereikt wordt indien geteld met multipliciteit (onder enkele technischere voorwaarden). De onderstaande illustratie in het tropische vlak beeldt een tweedegraads- en een derdegraadskromme af, die inderdaad snijden in zes punten.

De klassieke stelling van Pappus beschouwt negen rechten {a, a ′ , a ′′ , b, b ′ , b ′′ , c, c ′ , c ′′ } met de eigenschap dat alle acht de tripels {a, a′ , a′′ }, {b, b ′ , b ′′ }, {c, c ′ , c ′′ }, {a, b, c}, {a ′ , b ′ , c ′ }, {a, b ′ , c ′′ }, {a ′ , b ′′ , c} en {a ′′ , b, c ′ } concurrent zijn, en beweert dat dan hetzelfde geldt voor de drie rechten {a ′′ , b ′′ , c ′′ }. Onder deze formulering gaat dit resultaat helaas niet langer op voor tropische rechten. c ′′

c′

c

b′ b ′′ b a ′′

a a′

In de beide situaties is er duidelijk extra aandacht nodig om om te gaan met de mogelijkheid dat rechten een segment gemeenschappelijk hebben. [1] A. Gathmann, Tropical algebraic geometry. Jahresbericht der DMV, vol. 108, no. 1, 2006, p. 3–32. [2] J. Richter-Gebert, B. Sturmfels, T. Theobald, First steps in tropical mathematics. Contemporary Math., vol. 377 (Idempotent Mathematics and Mathematical Physics), 2005, p. 289–317. [3] D. Speyer, B. Sturmfels, Tropical mathematics. Mathematics Magazine, vol. 82, no. 3, 2009, p. 163–173. [4] How geometry came to the rescue during the banking crisis. The Guardian, Newton channel, 2013.



46

Conways look-and-say-rij

In een onderhoudend artikel getiteld The weird and wonderful chemistry of audioactive decay ([]) gaf John Conway een verrassend diepgaande analyse van een curieuze rij getallen, die er op het eerste zicht niet eens zo wiskundig uitziet. Herken je het patroon in deze getallen? , , , , , , , , , , . . . Elke volgende term wordt verkregen door de cijfers van de laatste term in groepjes af te lezen. Vanuit de startterm staat er e´e´n 1, dus de volgende term wordt . Er staan twee 1’en, dus de volgende term wordt . Er staan e´e´n 2, e´e´n 1, dus de volgende term wordt , enzoverder. Het proces verklaart ook de naam waaronder de rij bekendstaat—Conway’s look-and-say-rij. Formeel defini¨eren we een “audioactieve operator” ð op reeksen van cijfers, ð(x1k1 x2k2 ⋯ x nk n ) = k1 x1 k2 x2 ⋯ k n x n , waaronder we verstaan dat de schrijfwijze x1k1 x2k2 ⋯ x nk n optimaal is (dus x1 ≠ x2 enzoverder), en waar we via spaties tussen de fragmenten k i x i de afleiding kunnen aanduiden (of parsen). De specifieke rij van Conway wordt dan verkregen door ð te itereren vanuit de startreeks , al is natuurlijk eender welke startwaarde mogelijk. Merk op dat ð() = ! Conway begint zijn analyse met enkele eenvoudige observaties. Bijvoorbeeld, toepassen van ð kan geen fragment van de vorm ax bx doen ontstaan, want deze zou afkomstig moeten zijn van een niet-optimaal-geschreven x a x b = x a+b . In het bijzonder zijn fragmenten x 4 of langer uitgesloten in beeldreeksen. Na nog eens ð toepassen, kunnen dus geen cijfers groter dan  opduiken, tenzij deze al in de startreeks aanwezig waren (als x i of als k i ). Een belangrijk inzicht is dat sommige afleidingen ontbonden kunnen worden in fragmenten die onderling niet verder interageren. We zeggen dan dat de reeks splijt. In symbolen splijt w tot w = u ⋅ v indien ð n (uv) = ð n (u)ð n (v) voor alle n ∈ N. Elementen zonder niet-triviale splijtingen noemen we uiteraard atomen, anders samengestelde elementen. Stelling (Conways kosmologische stelling). Na hoogstens  ð-iteraties splijt elke startreeks tot een samengesteld element opgebouwd uit  mogelijke common elements (op de volgende pagina opgelijst en vernoemd naar de chemische elementen), eventueel aangevuld met twee speciale klassen van transuranic elements die ontstaan uit startcijfers groter dan , • isotopen van plutonium, Pu = n (n ⩾ ), en • isotopen van neptunium, Np = n (n ⩾ ).



. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .



H =  He =  Li =  Be =  B =  C =  N =  O =  F =  Ne =  Na =  Mg =  Al =  Si =  P =  S =  Cl =  Ar =  K =  Ca =  Sc =  Ti =  V =  Cr =  Mn =  Fe =  Co =  Ni =  Cu =  Zn =  Ga =  Ge =  As =  Se =  Br =  Kr =  Rb =  Sr =  Y =  Zr =  Nb =  Mo =  Tc =  Ru =  Rh =  Pd = 

H Hf ⋅ Pa ⋅ H ⋅ Ca ⋅ Li He Ge ⋅ Ca ⋅ Li Be B C N O F Ne Pm ⋅ Na Mg Al Ho ⋅ Si P S Cl Ar K Ho ⋅ Pa ⋅ H ⋅ Ca ⋅ Co Sc Ti V Cr ⋅ Si Mn Fe Zn ⋅ Co Ni Cu Eu ⋅ Ca ⋅ Ac ⋅ H ⋅ Ca ⋅ Zn Ho ⋅ Ga Ge ⋅ Na As Se Br Kr Rb Sr ⋅ U Y ⋅ H ⋅ Ca ⋅ Tc Er ⋅ Zr Nb Mo Eu ⋅ Ca ⋅ Tc Ho ⋅ Ru Rh

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ag =  Cd =  In =  Sn =  Sb =  Te =  I =  Xe =  Cs =  Ba =  La =  Ce =  Pr =  Nd =  Pm =  Sm =  Eu =  Gd =  Tb =  Dy =  Ho =  Er =  Tm =  Yb =  Lu =  Hf =  Ta =  W =  Re =  Os =  Ir =  Pt =  Au =  Hg =  Tl =  Pb =  Bi =  Po =  At =  Rn =  Fr =  Ra =  Ac =  Th =  Pa =  U=

Pd Ag Cd In Pm ⋅ Sn Eu ⋅ Ca ⋅ Sb Ho ⋅ Te I Xe Cs Ba La ⋅ H ⋅ Ca ⋅ Co Ce Pr Nd Pm ⋅ Ca ⋅ Zn Sm Eu ⋅ Ca ⋅ Co Ho ⋅ Gd Tb Dy Ho ⋅ Pm Er ⋅ Ca ⋅ Co Tm Yb Lu Hf ⋅ Pa ⋅ H ⋅ Ca ⋅ W Ta Ge ⋅ Ca ⋅ W Re Os Ir Pt Au Hg Tl Pm ⋅ Pb Bi Po Ho ⋅ At Rn Fr Ra Ac Th Pa



De bovenstaande tabel lijst de  elementen van Conway op, met rechts de elementen waarin ze vervallen. Voor de isotopen geldt daarnaast dat ð(Pu) = Np, ð(Np) = Hf ⋅ Pa ⋅ H ⋅ Ca ⋅ Pu. Met andere woorden, eender welke startreeks evolueert na een aantal stappen naar een combinatie van een eindig aantal vaste elementen en blijft daarna dan ook binnen deze familie. Het exotische atoom  bijvoorbeeld vervalt na acht stappen in hafnium en tin, waarna de rest van de look-and-say-rij volledig uit de klassieke elementen blijft bestaan. , , , , , , ,  ⋅  = Hf ⋅ Sn, . . . De grens van  is scherp. Mike Guy heeft immers exotische elementen gevonden die slechts na  stappen in vertrouwde elementen vervallen (isotopen van “methuselum”, n, vernoemd naar de Bijbelse figuur die een leeftijd van  jaar zou hebben bereikt). John Conway en Richard Parker vonden een compleet bewijs voor de kosmologische stelling via een ingewikkelde reductie naar enkele honderden gevallen, om deze vervolgens allemaal manueel te controleren. Mike Guy vond een iets eleganter bewijs, dat bovendien het element methuselum onthulde, maar nog steeds vele pagina’s in beslag nam. Beide originele bewijzen zijn verloren gegaan. Ondertussen werd het resultaat ook op meerdere manieren computergeverifieerd (zie bijvoorbeeld []). Een indrukwekkend gevolg is dat de lengtes van opeenvolgende termen van de look-and-sayrij naar een vaste verhouding convergeren, zelfs voor eender welke startreeks w verschillend van , namelijk ∣ð n+1 (w)∣ = . . . . = λ. n→∞ ∣ð n (w)∣ lim

De limiet kan worden bepaald uit een eigenwaardenanalyse van een  × -transitiematrix: λ is als grootste eigenwaarde verantwoordelijk voor het asymptotisch gedrag, en is de unieke re¨ele wortel van de veelterm x 71 − x 69 − x 68 − x 67 + x 66 + x 65 + x 64 − x 63 − x 62 − x 61 − x 60 − x 59 + x 58 + x 57 + x 56 − x 55 − x 54 − x 53 − x 52 + x 51 + x 50 + x 49 + x 48 − x 47 − x 46 − x 45 − x 44 + x 43 + x 42 + x 41 − x 40 − x 39 + x 38 − x 37 + x 36 + x 35 − x 34 + x 33 + x 32 − x 31 − x 30 − x 29 − x 28 + x 27 + x 26 − x 25 + x 24 − x 23 − x 21 + x 20 + x 19 − x 18 − x 17 − x 16 + x 15 + x 14 + x 13 − x 12 − x 11 − x 10 + x 9 + x 7 − x 6 + x 5 − x 4 + x 3 − x 2 + x −  als irreduciebele factor van de karakteristieke veelterm.

[1] J. Conway, The weird and wonderful chemistry of audioactive decay. Eureka, vol. 45, 1985, p. 5–18. [2] S. Ekhad, D. Zeilberger, Proof of Conway’s lost cosmological theorem. Electronic Research Announcements, vol. 3, 1997, p. 78–82. [3] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A005150.



46

(todo)

46.1 Mandelbrotfractaal

46.13 Origami

46.2 Phyllotaxis e.d.

46.14 36-officierenprobleem van Euler

46.3 Getal van Graham

46.15 Fractran

46.4 Lorenzattractor

46.16 Taartverdeelproblemen

46.5 Liftparadox van Gamow–Stern

46.17 Hackenbush

46.6 Dilation-free planar graphs

46.18 Chomp

46.7 Chomp

46.19 Rij van van Eck

46.8 Spel van Ducci

46.20 Rij van Thue–Morse

46.9 Tangles van Conway

46.21 Rij van Kolakoski

46.10 Stelling van Jordan + gehoornde sfeer van Alexander

46.22 Rij van Golomb 46.23 Som van kwadraten

46.11 Knoopinvarianten

46.24 Mier van Langton en turmieten

46.12 Meren van Wada

46.25 Game of Life



Quotes

Mathematics is not a careful march down a well-cleared highway, but a journey into a strange wilderness, where the explorers often get lost. Rigour should be a signal to the historian that the maps have been made, and the real explorers have gone elsewhere. William Anglin Id., Mathematics and history, Mathematical Intelligencer, vol. 14, no. 4, 1992, p. 10. There are things which seem incredible to most men who have not studied mathematics. Archimedes D. MacHale, Comic sections, Boole Press, 1993. It was mathematics, the non-empirical science par excellence, wherein the mind appears to play only with itself, that turned out to be the science of sciences, delivering the key to those laws of nature and the universe that are concealed by appearances. Hannah Arendt Ead., The life of the mind, Harcourt, 1971. In the broad light of day mathematicians check their equations and their proofs, leaving no stone unturned in their search for rigour. But at night, under the full moon, they dream, they float among the stars and wonder at the miracle of the heavens. They are inspired. Without dreams there is no art, no mathematics, no life. Michael Atiyah Id., Michael Atiyah collected works: –, Oxford University Press, 2014. “Should you just be an algebraist or a geometer?” is like saying “Would you rather be deaf or blind?” Michael Atiyah Id., Mathematics in the th century, The American Mathematical Monthly, vol. 108, no. 7, 2001, p. 654–666. Mathematics is the gate and key of the sciences. Francis Bacon M. Kline, Mathematics and the physical world, Dover Publications, 1969. “It’s magic,” the chief cook concluded, in awe. “No, not magic,” the ship’s doctor replied. “It’s much more. It’s mathematics.” David Brin Id., Glory season, Orbit, 1993. The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. Gilbert Chesterton Id., Orthodoxy, New York: John Lane co., 1908.

The study of mathematics, like the Nile, begins in minuteness but ends in magnificence. Charles Colton Id., Lacon, or, many things in a few words: addressed to those who think, 1824. A mathematician is a conjurer who gives away his secrets. John Conway Id., Fractran: a simple universal programming language for arithmetic, Open Problems in Communication and Computation, 1987, p. 4–26. Martin Gardner has turned dozens of innocent youngsters into math professors and thousands of math professors into innocent youngsters. Persi Diaconis M. Gardner, The colossal book of mathematics, W. W. Norton, 2001. The life of a mathematician is dominated by an insatiable curiosity, a desire bordering on passion to solve the problems he is studying. Jean Dieudonn´e Id., Mathematics—the music of reason, Springer-Verlag Berlin Heidelberg, 1992. Though he may not always recognize his bondage, modern man lives under a tyranny of numbers. Nicholas Eberstadt Id., The tyranny of numbers: mismeasurement and misrule, American Enterprise Institute, 1995. Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. Paul Erd˝os P. Hoffman, The man who loved only numbers, Hyperion Books, 1998. Mathematics may be likened to a large rock whose interior composition we wish to examine. The older mathematicians appear as persevering stone cutters slowly attempting to demolish the rock from the outside with hammer and chisel. The later mathematicians resemble expert miners who seek vulnerable veins, drill into these strategic places, and then blast the rock apart with well placed internal charges. Howard Eves Id., Mathematical circles squared, Boston: Prindle, Weber and Schmidt, 1972. In elementary and middle school, we hide math’s great masterpieces from students’ view. The arithmetic, algebraic equations and geometric proofs we do teach are important, but they are to mathematics what whitewashing a fence is to Picasso: so reductive it’s almost a lie. Edward Frenkel Id., How our -year-old math curriculum cheats America’s kids, Los Angeles Times, 2014. You can’t think of maths just as this abstract thing that exists only in isolation. I genuinely struggle to find a topic where maths can’t offer you at least some use or insight. Hannah Fry A. Lambert, In conversation with Hannah Fry, Chalkdust Magazine, 2015.



There’s barely any aspect of our modern lives that hasn’t had a mathematical contribution at some point and yet, if you asked the average person, they might think that maths is just difficult, irrelevant and uninteresting. Hannah Fry K. Buchan, Hannah Fry: “There’s a mathematical angle to almost anything”, The Guardian, 2016. Biographical history, as taught in our public schools, is still largely a history of boneheads: ridiculous kings and queens, paranoid political leaders, compulsive voyagers, ignorant generals—the flotsam and jetsam of historical currents. The men who radically altered history, the great scientists and mathematicians, are seldom mentioned, if at all. Martin Gardner G. Simmons, Calculus gems, New York: McGraw Hill, 1992. Math is like ice cream, with more flavors than you can imagine—and if all your children ever do is textbook math, that’s like feeding them broccoli-flavored ice cream. Denise Gaskins Ead., Let’s play math, https://denisegaskins.com. Mathematics is the queen of sciences and number theory is the queen of mathematics. She often condescends to render service to astronomy and other natural sciences, but in all relations she is entitled to the first rank. Carl Friedrich Gauss W. von Waltershausen, Gauss zum Ged¨achtnis, 1856. ‘Recreational mathematics’: an obvious oxymoron to most non-mathematicians, but a pleonasm to true believers. Solomon Golomb Id., Mathematics after forty years of the space age, Mathematical Intelligencer, vol. 21, no. 4, 1999, p. 38–44. A mathematician, like a painter or poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. Godfrey Hardy Id., A mathematician’s apology, Cambridge University Press, 1941. Archimedes will be remembered when Aeschylus is forgotten, because languages die and mathematical ideas don’t. ‘Immortality’ may be a silly word, but probably a mathematician has the best chance of whatever it may mean. Godfrey Hardy Id., A mathematician’s apology, Cambridge University Press, 1941. One of the big misapprehensions about mathematics that we perpetrate in our classrooms is that the teacher always seems to know the answer to any problem that’s discussed. This gives students the idea that there is a book somewhere with all the right answers to all of the interesting questions, and that teachers know those answers. And if one could get hold of the book, one would have everything settled. That’s so unlike the true nature of mathematics. Leon Henkin L. Steen, D. Albers, Teaching teachers, teaching students, Boston: Birkhauser, 1981. In mathematics, our role is more of servant than of master. Charles Hermite J. Hadamard, How I did not discover relativity, Mathematical Intelligencer, vol. 10, no. 2, 1988, p. 65–67.



Mathematics knows no races or geographic boundaries; for mathematics, the cultural world is one country. David Hilbert H. Eves, Mathematical circles squared, Boston: Prindle, Weber and Schmidt, 1972. The art of doing mathematics is finding that special case that contains all the germs of generality. David Hilbert C. Reid, Hilbert, Springer Science & Business Media, 1996. From the intrinsic evidence of his creation, the Great Architect of the Universe now begins to appear as a pure mathematician. James Jeans Id., The mysterious universe, Cambridge University Press, 1930. An elegantly executed proof is a poem in all but the form in which it is written. Morris Kline Id., Mathematics in western culture, George Allen & Unwin Ltd., 1954. It is impossible to be a mathematician without being a poet in soul. Sofia Kovalevskaya I. Hapgood, S´onya Koval´evsky: her recollections of childhood, 1895. Many who have never had an opportunity of knowing any more about mathematics confound it with arithmetic, and consider it an arid science. In reality, however, it is a science which requires a great amount of imagination. Sofia Kovalevskaya I. Hapgood, S´onya Koval´evsky: her recollections of childhood, 1895. It is magic until you understand it, and it is mathematics thereafter. Bh¯arat¯ıkr.s.n.a T¯ırtha K. Williams, M. Gaskell, The Cosmic Calculator, Motilal Banarsidass Publishers, 2002. Number theorists are like lotus-eaters—having tasted this food they can never give it up. Leopold Kronecker H. Eves, Mathematical circles squared, Boston: Prindle, Weber and Schmidt, 1972. Last time, I asked: “What does mathematics mean to you?” Some people answered: “The manipulation of numbers, the manipulation of structures.” And if I had asked what music means to you, would you have answered: “The manipulation of notes?” Serge Lang Id., The beauty of doing mathematics: three public dialogues, Springer Science & Business Media, 2012. There is no branch of mathematics, however abstract, which may not some day be applied to phenomena of the real world. Nikolai Lobachevsky S. Gudder, A mathematical journey, McGraw-Hill, 1976.



Math is the only place where truth and beauty mean the same thing. Danica McKellar Ead., Math doesn’t suck, Hudson Street Press, 2007. The mathematician’s best work is art, a high perfect art, as daring as the most secret dreams of imagination, clear and limpid. Mathematical genius and artistic genius touch one another. G¨osta Mittag-Leffler N. Rose, Mathematical maxims and minims, Raleigh NC: Rome Press inc., 1988. Life is good for only two things, discovering mathematics and teaching mathematics. Sim´eon Poisson F. Arago, Œvres compl`etes de Franc¸ois Arago, vol. 2, 1854. If I feel unhappy, I do mathematics to become happy. If I am happy, I do mathematics to keep happy. Alfr´ed R´enyi P. Tur´an, The work of Alfr´ed R´enyi, Matematikai Lapok, vol. 21, 1970, p. 199–210. We often hear that mathematics consists mainly of ‘proving theorems.’ Is a writer’s job mainly that of ‘writing sentences?’ Gian-Carlo Rota P. Davis, R. Hersh, The mathematical experience, Boston: Birkhauser, 1981. Trying to solve real-world problems, researchers often discover that the tools they need were developed years, decades or even centuries earlier by mathematicians with no prospect of, or care for, applicability. Peter Rowlett Id., The unplanned impact of mathematics, Nature, vol. 475, 2011, p. 166-169. Mathematics, rightly viewed, possesses not only truth, but supreme beauty—a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. Bertrand Russell Id., Mysticism and logic and other essays, George Allen & Unwin Ltd., 1910. Go down deep enough into anything and you will find mathematics. Dean Schlicter M. Joseph, The future of geometry, The Mathematics Teacher, vol. 24, no. 1, 1936, p. 29. Wiskunde is als zuurstof. Als het er is, merk je het niet. Als het er niet zou zijn, merk je dat je niet zonder kunt. Lex Schrijver B. Mols, I. Smeets, Succesformules: toepassingen van wiskunde, Platform Wiskunde Nederland, 2014. The mathematician is fascinated with the marvelous beauty of the forms he constructs, and in their beauty he finds everlasting truth. George Shaw N. Rose, Mathematical maxims and minims, Raleigh NC: Rome Press inc., 1988.



Mathematical reasoning may be regarded rather schematically as the exercise of a combination of two facilities, which we may call intuition and ingenuity. Alan Turing Id., Systems of logic based on ordinals, Proceedings of the London Mathematical Society 2, vol. 45, 1939. Mathematics is the supreme arbiter. From its decisions there is no appeal. We cannot change the rules of the game, we cannot ascertain whether the game is fair. We can only study the player at his game; not, however, with the detached attitude of a bystander, for we are watching our own minds at play. David van Dantzig E. Maor, To infinity and beyond, Princeton, 1991. If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is. John von Neumann F. Alt, Archaeology of computers: reminiscences, –, Communications of the ACM, vol. 15, no. 7, 1972. One of the key characteristics of mathematicians and puzzlers is that they don’t simply give up, they try to prove that it’s impossible. Colin Wright Id., The mutilated chessboard (revisited), Recreational Mathematics Magazine, vol. 1, 2014, p. 4–9.



Index

