SciLogs International .com.be.es.de

Recentste blogposts RSS

Hoe een oneerlijk driehoekspel voor verdelingen zonder afgunst zorgt

16. Juni 2014, 15:55

Het driehoekspel
Als je ooit nog eens vijf minuten tijd hebt, kan je eventueel snel het driehoekspel spelen. Je hebt niet veel nodig, een tegenspeler en een driehoek. Deze laatste moet je wel in een rooster van kleinere driehoekjes onderverdelen, zoals in onderstaande figuur:


Het aantal roosterdriehoekjes mag je zelf kiezen en wordt bepaald door de tijd die je hierin wilt steken (we kozen hierboven voor 36). Je mag dit driehoekrooster wat ons betreft slordig en onregelmatig tekenen, zolang je er maar voor zorgt dat iedere zijde van een klein driehoekje ofwel op een zijde van de grote driehoek ligt, ofwel tot juist 2 driehoekjes behoort.

Het spel verloopt eerlijk gezegd vrij saai. Vooraf worden op de 3 hoekpunten van de grote driehoek willekeurig 3 labels geplaatst, die we droogweg A, B en C zullen noemen. Om de beurt moet iedere speler nu verder een van deze 3 letters aan een nog vrij hoekpunt toekennen. Uiteraard mag hij geen letters weggommen of overschrijven. Wanneer alle hoekpunten uiteindelijk bezet zijn, stopt het spel en bepaalt de hieronder beschreven puntenverdeling wie de winnaar is. Let op, er is een eenvoudige regel die tijdens het spel in acht moet worden genomen: de hoekpunten op een zijde van de grote driehoek mogen enkel een van beide letters krijgen die voor de eindpunten van deze grote zijde gekozen zijn. Dit is bijvoorbeeld een tussentijdse spelsituatie:


Wie wint het spel? Bij de eindafrekening worden enkel de driehoekjes beschouwd die de 3 letters (A, B, C) op hun hoekpunten hebben staan. Op de hoekpunten van deze “kredietwaardige” driehoekjes verschijnt de alfabetische volgorde A-B-C ofwel in wijzerzin, ofwel in tegenwijzerzin. Voor het spel begint, werd afgesproken welke speler een punt krijgt in het eerste geval, persoon Wijzerzin (W) genoemd, en welke speler een punt krijgt in het tweede geval, persoon Tegenwijzerzin (T) genoemd. In de tussenstand van het driehoekspel hierboven afgebeeld, heeft T al 2 punten, maar W slechts 1.

Het lemma van Sperner
Dit is het moment om de Duitse wiskundige Emanuel Sperner (1905-1980) op te voeren. Hij heeft de hierboven beschreven driehoekjes en labels gebruikt om op een aanschouwelijke en combinatorische manier moeilijke topologische vraagstukken te bestuderen en op te lossen.


(geleend van de fotocollectie van Oberwolfach)

Sperner ontdekte een verrassende eigenschap, die nu bekend staat als Het lemma van Sperner, en die in de terminologie van het bovengenoemde driehoekspel de volgende ontnuchterende formulering kent:

Onafhankelijk van het spelverloop zal speler T altijd winnen met 1 punt voorsprong op speler W.

De winnaar wordt dus bepaald door de startplaatsen voor de letters op de hoekpunten van de grote driehoek. Moesten we hierboven A-B-C in wijzerzin geplaatst hebben, dan zou speler W gegarandeerd winnen (met 1 punt voorsprong op speler T). Merk op dat het Lemma van Sperner de volgende onthutsende implicatie heeft (meestal zelf bekend als het Lemma van Sperner):

Als je het driehoekspel helemaal uitspeelt, dan zal het aantal roosterdriehoekjes met de 3 letters op de hoekpunten altijd oneven zijn. Er is er dus minstens 1.


Terzijde merken we op dat geavanceerde spelers ook op een tetraëder kunnen spelen, maar dan met 4 letters (A, B, C, D) op de 4 hoekpunten. Het driedimensionale speelbord wordt in dit geval onderverdeeld in kleine tetraëders. De regels zijn analoog, dus de rasterhoekpunten op de ribbe met eindpunten gelabeld door bijvoorbeeld A en B mogen enkel een A of een B krijgen, en de rasterhoekpunten in bijvoorbeeld het zijvlak A-B-C mogen enkel een A of een B of een C krijgen. Wie het praktisch weet te organiseren, kan zelfs in een wereld met een willekeurig aantal dimensies n spelen, op een n-simplex met (n+1) letters. Ook in deze hoog dimensionale context kan het Lemma van Sperner geformuleerd en bewezen worden.

De motivatie van Sperner achter dit lemma was het vinden van een elementair bewijs voor een niet zo voor de hand liggende topologische stelling, met name het overdekkingstheorema van Lebesgue. Maar achteraf bleek zijn lemma niet enkel een korte observatie over een spelletje in een driehoek, maar ook een krachtige bron voor vele toepassingen en andere elementaire bewijzen. De fameuze dekpuntstelling van Brouwer bijvoorbeeld kan redelijk snel aangetoond worden met behulp van het lemma van Sterner. Toegepast op een driehoek zegt deze stelling (informeel) dat als we de punten van een driehoek in beweging brengen, zonder de driehoek te verlaten, dat er dan op ieder moment noodzakelijkerwijs een punt stil staat. Volgens de overlevering kwam Brouwer op het idee van zijn dekpuntstelling tijdens het roeren in een kop koffie.


Sterk gerelateerd hieraan is het bestaan van het zogenaamde Nash-evenwicht in sommige spelen of marktsituaties (herlees onze eerdere blogpost over speltheorie).

Afgunstvrije verdelingen
Maar misschien de meest verrassende, zo niet dan toch de leukste toepassing van het lemma van Sperner is de garantie op het bestaan van een afgunstvrije verdeling van ongelijke stukken tussen deelnemers met verschillende voorkeuren. Een herkenbaar voorbeeld is de verdeling van de maandhuur van een studentenkot onder meerdere studenten in het geval van verschillende kamers. De ene zal de grootste kamer verkiezen, de andere misschien de kamer met een lavabo. Iemand zal allicht tevreden zijn met de kleinste kamer op voorwaarde dat de anderen meer betalen. Het lemma van Sperner heeft als eigenaardige implicatie dat de maandhuur altijd kan verdeeld worden, en ook de kamers, zodat iedere student bij deze prijsafspraak de kamer van zijn voorkeur krijgt.

We leggen dit uit aan de hand van een eenvoudiger voorbeeld. Stel dat we een taart moeten verdelen onder een aantal personen. We beperken ons tot 3 gasten om te vermijden dat we het lemma van Sperner in hogere dimensies moeten gebruiken. Het kan zijn dat iemand hoe dan ook het grootste stuk wil, terwijl iemand anders eerder een gecompliceerde relatie heeft met zijn weegschaal. Of wil er iemand vooral het stuk met de kers? Kunnen we de taart verdelen en iedere gast een stuk geven zonder afgunst te creëren? Ja, dat kunnen we! Of beter gezegd, het lemma van Sperner kan dat.

Om dit te begrijpen benoem je de 3 taartstukken van links naar rechts met de letters van ons driehoekspel: A, B, C. Opnieuw plaatsen we de deze drie letters op de hoekpunten van de grote driehoek. Ieder proportionele verdeling tussen stukken A, B en C kan voorgesteld worden als een punt in de driehoek.

bary2

Bijvoorbeeld als we onze eerste snede in de helft kiezen en de tweede in de helft van het resterende deel, dan bevat A 50% van de taart, B en C 25%. Het bijhorende punt in de driehoek ligt dan op positie 1/2A + 1/4B + 1/4C, of, voor de kenners, het punt met barycentrische coördinaten (1/2,1/4,1/4). Ook omgekeerd refereert ieder punt in de driehoek naar een unieke A-B-C verdeling.
Bijvoorbeeld het zwaartepunt van de driehoek komt overeen met de verdeling met 3 even grote stukken. We laten ook toe dat A of B of C gewoon niets is (een “leeg stuk”). Deze spijtige verdelingen worden geassocieerd met punten op de rand van de driehoek. Zo komt het midden van zijde [BC] overeen met een verdeling waarvoor A een leeg stuk is en B en C juist de helft. De hoekpunten van de driehoek verwijzen naar de meest absurde taartverdeling: hoekpunt A bijvoorbeeld is een verdeling waarbij deel A uit de hele taart bestaat, en lege delen B en C.

Vervolgens verdelen we de driehoek in een raster van kleine driehoekjes (zoals in het spel). Het aantal roosterdriehoekjes speelt voorlopig geen rol. Elk hoekpunt van deze driehoekjes krijgt een van drie mogelijke kleuren. Kies bijvoorbeeld rood, geel en groen, zoals hieronder:



Merk op dat de hoekpunten van ieder roosterdriehoekje telkens drie verschillende kleuren dragen. Dit kunnen we altijd zo regelen (denk hier straks eens over na, maar nu eerst verder lezen). Iedere kleur codeert een taarteter: Mevrouw Rood, mijnheer Geel en mevrouw Groen. Zoals hierboven uitgelegd, stellen al deze roosterhoekpunten een taartverdeling voor. In elk van deze hoekpunten stellen we aan de persoon met de overeenkomstige kleur de vraag welk deel hij of zij prefereert: A, B of C (in geval van meerdere favoriete stukken moet de knoop toch doorgehakt worden).

 

Nu is het tijd voor een veronderstelling, zo gaat dat bij wiskundige resultaten, al gaat het hier om een redelijke voorwaarde:

De hongerhypothese: iedere persoon heeft toch een beetje honger, dus een leeg deel zal nooit geprefereerd worden.

De “kleurverantwoordelijke” van een roosterhoekpunt op bijvoorbeeld zijde [AB] zal dus ofwel voor A opteren, ofwel voor B, nooit voor het lege deel C. En mijnheer Rood zal in het hoekpunt van de grote driehoek altijd voor de letter kiezen die bij de start hier geplaatst werd, omdat dit verwijst naar het enige niet lege deel bij de overeenkomstige (absurde) taartverdeling. Wat ons betreft mag je de kleuren nu vergeten, maar schrijf wel bij ieder roosterpunt de keuze (A of B of C) die hier gemaakt werd. Uit de hongerhypothese volgt dat we op deze manier een eindsituatie krijgen van het driehoekspel. Het lemma van Sperner garandeert dus het bestaan van minstens 1 driehoekje waar de drie taarteters in hun hoekpunt een ander deel kiezen. We noemen dit een afgunstvrij driehoekje.

Maar we zijn er nog niet, want de verschillende voorkeuren horen bij verschillende roosterpunten en slaan daarom op verschillende verdelingen. Dus we hebben nog geen afgunstvrije verdeling gevonden. Maar de vorige redenering gaat natuurlijk ook op als we een hele fijne driehoekige rastering gebruiken, met desnoods een miljoen minuscuul kleine driehoekjes. We zouden dan wel geen plaats meer hebben om onze letters A-B-C te schrijven, maar het idee blijft gelden, zelfs als de driehoekjes zo klein worden dat de 3 taartverdelingen in de hoekpunten van zo’n roosterdriehoekje praktisch identiek zijn, omdat het verschil in de A-delen minder dan een deegkruimeltje is, en zo ook voor de andere delen. Als we dan een afgunstvrij driehoekje selecteren, vinden we uiteindelijk een verdeling (gelijk aan de min of meer gelijke verdelingen in de hoekpunten van dit driehoekje) waarbij Rood, Geel en Groen verschillende stukken prefereren! Om echt tot een wiskundig punt te komen, zodat we de terminologie “min of meer” uit de vorige zin niet hoeven te gebruiken, is er nog een formeel limietargument nodig en een extra voorwaarde, maar we hopen dat we de lezer nu al overtuigd hebben.


Opgelet: Het lemma van Sperner mag dan wel het bestaan van een afgunstvrije verdeling garanderen, maar het zegt ons niet hoe we zo'n verdeling vinden. Commentaar en hints zijn meer dan welkom!

Een “bewijs uit het boek” voor het lemma van Sperner
Nu we getoond hebben hoe een eenvoudige maar verrassende eigenschap over de labels in het driehoekspel een brede waaier van consequenties biedt, is het niet minder dan onze burgerplicht om de meerwaardezoekende lezer uit te leggen waarom het lemma van Sperner eigenlijk waar is. Een bewijs dus. En niet zomaar een bewijs. We geven een kristalhelder elegant argument dat zelfs bij een niet-wiskundige dopamine doet vrijkomen (of toch zeker een glimlach) tijdens de haha-beleving.

Gegeven is dus een onderverdeling van een driehoek in kleine driehoekjes waarvan de hoekpunten een label A of B of C dragen volgens de regels van het driehoekspel. Dan kunnen we binnen ieder driehoekje iedere zijde een nummer geven, -1 of 0 of 1, volgens het volgende systeem. Als de eindpunten van de zijde dezelfde letter dragen dan kiezen we nummer 0 voor deze zijde. Als de letters verschillend zijn, dan geeft de alfabetische volgorde van deze letters deze zijde een richting die voor het betreffende driehoekje met wijzerzin of tegenwijzerzin overeenkomt. Is dit tegenwijzerzin (= de A-B-C volgorde voor de hoekpunten van de grote driehoek), dan kiezen we nummer 1, anders -1. Zoals hieronder:



Iedere roosterzijde in het inwendige van de grote driehoek krijgt dus twee nummers, een voor elk driehoekje waartoe de zijde behoort, terwijl een rasterzijde die op de zijde van de grote driehoek ligt, maar één nummer krijgt. We maken onmiddellijk enkele observaties voor deze nummering:

  • De 2 nummers aan weerszijde van een inwendige roosterzijde zijn ofwel beide 0, ofwel -1 en 1.
  • De totale som van de nummers van alle roosterzijden op een grote driehoekzijde bedraagt juist 1. Inderdaad, doorloop bijvoorbeeld de roosterzijden op zijde [AB], startend bij A. We komen enkel A en B tegen in de roosterhoekpunten op [AB]. Zolang we A blijven tegenkomen, hebben we enkel nummer 0 op de roosterzijde. Een overgang naar B geeft nummer 1, maar iedere terugkeer naar A geeft dan weer nummer -1, zodat het tussenresultaat van de som steeds 0 is in een roosterpunt met label A, en 1 in een roosterpunt met label B. Omdat we op het einde van zijde [AB] in B landen, is de totale som voor deze zijde dus 1.


  • Als we in een roosterdriehoekje de 3 nummers van de zijden optellen dan hebben we 0 als er een letter meermaals voorkomt in de betreffende hoekpunten. Voor driehoekjes met 3 verschillende labels geeft dit “driehoekgetal” 3 als A-B-C in tegenwijzerzin voorkomt, en -3 in het andere geval.
Het bewijs van het lemma van Sperner is nu een simpele teloefening. We bereken namelijk

S = som van de driehoekgetallen van alle roosterdriehoekjes

Een seconde nadenken doet ons beseffen dat dus

S = som van alle nummers naast de roosterzijden

Maar omdat de nummers bij inwendig zijden in paren voorkomen die tegen elkaar wegvallen in de som (wegens beide 0, of beide tegengesteld), besluiten we dat

S = som van alle nummers op de roosterzijden die op de rand van de grote driehoek liggen

En dus S = 3, want de som per zijde is gelijk aan 1. Maar S is een som van driehoekgetallen, elk gelijk aan 0 of 3 of -3. Het aantal roosterdriehoekjes met driehoekgetal 3 is dus eentje meer dan de roosterdriehoekjes met driehoekgetal -3.

Persoon Tegenwijzerzin wint dus altijd het driehoekspel met juist 1 punt voorsprong op persoon Wijzerzin. Quod erat demonstrandum.

Leestip en hoofdbron
F. E. Su, Sperner’s Lemma in Fair Division, Amer. Math. Monthly, 106 (1999), 930-942. 


Geschreven in Algemeen | 0 Reacties | Vaste link | Afdrukken


Doe de test en win! Krijg jij het koud of warm bij deze twaalf stellingen?

16. Mei 2014, 14:33

boekbesprekingen Enkele maanden geleden heb je het al kunnen lezen in de kranten: een onderzoek door enkele neurobiologen wijst uit dat mooie wiskundige formules hetzelfde deel van de hersenen triggeren als een mooi schilderij. Het artikel, dat verscheen in het tijdschrift Frontiers in Human Neuroscience, beschrijft hoe 60 wiskundige formules voorgelegd werden aan 15 wiskundigen tijdens een hersenscan. De wiskundigen hadden op voorhand de formules gerangschikt van mooi naar lelijk. Bij het bekijken ervan was er heel wat activiteit op verschillende plaatsen in de hersenen, maar als het om een speciaal mooie vergelijking ging, dan lichtte de orbifrontale cortex op, het deel van de hersenen dat ook actief is bij het bekijken van prachtige schilderijen en het beluisteren van mooie muziek.
Ik heb het niet kunnen laten even een blik te werpen op de formules in kwestie, en dan blijkt dat het natuurlijk wel erg belangrijk is te weten dat het experiment gedaan is met wiskundigen. Ik kan me voorstellen dat velen van jullie het niet warm en koud krijgen bij het zien van de volgende wiskundige vergelijking:

Diffusievergelijking

Dit is de zogenaamde diffusievergelijking in 1 dimensie, een partiële differentiaalvergelijking die niet erg veelzeggend is zonder wat uitleg. De volgende vergelijking zal waarschijnlijk wel gevoelens oproepen:

mineentwaalfde
 
maar dan eerder weerstand en ongeloof. Nochtans is wat hier staat erg in op dit ogenblik, en het is inderdaad in zekere zin waar als speciaal geval van een vergelijking die ook voorkomt in het lijstje van 60, namelijk de functionaalvergelijking voor de Riemann-zetafunctie:

functionaalvergelijking zetafunctie

Weinig mensen zullen zich opwinden over deze vergelijking, maar voor s gelijk aan -1 staat er eigenlijk hetzelfde. (Het filmpje op Numberphile laat overigens wat te wensen over omdat het de zaken niet goed kadert. Er kwam dan ook de volgende terechte reactie op: een heel groot deel van de bevolking zal na het zien ervan zeker gaan veronderstellen dat wiskunde tegenintuïtief is, en meer tovenarij dan iets anders, en dat is geen goede zaak.)

In 1988 heeft wiskundige David Wells de wiskundige wereld al eens onderworpen aan een soortgelijke test, niet om de reacties in de hersenen te testen, maar gewoon om de voor wiskundigen mooiste wiskundige formule te vinden. De lezers van het tijdschrift The Mathematical Intelligencer kregen een lijstje met 24 wiskundige stellingen die ze een score voor schoonheid moesten geven tussen 0 en 10. Er kwamen 68 goed ingevulde formulieren bij hem terug binnen. Een deelnemer had elke stelling score 0 gegeven, en hij gaf als commentaar: Wiskunde is een instrument. Kunst heeft schoonheid.
Dit laatste is dus duidelijk niet waar, blijkt uit het recente onderzoek.

DOE MEE EN WIN EEN BOEK!

We nemen de proef op de som. Ik geef hier een lijstje met een aantal stellingen uit de wiskunde, telkens met een woordje uitleg. En als er stellingen bij zijn waar jullie iets bij voelen, dan had ik het graag gehoord in een reactie. Als je reageert, geef dan ook je eigen rangschikking van deze stellingen, van mooist naar lelijkst. Ze hebben allemaal een rangnummer. Uiteraard heb ik een keuze moeten maken, en daarin heb ik me laten leiden door de eenvoud van het resultaat. Onder de inzendingen wordt een boek verloot, meer bepaald het prachtige, recent verschenen werk Wiskunde in beeld, van Glaeser en Polthier, dat we hier besproken hebben. Indien je vindt dat er nog andere stellingen zijn die erg mooi zijn, dan mag je dat ook laten weten natuurlijk. Op 15 juni wordt het boek verloot onder de binnengekomen reacties.



Stelling 1.

Oneindig veel priemgetallen

Deze eerste stelling vraagt niet veel uitleg. Ze is reeds 2000 jaar oud, en ook het aantonen ervan is niet zo lastig, hier vind je twee bewijzen.
Op een gelijkaardige manier kan je bewijzen dat er oneindig veel priemgetallen zijn die één meer zijn dan een viervoud, en dat is nuttig om te weten, anders is de volgende stelling niet zo indrukwekkend.



Stelling 2.

somkwadraten

Het gaat hier natuurlijk om de som van de kwadraten van twee gehele getallen.
Enkele voorbeelden:

13 is een priemgetal en 13 (= een viervoud + 1) is als volgt te schrijven als de som van twee kwadraten: 13 = 22 + 32

29 is een priemgetal en 29 (= een viervoud + 1) is als volgt te schrijven als de som van twee kwadraten: 29 = 22 + 52

17021 is een priemgetal en 17021 (= een viervoud + 1) is als volgt te schrijven als de som van twee kwadraten: 17021 = 112 + 1302

De stelling zegt niet dat er geen andere getallen te schrijven zijn als de som van twee kwadraten:

377 is geen priemgetal en is te schrijven als 377 = 42 + 192 = 112 + 162

En we hebben ook:

21 is geen priemgetal en is niet te schrijven als de som van twee kwadraten

23 is een priemgetal en 23 (= een viervoud + 3) is niet te schrijven als een de som van twee kwadraten

Maar welk priemgetal je ook neemt, als het een eenheid meer is dan een viervoud, dan kan je twee gehele getallen vinden waarvan de som van de kwadraten precies gelijk is aan dit priemgetal. Deze stelling wordt toegeschreven aan Pierre de Fermat (1601-1665).



Stelling 3.

5 regelmatige veelvlakken

Veelvlakken zijn ruimtelijke objecten die aan alle kanten begrensd worden door delen van vlakken. De regelmatige veelvlakken worden gekenmerkt door regelmaat: al hun zijvlakken zijn even groot en hebben dezelfde vorm, nl. die van een regelmatige veelhoek. Bovendien komen er in elk hoekpunt van zo'n regelmatig veelvlak ook evenveel zijvlakken samen. De Griekse wijsgeer Plato wist al dat er zo precies 5 zijn. Dit zijn ze alle vijf:

Platonische lichamen



Stelling 4. De vierkleurenstelling

Oneindig veel priemgetallen

Deze bekende stelling werd in 1976 bewezen ... m.b.v. de computer. De formulering hierboven is iets te los, er zijn wel degelijk beperkingen: de landen op de landkaart mogen geen enclaves hebben, want dan kom je soms niet toe met vier kleuren. Voor een interessant boek over deze stelling: lees hier, p. 7-8.
Leuk om te weten in dit kader is dat Martin Gardner, die we al vaker zijn tegengekomen in deze blog, in 1975 als aprilgrap in Scientific American een kaart publiceerde die (volgens hem) niet met 4 kleuren te doen was. 



Stelling 5. De formule van Euler voor veelvlakken

Formule van Euler

Om een voorbeeld te geven: neem het eenvoudige geval van een kubus. Een kubus heeft 8 hoekpunten (H=8), 12 ribben (R=12) en 6 zijvlakken (Z=6) en dus zien we dat H-R+Z=2.
Dat de formule waar is, is eerst opgemerkt door Leonhard Euler
(1707-1783) in 1750.
Deze stelling is vooral bekend dankzij het boek Proofs and Refutations van de filosoof Imre Lakatos, die haar als voorbeeld gebruikt van hoe wiskunde evolueert.
Eigenlijk geldt de formule van Euler enkel voor sferische veelvlakken. Dit zijn veelvlakken die als ze van rubber gemaakt worden tot een bal kunnen opgeblazen worden. Hieronder valt niet het volgende voorbeeld:

Torus

dat een torisch veelvlak genoemd wordt. Tel maar na: H-R-Z = 0!



Stelling 6. De vaste-puntstelling van Brouwer

Dekpuntstelling

Deze lastig klinkende stelling wordt heel duidelijk met een figuur: in de linkse figuur zie je een vierkant met een diagonaal ervan.

Vierkant Vierkant

Kies nu op elk van beide opstaande zijden een willekeurig punt (je ziet een mogelijke keuze in de figuur links, de rode punten).
De stelling zegt dan het volgende: als je probeert het linkse punt te verbinden m.b.v. een (gebogen) lijn met het rechtse punt, en je zorgt ervoor dat je je pen niet opheft en ook niet buiten het vierkant gaat, dan zal die lijn altijd de diagonaal snijden. Zie voor een voorbeeld de rechtse figuur.
De stelling van Brouwer heeft veralgemeningen in hogere dimensies. Een voorbeeld ervan is de Harige Bal Stelling. Andere toepassingen: in drie dimensies is het een gevolg van deze stelling dat er op aarde op elk ogenblik minstens twee plaatsen zijn met dezelfde temperatuur én luchtdruk.




Stelling 7. De stelling van Morley

Stelling van Morley

Met trisectrices worden de rechten bedoeld die een hoek van de gegeven driehoek in drie gelijke delen verdelen. 'Aanliggend' wordt hier gebruikt in de zin van 'aanliggend aan dezelfde zijde van de gegeven driehoek'. Zie de volgende figuur:

Morley

Deze stelling dateert van 1899, wat erg recent is voor zo'n eenvoudige meetkundige stelling.




Stelling 8. De laatste stelling van Fermat

Laatste stelling


Hierbij mogen a, b en c niet gelijk zijn aan 0.
Waarschijnlijk is dit na de stelling van Pythagoras de bekendste stelling uit de wiskunde. Het bewijs liet honderden jaren op zich wachten, en kwam er eindelijk in 1994. Gevolg is dat deze stelling nog niet is opgenomen in de lijst van David Wells, want toen was het nog geen stelling.

Fermat




Stelling 9. De grondformule van de goniometrie

Pythagoras

Dit is natuurlijk een vermomde versie van de stelling van Pythagoras. Zie figuur. De som van de kwadraten van de twee rechthoekszijden (respectievelijk de cosinus en de sinus van de hoek θ) is gelijk aan het kwadraat van de schuine zijde, 1 in dit geval.

driehoek




Stelling 10. Het Baselprobleem

Basel

Deze stelling, die eerst bewezen werd door Leonhard Euler, zegt dat de oneindige som van de omgekeerden van de kwadraten van de natuurlijke getallen gelijk is aan een eindig getal, meer bepaald het getal π2/6 .



Stelling 11. De verjaardagenparadox

Verjaardagenparadox

Dit onwaarschijnlijke resultaat is eenvoudig na te gaan. In de volgende figuur krijg je meer informatie. In een groep van 57 mensen is de kans zelfs groter dan 99%.

tabel




Stelling 12. De formule van Vieta

Vieta

oftewel het getal π geschreven met uitsluitend tweeën. Deze formule is een van de oudste (oneindige) uitdrukkingen voor het getal π. De methode waarmee François Viète (1540-1603) deze formule afleidde is dezelfde als die welke Archimedes al gebruikte om zijn benaderingen voor het getal π te vinden, met behulp van aan een cirkel omschreven en ingeschreven veelhoeken.



We houden het hierbij. Maar laat het duidelijk zijn dat er nog vele andere zijn.
We maken van de gelegenheid gebruik om nog wat boeken voor te stellen. Een boek dat perfect past in deze blog is het prachtige boek Beautiful Geometry van Eli Maor en Eugen Jost. Het is een samenwerking tussen wiskundige
Eli Maor (zie ook hier), en kunstenaar Eugen Jost. Deze laatste is gefascineerd door wiskunde en veel van zijn kunstwerken dragen er dan ook de sporen van. De uitgever van het boek was zo vriendelijk me enkele van de afbeeldingen uit het boek te bezorgen.
De eerste hoort bij hoofdstuk 8 over Pythagoreïsche drietallen:

Jost1

Je ziet de bekende (3,4,5)-rechthoekige driehoek, en de vier cirkels die raken aan de drie zijden ervan.
De volgende figuur hoort bij het hoofdstuk over de gulden snede. Als je er op klikt, dan krijg je een vergroting.

hfdstk 21

En hier zie je versies van Steiner's Porism:

hfdstk39

En tot slot een illustratie van onze stelling 7:

hfdstk48


Maor en Jost

Eli Maor en Eugen Jost,
Beautiful Geometry. Princeton University Press (2014) 187 pagina's. 

Dit coffee table book is een aanrader voor iemand met interesse voor wiskunde. Het is opgebouwd uit 51 korte hoofdstukken, maar een paar bladzijden lang, telkens voorzien van een prachtige illustratie van de hand van Jost. Vaak gaat het om meetkundige stellingen. Het boek draagt dan wel de titel Prachtige meetkunde, niet alle behandelde onderwerpen zijn even duidelijk meetkunde. Er is bijvoorbeeld ook een hoofdstuk over de harmonische reeks, over het getal e, en over het diagonalisatieprocedé van Cantor waarmee de aftelbaarheid van verzameling van de rationale getallen wordt bewezen.
Achteraan in het boek staan bewijzen van enkele stellingen uit het boek.

Formuledichtheid: Θ Ο Ο Ο Ο
Moeilijkheidsgraad: Θ Ο Ο Ο Ο
Score: Θ Θ Θ Θ Ο



Het volgende boek is iets helemaal anders. Bij de hiervoor genoemde stellingen zijn er enkele die in het domein van de getaltheorie zitten (stellingen 1, 2 en 8). Recent verscheen er een boek dat een overzicht geeft van de meest eenvoudige dingen uit de getaltheorie via een historische kadering. De 'meest eenvoudige dingen' zijn echter niet altijd eenvoudig. Je vindt in het boek bijvoorbeeld de bewijzen van stellingen 1 en 2, maar niet van stelling 8, want voor dat bewijs is niet genoeg plaats in het boek. Maar je krijgt ook over deze laatste stelling van Fermat veel achtergrondinformatie. Zo is er een hoofdstuk over Sophie Germain, waarin haar pogingen om deze stelling te bewijzen uit de doeken worden gedaan. Hier zie je een stukje uit een brief die Germain in 1813 in dit verband schreef naar de grote Gauss (klik voor een vergroting).

Germain to Gauss


Watkins

John J. Watkins,
Number Theory. A Historical Approach. Princeton University Press (2014) 576 pagina's. 

Dit boek geeft de geschiedenis van de getaltheorie, van de Babylonische kleitabletten tot de cryptografie in de twintigste eeuw (RSA). Het is zeker niet bedoeld voor de niet-wiskundige maar de auteur slaagt er wonderwel in alles op een erg duidelijke manier te brengen. Het boek is doorspekt met interessante oefeningen die nauw aansluiten bij wat er in het corresponderende hoofdstuk is verteld. Achteraan in het boek vind je hints bij een aantal van die oefeningen, en ook oplossingen van een groot deel ervan. Je krijgt er ook nog een inleiding op het programma Sage, een online computerprogramma dat met grote getallen kan werken en waar je zelf mee kan experimenteren. Ook nog suggesties voor verdere lectuur, en een lijst van de wiskundigen die in het boek voorkomen en hoe je hun naam (als Engelssprekende) correct uitspreekt (bijvoorbeeld soh FEE zhehr MEHN).
Een aanrader voor lezers met een wiskunde-achtergrond die bijvoorbeeld wat meer willen weten over priemgetallen.

Formuledichtheid: Θ Θ Θ Ο Ο
Moeilijkheidsgraad: Θ Θ Θ Ο Ο
Score: Θ Θ Θ Θ Ο




Geschreven in Actuele wiskunde | 11 Reacties | Vaste link | Afdrukken


De repititieve aard van 3,14

14. Maart 2014, 08:18

Naar jaarlijkse traditie (de vorige versie vind je hier) presenteren we hier ter lering en vermaak opnieuw een hele resem $\pi$-weetjes.

pi cartoon

Wist je al ...
  • $\ldots$ dat het vandaag 14 maart $\pi$-dag is? Waarom? Omdat in de Amerikaanse schrijfwijze de datum 14 maart genoteerd wordt als 3/14 en 3,14 is een benadering voor het getal $\pi$.
  • $\ldots$ dat we dit jaar uitzonderlijk een volledige $\pi$-maand hebben: 3/14 ?
  • $\ldots$ dat je vandaag taart moet eten? Of iets wat er op gelijkt? Zoals dit, de traktatie vorig jaar van ons toenmalige departementshoofd (bedankt, Martine!):
pie

  • $\ldots$ dat er absoluut geen regelmaat of periode zit in de decimalen van het getal $\pi$? Er is dan ook geen breuk met gehele teller en noemer te vinden die als waarde $\pi$ heeft.

    pi

  • $\ldots$ dat het geen zin heeft al deze decimalen van buiten te leren? Enkele decimalen kennen is voor de meeste toepassingen voldoende. Als je er 39 kent dan kan je de omtrek berekenen van het heelal met als nauwkeurigheid de grootte van een waterstofatoom.
  • $\ldots$ dat er een voorstel is om de eenheid kg te definiëren met behulp van een perfecte bol? In dit geval zou dus het getal $\pi$ een rol gaan spelen in de definitie van de kg. Op de figuur zie je zo'n bol, gemaakt van silicium:

    kg

    De diameter is 93,6 mm, met een nauwkeurigheid van 0,6 nm.
  • $\ldots$ dat je in het Guinness Book of Records kan komen als je voldoende decimalen van $\pi$ uit je hoofd kan opzeggen? Het record staat op dit ogenblik op naam van Chao Lu (China) die $\pi$ kan opzeggen tot 67 890 plaatsen na de komma. Hij deed dit op 20 november 2005. De recordpoging duurde 24 uur en 4 minuten.
  • $\ldots$ dat er onduidelijkheid is over wat een pi-ku nu precies is. Volgens sommigen is het een haiku over het getal $\pi$, zoals deze:

    pi-ku

    Volgens anderen is het zoals een haiku, maar met 3 regels, de eerste regel bestaat uit 3 lettergrepen, de tweede uit 1, de derde uit 4. Zoals in dit cirkelgedicht:
    Omtrek is
    pi
    maal straal maal 2
  • $\ldots$ dat Ludolph Van Ceulen (1540-1610), een Duits wiskundige, een groot deel van zijn leven spendeerde aan het (met de hand) uitrekenen van decimalen van $\pi$? Hij deed dit met de methode van Archimedes en geraakte tot aan de 35ste decimaal. Daarom wordt $\pi$ ook het Ludolfiaans getal genoemd.

    lvc

  • $\ldots$ dat de Indische wiskundige Srinivasa Ramanujan (1887-1920) waarschijnlijk wel een speciale band had met het getal $\pi$? Hij liet een aantal notaboekjes na die vol wiskundige formules stonden. Het getal $\pi$ komt op bijna elk blad minstens 1 keer voor. Hier zie je zo'n blad:

    Ramanujan

  • $\ldots$ dat er recent weer een reeks is gevonden waarvan de som het getal $\pi$ bevat? De Catalangetallen $C_n$, genoemd naar de Belgische wiskundige Eugène Catalan (1814-1894), duiken op in allerlei telproblemen en zijn als volgt gedefinieerd: $$ C_n = \frac{1}{n+1} {2n \choose n } $$ Koshi en Gao bewezen in 2012 dat $$\sum_{n=0}^\infty \frac{1}{C_n} = 2 + \frac{4\sqrt{3}}{27} \pi$$
  • $\ldots$ dat je het getal $\pi$ zeer nauwkeurig kan berekenen met een formule met enkel drieën? De uitdrukking $$3+\sin 3 + \sin (3+\sin 3) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$ $$\ \ \ \ \ \ \ \ +\sin (3+\sin 3 + \sin (3+\sin 3))$$ geeft $\pi$ tot op 32 cijfers na de komma nauwkeurig.
  • $\ldots$ dat ook de mooiste formule in de wiskunde natuurlijk het getal $\pi$ bevat? $${\rm e}^{\rm i \cdot \pi} + 1 = 0 $$ Hierin is e de constante van Euler, en i de complexe eenheid, die voldoet aan i$^2=-1$. En dat deze formule voorkomt in één van de afleveringen van The Simpsons?

    Simpsons

  • $\ldots$ dat er ook formules zijn die een verband geven tussen de priemgetallen en het getal $\pi$? Hier zijn er alvast 2: $$\frac{\pi^2}{6} = \frac{2^2}{2^2-1} \cdot \frac{3^2}{3^2-1} \cdot \frac{5^2}{5^2-1} \cdot \frac{7^2}{7^2-1} \cdot \frac{11^2}{11^2-1}\ldots $$ $$\frac{\pi}{4} = \frac{3}{4} \cdot \frac{5}{4} \cdot \frac{7}{8} \cdot \frac{11}{12} \cdot \frac{13}{12}\cdot \frac{17}{16} \cdot \frac{19}{20}\cdot \frac{23}{24}\cdot \frac{29}{28}\ldots $$

    wife of pi

  • $\ldots$ dat het getal $\pi$ je een praktische manier biedt om het aantal seconden in een eeuw te onthouden? Het getal $\pi$ is namelijk een goede benadering van het aantal seconden in een nano-eeuw. Het aantal seconden in een eeuw is ongeveer gelijk aan $\pi \cdot 10^{9}$. Dit wordt de regel van Duff genoemd (met dank aan Ronald).
  • $\ldots$ dat Lars Erickson een $\pi$-symfonie heeft gecomponeerd? Je kan ze hier beluisteren.

    pi-symphony

  • $\ldots$ dat het getal $\pi$ op de vreemdste plaatsen opduikt?
    Bijvoorbeeld hier (met dank aan Adhemar):

    mazda

    Of hier: kies willekeurig twee gehele getallen. Wat is dan de kans dat deze getallen geen gemeenschappelijke factor hebben? Die kans is $6/\pi^2$.

    pi cartoon


Geschreven in Algemeen | 4 Reacties | Vaste link | Afdrukken


De penetratie van moeilijke doelwitten. Een spoedcursus in kwantumcomputers.

15. Januari 2014, 17:29

Sinds het begin van deze maand weten we dankzij Edward Snowden dat de Amerikaanse nationale veiligheidsdienst NSA een budget van ongeveer $80 miljoen begroot heeft voor haar project Penetrating hard targets. Een belangrijke doelstelling van dit project is het kraken van de gangbare encryptie bij internetverkeer (RSA-codes) en omvat basisonderzoek naar kwantumcomputers.

   

Misschien klinken we nu verwend, maar we zijn de laatste tijd spectaculairdere lekken gewoon. Over heel de wereld proberen onderzoekers moeilijke codes te kraken om te testen hoe veilig ze zijn. En de kwantumcomputer is nu eenmaal een hot research item, je zou zelfs kunnen spreken van een academische race om als eerste zo’n effectief werkende machine te fabriceren. Voor zover we weten is de NSA verre van koploper in deze race en staat minder ver dan bijvoorbeeld  DARPA, de onderzoeksafdeling van de Amerikaanse defensie, maar ook minder ver dan instellingen in Canada, Rusland, China en Europa, met het onlangs opgerichte QuTech-centrum in Delft als een van de belangrijkste spelers.

Anderzijds veroorzaakte dit nieuwtje de echo’s van het woord “kwantumcomputer” op nieuwjaarsrecepties, tijdens koffiepauzes, in krantenartikelen en aandachtzoekende weblogs. Hoog tijd om ons jargon desaangaande te upgraden, om collega’s te imponeren of fondsaanvragen op te smukken.

Een spoedcursus in kwantumcomputers

  • Insiders beweren dat de horizon voor de productie van de eerste kwantumcomputer die praktisch bruikbaar is, ligt op ongeveer vijftien tot twintig jaar. We zijn dus ruim op tijd met deze blog. Anderzijds zijn computerwetenschappers al twee decennia druk in de weer met het ontwerpen van algoritmes voor deze toekomstmachines. Juist hier ligt de verklaring voor de belangstelling van NSA en andere geldschieters in kwantumcomputers. Onthoud in deze kwestie vooral:  

    1. Het algoritme van Grover: kan gebruikt worden om veel sneller gegevensbanken te doorzoeken dan de bestaande software voor gewone computers. De huidig grootste implementatie van Grover’s algoritme op een kwantumprototype kan slechts databanken met acht gegevens doorlopen. Voorlopig is onze privacy dus niet in gevaar, maar weet wel dat Google in zijn laboratoria al langer dan zeven jaar experimenteert met dit kwantumzoekalgoritme. 
    2. Het algoritme van Shor: Peter Shor, een Amerikaanse wiskundeprofessor op MIT, ontwikkelde in 1994, als werknemer van Bell Laboratories, een sensationeel factorisatie-algoritme voor kwantumcomputers. Dit algoritme werkt veel sneller dan de exponentiële methodes voor de klassieke computers. Dit zal ons in de toekomst dwingen om het huidige digitale beveiligingssysteem volledig te herzien. Inderdaad, het leeuwenaandeel van onze bankverrichtingen en van internetverkeer wordt versleuteld door RSA-codes die er van uitgaan dat het onmogelijk is om binnen redelijke tijd een groot getal (van pakweg 1024 bitlengte) te ontbinden in priemfactoren. Bovendien was dit algoritme het juist antwoord op de Physics Bowl competition in de episode "The Bat Jar Conjecture" van de televisieserie The Big Bang Theory:



      In 2010 hebben onderzoekers een eenvoudige kwantumcomputer gemaakt die met fotonen werkt en ze zijn er in geslaagd hierop het algoritme van Shor te laten draaien. Met succes hebben ze 21 kunnen ontbinden als 7 $\times $ 3. Het grootste getal, naar ons weten, met kwantumsoftware ontbonden is $143 = 11\times 13$ (in 2012, weliswaar met het adiabatische factorisatiealgoritme). We wensen de NSA veel succes toe om met deze middelen RSA-1024 te kraken.
    3. Wie meer wil weten over kwantumalgoritmes, wie zelfs wil bijbenen, bevelen we graag de homepage van Stephen Jordan aan: Quantum Algorithm Zoo.
  • In moeilijke tijden worden we al te dikwijls gesust met de gemeenplaats dat iedere crisis een opportuniteit is. Maar in dit verhaal is het zelfs zo dat de hindernis die de crisis veroorzaakte, tegelijkertijd de hefboom bleek voor de nieuwe opportuniteit. Zo worden we bijvoorbeeld geconfronteerd met de terminale diagnose voor de wet van Moore. Deze ingenieur bij Intel stelde in de jaren 60 dat het aantal transistors in een geïntegreerde schakeling om de twee jaar verdubbelt.  Maar de dichtheid van transistors op een chip stuit op een fysische beperking. Op het moment dat de steeds kleiner wordende schakelingen op atomair niveau gerealiseerd worden, moet met de spelregels van de kwantummechanica rekening gehouden worden. Het onzekerheidsprincipe van Heisenberg maakt transistors op microschaal onbetrouwbaar. Richard Feynman suggereerde in zijn voordracht op de First Conference on the Physics of Computation (1981) om deze onzekerheid nu net te gebruiken als principe voor een nieuw type computer. Feynman wordt dikwijls de vader van de kwantumcomputer genoemd (al beschreef de Russische wiskundige Yu Manin in 1980 reeds een principe van kwantumrekenen, en soms wordt Paul Benioff als de eerste theoretische grondlegger genoemd).
  • Maar nog voordat hij zijn entree gemaakt heeft, veroorzaakt de kwantumcomputer nu dus al de volgende crisis als potentieel gevaar voor onze privacy en veiligheid (algoritmes van Grover en Shor). Maar ook hier speelt de kwantummechanica de dubbelrol van probleem en oplossing. Ze vormt namelijk de basis voor een nieuwe klasse van codes, kwantumcryptografie, waarvan Quantum Key Distribution (QKD) de bekendste is. Volgens dit principe worden boodschappen gecodeerd in kwantumtoestanden van lichtdeeltjes, en vanaf het moment dat ook maar iemand probeert de boodschap te onderscheppen en te lezen, worden deze kwantumtoestanden vernietigd. Deze ultra-veilige cryptografie is al commercieel beschikbaar en werd zelfs gebruikt om de Zwitserse verkiezingen in 2007 te beveiligen. In connectie met QKD staat de fameuze No-Cloning Theorem in kwantummechanica. Volgens deze stelling is het onmogelijk om een ongekende kwantumtoestand te kopiëren. Dit biedt ongeziene opportuniteiten voor het veilig bewaren van gegevens en het beschermen van auteursrechten.
  • Klassieke computers opereren op bits, die elke juist één van twee waarden kunnen aannemen (uit/aan of 0/1). De eenheid van informatie in een kwantumcomputer is een qubit, een term bedacht door Benjamin Schumaker. Een qubit is de toestand van een elementair deeltje waarvoor twee waarneembare toestanden kunnen waargenomen worden. Bijvoorbeeld, de spinrichting van een elektron of de polarisatie van een lichtdeeltje. Je zou dus denken dat een qubit dezelfde binaire informatie bevat als een gewone bit. Maar het punt van de kwantummechanica is dat zolang we geen waarneming of meting uitvoeren op een elementair deeltje, het zich in een kwantumtoestand bevindt die de superpositie is van twee alternatieven.
  • Een populaire illustratie in tekstboeken over kwantummechanica is een halfdoorlatende spiegel (beam-splitter), hieronder aangeduid met een onderbroken lijntje. Juist de helft van het invallende licht gaat door, de andere helft wordt weerkaatst. De twee bundels van de gesplitste lichtstraal vertonen dan ook de helft van de oorspronkelijke intensiteit. Tot hier de verteerbare kost, op het niveau van de dagelijkse waarnemingen.  



    Maar stel nu dat we de intensiteit van het invallende licht zodanig dimmen dat er slechts één elementair lichtdeeltje overblijft. We hebben de technologie om dit te realiseren, en bovendien ook om dit foton te detecteren (bijvoorbeeld met een fotomultiplicator). Indien we voorbij de “halfspiegel” twee zulke detectoren plaatsen, kunnen we de knoop doorhakken over het gedrag van dit foton: transmissie of reflectie. Als we dit experiment veelvuldig herhalen dan zullen de fotondetectoren elk ongeveer in de helft van de gevallen aantikken, zoals verwacht bij een halfdoorlatende spiegel. Maar mensen bewegen zich als lompe olifanten tussen de porseleinen deeltjes waaruit de wereld is opgebouwd. Indien er twee (elkaar uitsluitende) mogelijkheden zijn, bijvoorbeeld transmissie (T) of reflectie (R), wil ons beperkte brein de knoop doorhakken, maar stiekem gedraagt een foton zich subtieler, namelijk in een mengtoestand van T en R nadat het de beam-splitter gepasseerd is.
  • De kwantumlogica verschilt dus drastisch van de vertrouwde binaire logica waarmee wij doorgaans de wereld willen begrijpen en waarop de klassieke computers gebaseerd zijn. Stel dat we twee mogelijk toestanden beschouwen voor een lichtdeeltje, naargelang het zich beweegt: neerwaarts (1) of opwaarts (0). Volgens de logica van de menselijke waarneming krijgen we na de ontmoeting met de beam-splitter, terug een binaire toestand (0 of 1). Bijvoorbeeld, als een neerwaarts invallende foton reflecteert dan krijgen we een opwaartse beweging, de 0 werd omgezet in een 1. Maar zonder menselijke metingen gehoorzaamt het foton de kwantumwetten, die voor de beam-splitter er als volgt uitzien:      
         
    $$\left| 0\right\rangle  \mapsto \frac{1}{\sqrt{2}}\left| 0\right\rangle -\frac{1}{\sqrt{2}}\left| 1\right\rangle$$            
    $$ \left| 1\right\rangle  \mapsto \frac{1}{\sqrt{2}}\left| 0\right\rangle + \frac{1}{\sqrt{2}}\left| 1\right\rangle$$
  • De notatie $\left| 0\right\rangle$ of $\left| 1\right\rangle$ verwijst naar kwantumtoestanden die simultaan optreden, elk met een eigen gewicht $\pm 1/ \sqrt{2}$ (de waarschijnlijkheidsamplitudes), in tegenstelling tot de (waarneembare) binaire toestanden 0 en 1, die exclusief optreden. (Terzijde: deze rare notatie voor een kwantumtoestand wordt in het jargon een ket genoemd, en is de rechterhelft van de Diracnotatie of braketnotatie). We leggen niet uit hoe de juiste waarden voor de waarschijnlijkheidsamplitudes berekend worden, die soms zelfs complexe getallen zijn, dat zijn dingen die je leert in een cursus kwantummechanica. Per definitie moeten de kwadraten van de waarschijnlijkheidsamplitudes de kansen geven voor het detecteren van de bijbehorende toestand, en dit kunnen we wel controleren (conform het principe van een halfdoorlatende spiegel):
    $$\left({\pm 1/ \sqrt{2}}\right)^2 = \frac{1}{2}$$
  • Tijdens de recente uitreiking van de Gouden Pipet droeg Lieven Scheire de volgende T-shirt:   



    We begrijpen nu net genoeg van kwantummechanica om zijn nerdy grapje te smaken: “Vraag me niet hoe ik me voel, of ik zou kunnen instorten.”
  • Sinds 2009 bestaan de eerste echte kwantumchips, met weliswaar een nog bescheiden functionaliteit. Sinds 2011 startte de Canadese firma D-Wave zelfs met de commerciële productie van een 128-qubit processor (de slogan op hun website: We have a problem with impossible). In mei 2013 werd de nieuwe 512-qubit kwantumcomputer geïnstalleerd in het prestigieuze Quantum Artificial Intelligence Lab, een samenwerking tussen NASA, Google en USRA.
  • De input voor een klassieke computer kan voorgesteld worden door een rij van $n$ bits, $011\ldots 01$, wat een keuze is uit $2^n$ mogelijkheden. Maar een rij van $n$ qubits stelt een superpositie voor van al deze $2^n$ mogelijkheden! Een kwantumcomputer (met kwantumpoorten) is dus in staat om super-parallelle berekeningen uit te voeren, simultaan op alle mogelijke inputs van $n$ bits.  
     
     
  • Voor sommige moeilijke problemen, zoals het ontbinden van natuurlijke getallen in priemfactoren, het opstellen van een collegerooster of het handelsreizigersprobleem, hebben de huidige algoritmes een exponentieel aantal bewerkingen nodig, maar kwantumcomputers kunnen dit veel sneller omdat ze alle mogelijkheden tegelijk kunnen beschouwen.
  • Een klassieke chip bevat logische circuits opgebouwd uit logische schakelingen zoals OR, AND en NOT. Een kwantumpoort heeft qubits als ingangen en uitgangen. Bijvoorbeeld, bovengenoemde beam-splitter realiseert de zogenaamde Hadamardpoort, die geen tegenpool heeft met een klassieke poort. Deze poort heeft één qubit-ingang en één qubit-uitgang. Een andere belangrijk voorbeeld is de cNOT-poort, een 2-qubit-poort die samen met de Hadamardpoort voldoende is om de universele Turing-kwantummachine te simuleren, zoals beschreven door David Deutsch, en dus in principe voldoende om alles te berekenen in onze macro- en micro-wereld.
  • In de wiskundige beschrijving worden de kwantumtoestanden voorgesteld als vectoren in een Hilbertruimte, en de kwantumpoorten als unitaire operatoren binnen deze ruimte. Maar voordat je je tijdens de koffiepauze op het werk bezondigt aan name-dropping in deze materie, zou ik eerst een en ander bestuderen.  
  • Het prepareren van qubits mag dan een technologisch huzarenstukje zijn, de echte uitdaging bij de bouw van een kwantumcomputer is het geïsoleerd houden van de kwantumcircuits zodat er geen interactie is met de omgeving. Want zodra er tijdens de berekenen ook maar iets kan gemeten worden, zodra er vroegtijdig informatie lekt, dreigen kwantumtoestanden in te storten met onnauwkeurigheden tot gevolg. Dit wordt het decoherentieprobleem genoemd. Om deze reden zijn de circuits van de huidige kwantumprocessoren gemaakt met supergeleiders, en functioneren ze meestal bij temperaturen dicht bij het absolute nulpunt, wat uiteraard een beperking geeft op het praktische gebruik.
  • In dit verband is het principe van Landauer uit 1961 erg belangrijk. Telkens als tijdens een computerberekening een bit aan informatie verloren gaat, dan komt er een beetje energie vrij. Vergeten doet opwarmen. Dit is bijvoorbeeld het geval bij een AND-poort, die twee ingangen heeft maar slechts één uitgang. Maar kwantumberekeningen gebruiken gelukkig poorten die voorgesteld worden door unitaire operatoren en zijn per definitie altijd omkeerbaar.
  • Behalve het principe van superpositie, verantwoordelijk voor het parallellisme bij kwantumcomputers, is er nog een ander kwantumfenomeen dat een rol speelt in deze futuristische machines: kwantumverstrengeling. Dit betekent dat de kwantumtoestanden van twee elementaire deeltjes met elkaar verbonden blijven, ook al worden ze uit elkaar getrokken. Dit is bijvoorbeeld nodig als we een berekening willen controleren, al is het maar om te kijken of deze afgelopen is. Wegens het decoherentieprobleem van kwantumcomputers (zie hierboven) moeten we kwantumcomputers hun werk laten doen in perfect geïsoleerde omstandigheden, maar ooit willen we wel een uitkomst weten natuurlijk. Een theoretische oplossing stelt voor om de qubits op een onrechtstreeks manier te controleren, door observaties op andere maar hiermee verstrengelde deeltjes, zodat de kwantumtoestand van de qubits binnenin de kwantumcomputer niet in elkaar stort. 

Toegift 

Als extraatje, net buiten deze spoedcursus voor kwantumcomputers, nog een kort lesje in kwantummechanica. Hoe weten de kwantumspecialisten dat elementaire deeltjes zich, na een gebeurtenis met alternatieve uitkomsten, in een parallelle kwantumtoestand bevinden. Immers, vanaf het moment dat iemand dit wil testen, vanaf het ogenblik dat iemand er nog maar naar kijkt, stort de kwantumtoestand in om kleur te bekennen tot juist één van de uitkomsten. Gelukkig is een mens slim genoeg om zijn eigen klassiek-logisch redenerende brein buiten spel te zetten. Hieronder laten we een foton ongemoeid twee beam-splitters passeren en detecteren we pas daarna in welke toestand het zich bevindt.


De halfdoorlatende spiegels komen overeen met de stippellijntjes, en de twee volle lijntjes stellen volledig reflecterende spiegels voor. Een lichtdeeltje dat zoals in de figuur initieel naar beneden gericht is, kan “kiezen” tussen vier mogelijke trajecten: RR, RT, TR en TT, waarbij R staat voor reflectie en T voor transmissie bij de opeenvolgende beam-splitters . Merk op dat de trajecten RR en TT in het laatste trajectdeel opwaarts gaan en in de bovenste detector arriveren. Anderzijds resulteren trajecten RT en TR in een neerwaartse beweging die tegen de onderste fotondetector zal tikken. Als een foton voor iedere passage bij een halfspiegel effectief de knoop zou doorhakken, met 50% kans voor elk van de beide mogelijkheden, dan zouden de vier trajecten (RR, RT, TR, TT) even waarschijnlijk zijn (elk 25% kans). Als we dit experiment de hele dag zouden herhalen dan verwachten we dat tegen de avond de beide detectoren ongeveer evenveel fotonen geturfd hebben. Maar dat is niet zo: het blijkt dat alle fotonen bovenaan gedetecteerd worden bij initieel neerwaarts invallende fotonen (en omgekeerd)! Dit wordt foutloos voorspeld door de kwantummechanica. We tonen dit voor de neerwaarts invallende foton (zoals in de figuur), geassocieerd met basistoestand $\left| 1\right\rangle$:

Eerste halfspiegel:

$\left| 1\right\rangle \mapsto \frac{1}{\sqrt{2}}\left| 0\right\rangle + \frac{1}{\sqrt{2}}\left| 1\right\rangle$

Spiegel:

$\mapsto \frac{1}{\sqrt{2}}\left| 1\right\rangle + \frac{1}{\sqrt{2}}\left| 0\right\rangle$

Tweede halfspiegel:

$\mapsto \frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2}}\left| 0\right\rangle + \frac{1}{\sqrt{2}}\left| 1\right\rangle) + \frac{1}{\sqrt{2}}(\frac{1}{\sqrt{2}}\left| 0\right\rangle -\frac{1}{\sqrt{2}}\left| 1\right\rangle)$ $=\left| 0\right\rangle$

Leestip 

Na vijftien jaar nog steeds overeind (en nog altijd een plezier om te herlezen):

The Feynman Processor, door Gerard J. Milburn, Perseus Books, 1998. 


Geschreven in Actuele wiskunde | 1 Reacties | Vaste link | Afdrukken


De pracht van priemgetallen

11. December 2013, 19:35

Wat hebben mensen toch met getallen? Vanmorgen kregen we op de radio te horen dat de Dienst Burgerzaken van de stad Gent vandaag woensdag koppels wil trouwen, terwijl dat normaal niet kan op een woensdag. Reden hiervoor is de datum: 11/12/13. Ook in Nederland, bijvoorbeeld in Amersfoort, is het niet anders. Daar trouwen 10 koppels vandaag 11/12/13, en wel om 14u15. 11-12-13-14-15 dus. Er waren in Amersfoort overigens 171 koppels die wel erg graag deze huwelijksdatum hadden gehad. 161 ervan vielen dus uit de boot.

Gelezen op het internet: de volgende speciale datum is 2/2/22. Tja, een beetje meer verbeelding en je hebt toch al snel heel wat meer interessante data. Zo hebben we pas nog een Pythagoreïsche dag gehad, op 5 december. Inderdaad, 5/12/13. Deze drie getallen vormen een Pythagoreïsch drietal. We hebben namelijk dat $5^2+12^2=13^2$ met als gevolg dat er een rechthoekige driehoek bestaat met zijden 5 - 12 - 13. De stelling van Pythagoras, weet je wel?
Dit is toch heel wat minder saai dan 2/2/22? En die 161 koppels moeten dan zelfs niet meer wachten to 2022 om in het het huwelijksbootje te stappen, want de volgende Pythagoreïsche dag is al 17/8/15.

Wat de 10 koppels waarschijnlijk niet beseffen, is dat 11/12/13 niet enkel interessant is omdat het drie opeenvolgende getallen zijn (of drie opeenvolgende termen van een rekenkundige rij met verschil 1). Als we het trio even van dichterbij bekijken, dan valt dadelijk op dat 11 en 13 een priemtweeling vormen, die netjes het sublieme getal 12 insluit. Wat een priemtweeling is, dat weet iedereen: het zijn twee priemgetallen die een verschil van 2 hebben. Een subliem getal is dan weer een getal met de volgende merkwaardige eigenschappen: het aantal delers ervan is een perfect getal (namelijk 6), en ook de som van die delers is een perfect getal (meer bepaald 28). Een perfect getal is overigens een getal dat de som is van zijn echte delers: 6 heeft als echte delers 1, 2, en 3, en 1+2+3=6.
Er zijn slechts twee sublieme getallen bekend, 12 en dan ook 6 086 555 670 238 378 989 670 371 734 243 169 622 657 830 773 351 885 970 528 324 860 512 791 691 264. Mensen met bindingsangst kunnen dus gerust tegen hun verloofde zeggen dat ze willen wachten tot het volgende sublieme getal.

11/12/13 is ook de dag dat ons boek officieel verschijnt. Na jaren bloggen dachten we wel materiaal genoeg te hebben om een boek te vullen. Dat bleek spijtig genoeg niet het geval, nogal wat aanvullingen waren noodzakelijk.
We hebben ons deze keer beperkt tot één onderwerp: de priemgetallen. Waarom priemgetallen? Om allerlei redenen:

Sinds het verschijnen van het boek De eenzaamheid van de priemgetallen vraagt iedereen zich af hoe eenzaam die priemgetallen nu in feite zijn.

Het jaar 2013 was een geweldig jaar voor de priemgetallen. Niet alleen was er het bewijs door Harald Helfgott van de zwakke vorm van het vermoeden van Goldbach (elk oneven getal groter dan 5 kan geschreven worden als de som van drie priemgetallen, bijv 7=3+2+2, 9=5+2+2, 11=7+2+2, 13=7+3+3, ...), ook het priemtweelingvermoeden kwam in de pers. Zijn er oneindig veel priemtweelingen zoals 11 en 13, en 17 en 19, 29 en 31? Dus koppels priemgetallen die 2 van elkaar verschillen. Het antwoord was een beetje onverwacht: "dat weten we nog niet, maar er zijn wel oneindig veel koppels opeenvolgende priemgetallen die ten hoogste 70 miljoen van elkaar verschillen". Een resultaat van Yitang Zhang.
En de media hebben ervan gesmuld. Ons besluit was: priemgetallen liggen goed in de markt!

Priemgetallen gaan al meer dan twee eeuwen mee. Het is heel eenvoudig uit te leggen wat een priemgetal precies is, en toch kan je ze niet gemakkellijk herkennen als je er een voor je neus hebt staan. Is 5731 er een? (Dit is overigens een makkelijke, 5-7+3-1=0, dus deelbaar door 11!)
Ze hebben bovendien merkwaardige eigenschappen: je kan er veilige codes mee maken (en dankzij deze codes zijn banktransacties per computer superveilig), tenminste tot het moment dat de quantumcomputers arriveren. Je kan er zelfs geld mee verdienen.

En het zijn geliefde onderwerpen voor blogs. Het kan namelijk zonder dat je er afbeeldingen bij moet zoeken, wat een geweldig comfort is.

Ons boek geeft een soort geschiedenis van de priemgetallen, met veel aandacht voor de speciale figuren die zich door de eeuwen heen met priemgetallen hebben beziggehouden.
  


De pracht van priemgetallen
Paul Levrie en Rudi Penne, De pracht van priemgetallen. Het verhaal van een eeuwenlange zoektocht naar verborgen patronen. Prometheus - Bert Bakker (2014) 198 pagina's.

Wil je graag weten wie Monsieur Le Blanc precies was? En kan je niet geloven dat de som van allemaal positieve getallen toch negatief kan zijn? Of ben je gebiologeerd door magische vierkanten en varianten daarvan zoals priemtovervierkanten? Wil je meer weten over de figuren achter de priemgetallen? Of ben je ervan overtuigd dat priemgetallen nutteloze dingen zijn? Wil je graag meer weten over priemvampiergetallen?
Lees dan zeker dit boek.
We proberen er te laten zien dat wiskunde ook leuk kan zijn.

 
Formuledichtheid: 
Moeilijkheidsgraad: 
Score: 






Geschreven in Actuele wiskunde | 2 Reacties | Vaste link | Afdrukken


Een ontdekt deeltje en een verdwenen wetenschapper

10. Oktober 2013, 21:12

De bloglezers die ons gemist hebben, willen we dadelijk geruststellen: we zijn niet weg, we zijn ook niet gebrouilleerd, we houden nog steeds van wiskunde. We hebben de voorbije maanden samen aan een project gewerkt dat nu de eindfase nadert, dat te maken heeft met deze blog, en waar we weldra hier over zullen berichten.
Vandaag wil ik het hebben over Majorana en Villarceau. Ettore Majorana zit in dezelfde league als onze kersverse nobelprijswinnaar François Englert, waarvan je hier een foto ziet:

Englert Higgs

samen met Peter Higgs. Proficiat,
François!
In de laatste reactie op onze blog van Fibonaccidag schonk Eos-redacteur Reinout Verbeke boeken weg, aan drie lezers die het juiste antwoord hadden gevonden op de vraag. Een boek over Riemann, een biografie van Fermi, en ook een over Majorana. Deze laatste naam deed bij mij geen belletje rinkelen. Majorana? Om eerlijk te zijn, ook de naam François Englert was ons tot voor kort onbekend. Enig opzoekwerk leerde me dat Majorana een geniaal theoretisch natuurkundige was. Hij was een medewerker van de beroemde fysicus Enrico Fermi.  Fermi zei over hem:

Er zijn verschillende soorten wetenschappers: tweede- en derderangswetenschappers die hun best doen, maar niet ver geraken; er zijn er ook van de eerste rang die grote ontdekkingen doen die fundamenteel zijn voor de ontwikkeling van de wetenschap; en dan zijn er de genieën, zoals Galilei en Newton. Wel, Majorana was een van hen.

Majorana is vooral bekend voor het Majorana-deeltje, een fermion dat zijn eigen antideeltje is. Hij voorspelde het bestaan ervan in 1937, en pas in 2012 is het Majorana-deeltje voor het eerst `gezien'. Hierover kan je lezen in het tijdschrift Science, in het nummer van 25 mei. Als je de cover ervan
bekijkt 

Science

door een SEM (een rasterelektronenmicroscoop)
, dan zie je dit:

SEM-beeld

heeft men mij verteld. Als je klikt op de figuur voor een vergroting, dan zie je op de punt van de nanodraad een afbeelding van Majorana. (Een vierde soort wetenschappers bij Science: grappenmakers?)
Waarom kennen we Majorana niet? Waarschijnlijk vooral omdat hij in 1938 spoorloos verdween en niemand precies weet wat er met hem gebeurd is. Hij was toen 32 jaar oud. Reden genoeg voor mij om het boek over hem even ter hand te nemen. Toen ik recent de kans kreeg om het in te kijken, viel mijn oog op een voorval verteld door Emilio Segrè: over Ettore Majorana die net vóór Emilio een mondeling examen moest afleggen, nog even het bewijs uitlegde van het bestaan van de cirkels van Villarceau op een torus.
Opnieuw een naam die me niets zei, maar deze keer gaat het over wiskunde!
En omdat dit een blog is over wiskunde, vergeten we Majorana nu volledig.

Yvon-Villarceau

Antoine François Joseph Yvon Villarceau (1813-1883) is vooral bekend als sterrenkundige, maar hij was ook wiskundige en ingenieur. Nu kennen we hem vooral door zijn cirkels, die bekijken we even.
We starten met een torus, ofte een donut, zie figuur:

donut

Een iets meer nauwkeurige uitleg van wat we precies bedoelen met een torus is misschien wel nuttig. Een torus is een oppervlak dat ontstaat door het wentelen van een cirkel om een as die in hetzelfde vlak ligt als die cirkel:

torus

De rode cirkel in de vorige figuur ligt in hetzelfde vlak als de rechte z. We laten het middelpunt van die cirkel lopen over de blauwe cirkel. De rode punten beschrijven dan een oppervlak dat wiskundigen een torus noemen (uit het Latijn, torus betekent verdikking, spier, kussen, matras):

animation

Neem nu een willekeurig punt op het oppervlak van deze donut/torus. De vraag die Villarceau zich stelde was de volgende: hoeveel cirkels kan je vinden die door dit punt gaan en volledig op het oppervlak van de torus liggen? Er zijn er alvast twee, door de manier waarop de torus ontstaat. Je kan dit zien op de volgende figuur, waar we een willekeurig punt genomen hebben:

torus

Villarceau wist te bewijzen dat er nog twee extra zijn, dit betekent dat er voor elk punt van de torus 4 cirkels te vinden zijn door dat punt die volledig op de torus liggen. Toch wel een onverwacht resultaat. Op de volgende figuur zie je ze alle vier liggen:

vier

Voor sommige startpunten kan je die twee laatste cirkels vinden door de torus te snijden met een vlak, lees: door de donut met een vlakke snede door te snijden. Het volgende filmpje illustreert de zaak:

circles

Dit is wat Villarceau hierover zei in 1848:

comptesrendues1848

Als je met een donut zit, zeker het proberen waard. En als je dan toch bezig bent, probeer ook eens met een vlakke snede een lemniscaat te krijgen.
Dat Villarceau misschien toch wel een paar honderd jaar te laat kwam met zijn idee, dat zou kunnen blijken uit de volgende figuren:

strasbourg

strasbourg

Dit zijn foto's, genomen in de Musée de l'Oeuvre de Notre-Dame in Strasbourg, waarop je een soort torus ziet, met de cirkels van Villarceau. Het gebouw in kwestie dateert uit de zestiende eeuw.



majorana
Luisa Bonolis, Majorana. Spoorloos verdwenen genie. Veen Media (2013) 160 pagina's.

Dit boek is een biografie van Ettore Majorana. Deze Italiaanse theoretische natuurkundige is bij ons minder bekend, maar werd in zijn tijd erg gewaardeerd door zijn beroemde tijdgenoten in de fysica. 

Het boek geeft een mooi beeld van de evolutie van de deeltjesfysica in de eerste helft van de twintigste eeuw. De auteur gaat ook dieper in op de verdwijning van Majorana in 1938. Na het verschijnen van de oorspronkelijke versie van het boek in 2002 zijn er overigens nog nieuwe documenten aan het licht gekomen i.v.m. deze verdwijning.

Formuledichtheid: Θ Ο Ο Ο Ο
Moeilijkheidsgraad: Θ Θ Ο Ο Ο
Score: Θ Θ Θ Ο Ο





Geschreven in Actuele wiskunde | 1 Reacties | Vaste link | Afdrukken


De oloïde: het perfecte cadeau

29. Mei 2013, 09:13

Paul Schatz


De oloïde is een elegante uitvinding van Paul Schatz (1890-1979). Deze eigenzinnige kunstenaar werd in Duitsland geboren en legde een studieparcours af dat zo grillig was dat we meeleven met de ouders die dit moesten ondergaan en bekostigen. Naar verluid studeerde hij eerst techniek en wetenschappen, waarin hij klaarblijkelijk uitblonk want hij won de Graf Zeppelin-Preis in 1916. Uit appreciatie werd hij prompt de eerste wereldoorlog ingestuurd als radio-operator. Na de oorlog studeerde hij wiskunde in München, maar hij verzuimde zijn diploma te halen, want net voor de eindstreep koos hij een andere studierichting, astronomie, die hij op haar beurt in 1922 inruilde tegen een kunstopleiding (voornamelijk houtsnijwerk). Tussen 1924 en 1927 werkte hij als beeldhouwer in zijn eigen atelier aan het Bodenmeer, waar hij zich ook verdiepte in de antroposofie, de spirituele filosofie geïnspireerd door de ideeën van Rudolf Steiner. Een en ander had tot gevolg dat een boek uit zijn pen vloeide Der Weg zur künstlerischen Gestaltung in der Kraft des Bewusstseins (Konstanz, 1927, in eigen beheer). Nog dat zelfde jaar verhuisde hij met zijn vrouw naar Zwitserland, waar hij zich tot zijn dood in 1979 bezighield met technische kunst en artistieke techniek.


In 1929 ontdekte Paul Schatz een techniek om een kubus binnenste buiten te keren. Deze inverteerbare kubus is sindsdien bekend als speelgoed of als basis voor een 3D-puzzel. Bekijk onderstaand filmpje.

 


Dit vloeiend mechanisme is een voorbeeld van een gesloten keten van tetraëders, door wiskundigen een kaleidocykel genoemd. Dat het inderdaad een kubus binnenste buiten keert, volgt misschien duidelijker uit het volgende filmpje, waarbij dezelfde beweging geïllustreerd wordt met het geraamte van een kubus.

 


In 1929 ontdekte Schatz trouwens ook hoe hij de andere Platonische lichamen kon inverteren, en de resulterende ritmische beweging bracht hem uiteindelijk tot de ontdekking van de oloïde (Swiss Patent 500.000). Verbaas uzelf over de elegante waggel waarmee dit mooie (bij voorkeur gladgepolijste) object zich voortbeweegt:

 



Een oloïde wordt gemaakt met behulp van twee cirkels $C_1$ en $C_2$ met gelijke straal $R$ die zich in loodrechte vlakken bevinden en die door elkaars middelpunt lopen:

ontstaan

Het object wordt dan gevormd door elk punt $A$ van $C_1$ te verbinden met juist dat punt $B$ van $C_2$ waarvoor de raaklijnen aan de respectieve cirkels elkaar snijden. Een oloïde is dus opgebouwd uit rechte lijnstukken, en wordt daarom een regeloppervlak genoemd.

regeloppervlak

De oloïde vertoont een verwarrende gelijkenis met de zogenaamde Two Disk Roller, ook al betreft het hier een verschillend principe. Deze constructie bestaat uit twee identieke cirkels, eveneens loodrecht in elkaar geschoven, maar ditmaal niet tot ze door elkaars middelpunt gaan. De afstand tussen de twee middelpunten is nu niet gelijk aan de straal $R$ (zoals bij de oloïde) maar eerder gelijk aan $\sqrt{2}\times R$. Tenslotte worden de cirkels als schijven opgevuld en worden geen punten van de verschillende cirkels met elkaar verbonden:


De rollende beweging wordt nu gekarakteriseerd door de eigenschap dat het zwaartepunt van de constructie op constante hoogte blijft. Probeer het maar eens zelf aan de toog met twee ronde bierkaartjes. Gegarandeerd succes, en beter dan om het even welke openingszin.  

Ook al zouden we Paul Schatz tegenwoordig een drop-out noemen, heeft hij de gediplomeerde wiskundigen bij verrassing genomen door voor de eerste keer een gesloten object te tonen dat zichzelf volledig ontwikkelt of afrolt. Dit heeft als gevolg dat het oppervlak van een oloïde volledig ontvouwbaar is op een vlak papier, en dus een patroon geeft dat zonder strekken of scheuren zich terug tot een oloïde opvouwt:

ontwikkeling

Dit is bijvoorbeeld niet mogelijk voor een boloppervlak, ook al lijkt een bol vlot te rollen. Daarom zullen we nooit een perfecte vlakke wereldkaart kunnen tekenen. Een ontwikkelbaar oppervlak (in 3 dimensies) is noodzakelijkerwijs een regeloppervlak. Bekende voorbeelden zijn kegels en cilinders, maar dan beschouwen we ze als onbegrensde oppervlakken, zonder grondvlak (dat tijdens het rollen nooit de tafel zou raken). Cilinders en kegels zijn dus niet praktisch realiseerbaar als ontwikkelbare oppervlakken. Voordat Schatz de oloïde in 1929 ontdekte, dacht men zelfs dat een volledig ontwikkelbaar (begrensd) object niet bestond. Volgens ons is er sindsdien nog maar 1 dergelijk object ontdekt, namelijk de sfericon, door de Israëlische speelgoeduitvinder David Haran Hirsch in 1980.

Een ander leuk wiskundig weetje over de oloïde is het feit dat haar oppervlakte gelijk is aan deze van een bol met dezelfde straal $R$.

Het kunstwerk van Paul Schatz is niet enkel interessant voor wiskundigen, het blijkt ook tot nuttige technische toepassingen te leiden. Een waggelende oloïde is namelijk in staat om een vloeistof perfect te mengen. Ziehier een spectaculaire oloïde-mixer:

mixer

Hieronder krijgt u een idee van de stromingen die een oloïde veroorzaakt:

mix1

mix2

Als men bovendien de oloïde tijdens het mengen ook zuurstof laat verspreiden, dan bekomt men een erg geschikt zuiveringsinstrument.

Maar los van de wiskundige en kinetische eigenschappen van de oloïde vinden we dat Paul Schatz zijn onsterfelijkheid verdiend heeft omwille van de elegantie en de schoonheid van dit object. Juwelenontwerpers en andere kunstenaars hebben dit al lang erkend, getuige de verschillende mooie hebbedingetjes die op het internet aangeboden worden en waarin we de oloïde duidelijk herkennen. Misschien een tip voor een bijzonder cadeau voor een bijzondere persoon?

juweel

juweel

juweel

juweel


Geschreven in Algemeen | 1 Reacties | Vaste link | Afdrukken


Over aanrakingen

14. April 2013, 19:55

Er zijn heel wat problemen die al verschillende eeuwen meegaan, en daarom dus waarschijnlijk wel interessant zullen zijn. Nu en dan zullen we proberen er een voor te stellen in deze blog. Het eerste probleem veroorzaakt al meer dan 2000 jaar publicaties.

Boeken die verloren gegaan zijn, zijn altijd interessant voor speculatie. Apollonius van Perga (262-192 voor Christus) schreef een boek (over wiskunde) met als titel Over aanrakingen. Een van de problemen die hij stelt in dit boek, is het volgende. Gegeven drie cirkels. Bepaal een cirkel die raakt aan deze 3 cirkels. Deze sangaku (van Hotta Jinsuke uit 1788) maakt er duidelijk gebruik van (rechts zie je het origineel):

sangaku hotta  sangaku hotta


Het boek van Apollonius is verloren gegaan, maar dankzij Pappus van Alexandrië (290-350) weten we dat het heeft bestaan, en ook dat het probleem door Apollonius inderdaad is opgelost. Sinds dan hebben heel wat wiskundigen de draad van dit Probleem van Apollonius weer opgepakt. Bijvoorbeeld de Fransman François Viète (of Vieta, 1540-1603) die er een boek over schreef, met als titel Apollonius Gallus:

Apollonius Gallus

Lachen met de Belgen was er ook in die tijd al bij. Vieta beantwoordde een uitdaging gesteld door de Leuvense wiskundige Adriaan van Roomen (1561-1615) met een andere uitdaging:

décrire un cercle tangent à trois cercles données.

Hij ging als volgt verder: si la Belgique ne met pas en avant ses Apollonius, la France produira le sien.
Toch even laten voelen dat het allemaal niet zo eenvoudig is. We beginnen met 2 cirkels in plaats van 3:

twee cirkels

Gezocht: een cirkel die raakt aan deze twee gegeven cirkels.
Het is duidelijk dat er meerdere oplossingen zijn. In de volgende figuur zie je er enkele:

twee cirkels

Om er een te selecteren geven we een extra punt erbij. We zoeken nu de cirkel die raakt aan beide cirkels en door het aangegeven punt op de grootste cirkel gaat:

twee cirkels

Hoe gaan we te werk? Je ziet hier de opeenvolgende stappen in het proces:

twee cirkels
Het middelpunt van de gezochte cirkel ligt op de zwarte lijn, door symmetrie.









twee cirkels
Teken met het gegeven punt als middelpunt een cirkel even groot als de tweede. Deze cirkel snijdt de zwarte lijn in het blauwe punt.









twee cirkels
Als we nu een cirkel zoeken met middelpunt op de zwarte lijn, door de twee blauwe punten, dan zal de gezochte cirkel hetzelfde middelpunt hebben. De rode rechte is de verzameling van alle punten die op gelijke afstand liggen van de twee blauwe. Het middelpunt van de cirkel door de twee blauwe punten is dus het rode punt.
twee cirkels
Nu kunnen we de gezochte cirkel tekenen. Middelpunt is het rode punt, straal is de afstand van dit punt tot het punt op de omtrek van de groene cirkel. 
Klaar.






Het probleem wordt nog moeilijker als je start met drie cirkels. Adriaan van Roomen deed het niet slecht. Hij had door dat alle middelpunten van cirkels die raken aan twee gegeven cirkels op een hyperbool liggen. Dus, besloot hij, als je drie cirkels hebt, dan neem je ze per twee samen, A en B, en B en C, dan heb je twee zo'n hyperbolen en die snijden elkaar in het gezochte middelpunt (in het geel) van de rakende cirkel:

2 hyperbolen

Vieta lachte hem hiermee uit, want hyperbolen waren nu eenmaal niet-construeerbare krommen. Construeerbaar betekent: je kan het tekenen met passer en liniaal. Dus gaf Vieta zelf maar de oplossing.
Ook René Descartes (1596-1650) vond het een opgave die de moeite waard was. Hij correspondeerde met een prinses, Elisabeth van Bohemen (1618-1680), o.a. over wiskundige zaken:

brief

Al snel dacht Descartes dat het probleem wat te moeilijk was, en vereenvoudigde hij het tot het geval dat de drie gegeven cirkels elkaar al onderling raken. Elisabeth had het er nog moeilijk mee, maar geraakte toch heel ver. Dit alles leidde tot wat nu bekend staat als de cirkelstelling van Descartes (zie vorige blog, voor pi-dag) die een verband geeft tussen de stralen van vier cirkels die elkaar zo raken. Er zijn normaal twee oplossingen (in het oranje op de figuren):

oplossing 1

oplossing 2

uitwendig, en inwendig rakend. (In dit geval spreken we over cirkels van Soddy, genoemd naar nobelprijswinnaar Frederick Soddy (1877-1956) die Descartes' cirkelstelling herontdekte in 1936, en ze zo leuk vond dat hij er een gedicht over schreef.)
Natuurlijk was het vóór de tijd van Descartes allemaal maar wat knoeien, want Descartes was degene die de coördinaten uitvond, en vanaf dan kon men wiskundige figuren ook nauwkeurig beschrijven met vergelijkingen. De formule voor de stralen was een lastige om af te leiden (nog steeds overigens).
Maar nu we ze hebben, kunnen we ze ook gebruiken om figuren zoals deze te maken:

gasket

Een fractaal avant la lettre. Nog andere grote wiskundigen hielden zich bezig met het probleem van Apollonius, bijvoorbeeld Isaac Newton (1642-1727), Leonhard Euler (1707-1783), Carl Friedrich Gauss (1777-1855), en ook Augustin Louis Cauchy (1789-1857). Ook Jakob Steiner (1796-1863) vond het interessant, en dit leidde tot Steiner-kettingen zoals deze:

steiner

of kunstige limietgevallen hiervan:

steiner

Uitbreidingen naar drie en meer dimensies is de volgende natuurlijke stap: gegeven  4 bollen in de driedimensionale ruimte, zoek de bol die raakt aan deze 4. Hier zie je een oplossing:

coxeterFirmament van John Robinson

een kunstwerk gemaakt door John Robinson voor de 90ste verjaardag van de meetkundige Donald Coxeter, die zich ook gebogen heeft over het probleem van Apollonius.
Is dit ook nuttig, vraag je je misschien af? Welja, soms wel. Bijvoorbeeld voor hyperbolische trilateratie. In de eerste wereldoorlog werd dit gebruikt om de positie te bepalen van artilleriegeschut op basis van drie waarnemingen ervan. Ook foutencorrectie bij DVD's is een toepassing.
En als je nu echt wil weten hoe je zo'n rakende cirkel construeert, dan kan je de constructie hier volgen, in 8 stappen:
Noot als afsluiting: indien je je moest afvragen vanwaar de titel Apollonius Gallus komt, het is niet Het kieken Apollonius, hoewel gallus wel degelijk "haan" betekent. Het is waarschijnlijk "De Gallische Apollonius". Leuk om weten is dat Willibrord Snell (of Snellius, 1580-1626) naar aanleiding van het boek van Vieta zijn eigen versie uitbracht met als titel Apollonius Batavus (de Nederlandse Apollonius).

Apollonius Batavus



Geschreven in De klassieke problemen uit de wiskunde | 1 Reacties | Vaste link | Afdrukken


Ook u kunt u zeker vergissen

14. Maart 2013, 06:19

Uw zwakke brein kan plots verkeerd beslissen. Of ook: I nunc, O Baili, Parnassum et desere rupem, dic sacra Peridium deteriora quadris! En dit allemaal als gevolg van de verzuchting: how I wish I could enumerate pi easily...
Naar jaarlijkse traditie (de vorige versie vind je hier) presenteren we hier ter lering en vermaak opnieuw een hele resem $\pi$-weetjes.

Wist je al ...
  • $\ldots$ dat het vandaag 14 maart $\pi$-dag is? Waarom? Omdat in de Amerikaanse schrijfwijze de datum 14 maart genoteerd wordt als 3/14 en 3,14 is een benadering voor het getal $\pi$.
  • dat Eric Baranyanka (vroeger bij de Ketnetband) een nummer heeft gemaakt over het getal $\pi$, en $\pi$-dag? Klik hier.
  • $\ldots$ dat je vandaag om 15 u taart moet eten?
    Ik kreeg mijn eerste echte $\pi$-taart vorig jaar: Zoals je kunt zien was het een zeer grote. Goed voor 18 personen. Ik heb ze gekregen van mijn baas, die echt wel zin krijgt in $\pi$-dag. Bedankt Martine!

    Pie
  • $\ldots$ dat het record uit 2010 voor het berekenen van de verste decimaal van het getal $\pi$, dat op naam stond van een team van Yahoo dat hiervoor 1000 computers gebruikte, is verpulverd door Ed Karrels in augustus 2012?
    Beginnend vanaf de 1.000.000.000.000.000ste plaats zijn de volgende 26 hexadecimale cijfers:
    8353CB3F7F0C9ACCFA9AA215F2
    Karrels maakte hiervoor gebruik van een speciale formule ontdekt door Fabrice Bellard in 1997.
    Deze formule is speciaal in de zin dat je er decimalen van $\pi$ mee kan berekenen zonder de vorige uit te rekenen zoals de meeste algoritmes doen.
  • $\ldots$ dat de volgende bekende formule
    $$\cos {{\pi}\over{3}} = \frac{1}{2}$$ slechts een speciaal geval is van een oneindige rij van soortgelijke formules met in het rechterlid $\frac{1}{2}$? Hier zijn de volgende drie: $$ \cos \frac{\pi}{5} - \cos \frac{2\pi}{5}= \frac{1}{2} $$ $$ \cos \frac{\pi}{7} - \cos \frac{2\pi}{7} + \cos \frac{3\pi}{7}= \frac{1}{2} $$ $$ \cos \frac{\pi}{9} - \cos \frac{2\pi}{9} + \cos \frac{3\pi}{9} - \cos \frac{4\pi}{9}= \frac{1}{2} $$ Dit werd bewezen door Packard en Reitenbach in april 2012.
  • $\ldots$ dat als je een configuratie hebt zoals deze:

    Descartes

    met 4 cirkels (cirkels doen - hopelijk - aan $\pi$ denken) die elkaar raken, dat de stralen van deze cirkels dan voldoen aan de volgende vergelijking?
    $$ \frac{1}{(R_1)^2} + \frac{1}{(R_2)^2} + \frac{1}{(R_3)^2} + \frac{1}{(R_4)^2} = \frac{1}{2} \left( \frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3} + \frac{1}{R_4} \right)^2 $$ Dit staat bekend als de Cirkelstelling van Descartes.
  • $\ldots$ dat de film Life of Pi onlangs 4 Oscars heeft gewonnen?
    Het boek waarnaar de film is gemaakt: Life of Pi door Yann Martel, won de Booker Prize in 2002. Van het boek werd onlangs het 3.141.593ste exemplaar in de originele versie verkocht. En het zal wel geen toeval zijn dat de hoofdpersoon Pi een schipbreuk overleeft en precies $\underline{227}$ dagen in een reddingsboot/vlot (samen met een Bengaalse tijger) blijft ronddobberen ($\frac{22}{7}$ is een bekende benadering van $\pi$).

    Life of Pi

    Dit is hoe de hoofdpersoon, Pi, aan zijn bijnaam komt:

    My name is Piscine Molitor Patel, known to all as - I double underlined the first two letters of my given name - Pi Patel. For good measure, I added, $\pi$ = 3.14, and I drew a large circle, which I then sliced in two with a diameter, to evoke that basic lesson of geometry.
  • $\ldots$ dat op 12 september 2012 vijf vliegtuigen met dot-matrix luchtschrifttechnologie duizend decimalen van $\pi$ hebben geschreven in de hemel van de San Francisco Bay Area op een hoogte van 3.000 meter?
    De cijfers waren elk bijna 400 m hoog, en ze waren geplaatst in een 161 km lange lus: 

    Pi in th Sky

    Dit evenement werd Pi in the Sky genoemd, en het is een $\pi$-record: de grootste fysieke uitdrukking voor het getal $\pi$ ooit.
  • $\ldots$ dat de Poolse wiskundige Adam Adamandy Kochanski in 1685 een eenvoudige constructie van (een benadering van) het getal $\pi$ heeft gepubliceerd? Hier is ze:

    Kochanski
  • $\ldots$ dat er heel wat materiaal is voor $\pi$-verzamelaars?

    pi memorabilia

    (Dank u, Imanol, voor de fles!)
  • $\ldots$ dat het volgende geldt? $$ \cos (\pi \cos (\ln (\pi+20))) = -1 $$ Als je het nog niet wist, het heeft geen zin het te onthouden, want het is niet waar. Het is slechts een benadering, maar een hele goede. Als je dit berekent met je rekentoestel, dan krijg je inderdaad $-1$. Maar de werkelijke waarde is: $$ -0.99999999999999999717719... $$ die zeer dicht bij $-1$ zit . Dit is een gevolg van het feit dat $e^\pi-\pi =19.999099979...$.
  • $\ldots$ dat er een limerick is die het trieste verhaal vertelt van William Shanks (1812-1882)? Hij berekende de eerste 707 decimalen van het getal $\pi$ met de hand. Het kostte hem 15 jaar. Later, in 1944, werd ontdekt dat alleen de eerste 527 correct waren. De limerick is van de hand van N. Rose.

    Seven hundred seven, Shanks did state,
    Digits of $\pi$ he would calculate
    And none could deny
    It was a good try
    But he erred in five twenty-eight.
dilbert


Geschreven in Actuele wiskunde | 0 Reacties | Vaste link | Afdrukken


De eerbaarheid van de priemgetallen

23. Februari 2013, 21:19

Volmaakte getallen en een Franse monnik

Historici kibbelen nog een beetje over wanneer juist de mens de priemgetallen ontdekt heeft, maar we kunnen wel stellen dat ze voor het eerst uitgebreid bestudeerd zijn in de Griekse oudheid. Een getal zoals 6 werd door de Grieken (en nog altijd) een samengesteld getal genoemd omdat het kan ontbonden worden als product van andere getallen: 6 = 2 × 3. Priemgetallen zijn enkel deelbaar door 1 en zichzelf en spelen dus binnen de getaltheorie de rol van basiselementen zoals de atomen in de chemie. Maar deze metafoor is niet erg geslaagd, want er bestaat niet zoiets als een tabel van Mendeljev voor priemgetallen.


euclidesOm te beginnen zijn er oneindig veel priemgetallen, reeds in de 3de eeuw voor Christus bewezen door Euclides. Bovendien duiken ze willekeurig op tussen de natuurlijke getallen en schijnen ze zich aan geen enkele wet of regel te storen (zoals “onkruid”, om met Don Zagier te spreken). Anderzijds is het een boeiend tijdverdrijf voor getaltheoretici om juist tussen deze schijnbare willekeur naar patronen te zoeken. Lees bijvoorbeeld onze vroegere blogbijdrage over de eenzaamheid van de priemgetallen. Iets minder bekend (voor het grote publiek) is dat de oude Grieken de samengestelde getallen onderverdeelden in drie categorieën:

Volmaakte getallen: als de som van de delers (behalve het getal zelf) juist gelijk is aan het getal. Bijvoorbeeld: 6=1+2+3 is een volmaakt getal.

Gebrekkige getallen: als de som van de delers (behalve het getal zelf) kleiner is dan het getal. Bijvoorbeeld: 8 is gebrekkig want 1+2+4 < 8.

Overvloedige getallen: als de som van de delers (behalve het getal zelf) groter is dan het getal. Bijvoorbeeld: 12 is overvloedig want 1+2+3+4+6 > 12.

Aan volmaakte getallen werden mystieke en religieuze eigenschappen toegeschreven, niet alleen door de Grieken, maar ook door de christenen, de Egyptenaren en wie weet nog altijd heden ten dage door sommige esoterische zonnegroetende medemensen. Nochtans kenden de Grieken maar 4 volmaakte getallen: 6, 28, 496 en 8128. Merk op dat al deze volmaakte getallen even zijn. Tot nu toe heeft men nog geen enkel oneven volmaakt getal gevonden en er zijn sterke aanwijzingen dat oneven volmaakte getallen niet bestaan.

De Grieken hadden deze volmaakte getallen gevonden met behulp van een procedé van Euclides: neem een priemgetal p en bereken 2p-1(2p-1):

p = 2: 21(22−1) = 6
p = 3: 22(23−1) = 28
p = 5: 24(25−1) = 496
p = 7: 26(27−1) = 8128.

Helaas liep het mis bij p = 11. Inderdaad, 210(211-1) is niet volmaakt. De reden van het falen is dat 211−1 = 2047 = 23×89 geen priemgetal is, een inzicht dat al aanwezig was bij Euclides.
Maar het was wachten tot de 18de eeuw vooraleer Leonhard Euler (Zwitserse wiskundige buiten categorie) dit mooi verband tussen priemgetallen en volmaakte getallen bewees:

een even getal N is juist dan volmaakt als het
van de vorm 2(p-1)(2p-1) is met 2p-1 een priemgetal.

mersenneHet is niet moeilijk om aan te tonen dat 2p-1 enkel een priemgetal kan zijn als p een priemgetal is, maar dat dit niet voldoende is wordt geïllustreerd door 211−1 = 2047 = 23×89.
Op dit punt van het verhaal zijn we aanbeland bij de Franse monnik Marin Mersenne (1588-1648). We zouden veel kunnen vertellen over deze boeiende wiskundige, theoloog en filosoof, maar op dit moment beperken we ons tot zijn befaamde studie van priemgetallen van de vorm 2p-1. Dergelijk priemgetal wordt sindsdien een Mersennepriemgetal genoemd en Mp genoteerd. Mersenne publiceerde in 1644 een lijst van 11 priemgetallen van dit type, waarvan hier de eerste 8:
p Mp
2 3
3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647

Wie goed heeft opgelet, beseft dat deze lijst meteen ook 8 volmaakte getallen oplevert, via de formule van Euclides-Euler: N = 2p-1(2p-1). Mersenne had ook nog M67, M127 en M257 in zijn lijst opgenomen, maar hiervan ontdekte men achteraf dat M67 en M257 samengestelde getallen zijn. Onze monnik had dus geen foutloos werk afgeleverd, en had bovendien M61, M89 en M107 over het hoofd gezien, die wel priemgetallen waren.

Een priemrecord

In de loop der geschiedenis is deze lijst van Mersennepriemgetallen druppelsgewijs aangevuld. Zoals andere priemgetallen worden ook zij steeds zeldzamer naarmate de getallen langer worden, het is zelfs geenszins zeker dat er oneindig veel Mersennepriemgetallen bestaan. Behalve hun rol in het construeren van volmaakte getallen, zijn Mersennepriemgetallen ook handig in de zoektocht naar grote priemgetallen.

cooperJuist vanwege het ontbreken van enige regelmaat of formule voor priemgetallen is het zelfs voor de snelste supercomputers uitputtend werk om voor een groot getal (van pakweg een miljoen cijfers) na te gaan of het al dan niet een priemgetal is.
Deze maand werd in de betere kranten en tijdschriften melding gemaakt van een opmerkelijk record: op 25 januari 2013 heeft Curtis Cooper, een wiskundige uit Missouri, een priemgetal met 17.425.170 cijfers ontdekt. Dit is het grootste tot nu toe bekende priemgetal, en bovendien een Mersennepriemgetal: 257.885.161-1.
Dit is geen toeval, alle vorige records van de laatste 20 jaar waren ook Mersennepriemgetallen. Het zit namelijk zo dat voor getallen van de vorm Mp = 2p-1 de zogenaamde Lucas-Lehmertest ontwikkeld is, waarmee ze sneller ontmaskerd worden als een priemgetal dan een ander getal van dezelfde lengte. Opgelet, het blijft een titanenwerk natuurlijk (het vorige record dateert alweer van 5 jaar geleden).
Eigenlijk is Curtis Cooper een deelnemer van het vrijwilligersproject Great Internet Mersenne Prime Search (GIMPS), waarin wereldwijd ongeveer 360.000 computerprocessoren verbonden zijn in een grid-configuratie, die op piekmomenten ongeveer 150 × 1012 berekeningen per seconde maakt.
Het priemgetal dat in 25 januari 2013 gevonden werd door Curtis (en nadien door anderen gecontroleerd) is het 48ste Mersennepriemgetal dat tot nu toe ontdekt werd. En wie weet, misschien het allerlaatste dat sowieso voorhanden is. Misschien heeft God om een of andere reden beslist om ons maar 48 volmaakte getallen te schenken.

priem


Grote priemgetallen en veilig bankverkeer 

Maar kan je daar nu ook iets nuttigs mee doen, met grote priemgetallen? hoor ik je al vragen. Sinds kort wel. En wel als gevolg van een ander probleem ermee, dat zelfs niet met 360.000 computers is op te lossen. We proberen het even uit te leggen.

Het is heel eenvoudig twee grote getallen met elkaar te vermenigvuldigen. Neem bijvoorbeeld 352617 en 273872. Wil je hiervan het product hebben, dan neem je een rekentoestel, je tikt de getallen in en je krijgt je resultaat:

352617 × 273872 = 96571923024

Maar het omgekeerde is lastiger: je krijgt een groot getal, zoek de factoren ervan. Bijvoorbeeld het getal 3141592657389793238462643383. Zelfs als je weet dat dit getal het product is van slechts twee priemfactoren, het is heel moeilijk om die twee factoren te bepalen, want in essentie moet je daarvoor achtereenvolgens de getallen 2,3,4,... als delers testen.
Opmerking: het resultaat is overigens

3141592657389793238462643383                                
= 21205634761907 
× 148148956287469

Er is iets asymmetrisch aan de zaak, en die asymmetrie kan gebruikt worden om een zeer veilig beveiligingssysteem te maken. We schetsen de grote lijnen.
Het gaat hier om het veilig uitwisselen van informatie tussen twee partijen, laten we het even houden op een bank en haar klanten. Een van de klanten wil informatie doorsturen naar de bank, en allle klanten hebben van de bank een "sleutel" gekregen waarmee ze die informatie kunnen versleutelen. De sleutel bestaat uit 2 getallen, een van beide is het product van 2 grote priemgetallen. We zullen het eenvoudig houden, en met kleine priemgetallen werken, stel 17 en 19, met product 323. Het andere getal is tamelijk willekeurig te kiezen, neem bijvoorbeeld 7. Dus alle klanten kennen die 2 getallen: 7 en 323.
Klant A wil iets doorsturen naar de bank, het kan bijvoorbeeld ook een tekst zijn, of een woord, laten we het houden op het woord BAD (onwaarschijnlijk, ik geef het toe). Wat moet de klant dan doen om deze boodschap te versleutelen?
Eerst moet hij met een welbepaald systeem dat de bank ook kent dit woord omzetten naar een getal, voor de eenvoud zullen we elke letter laten overeenkomen met de plaats ervan in het alfabet.
BAD wordt dan 214.
Dat resultaat verheft de klant tot de zevende macht (7 was het eerste deel van de sleutel), dus de klant berekent:

214 × 214 × 214 × 214 × 214 × 214 × 214
= 20 554 002 898 923 904

Hij kijkt hoeveel maal 323 (het tweede deel van de sleutel) in dit getal past, en bepaalt de rest:

20 554 002 898 923 904 = 323 × 63 634 683 897 597 + 73

Die rest 73 is het bericht dat de klant doorstuurt naar de bank.
En wat doet de bank daarmee? De bank, die de klantsleutel 7, 323 gegenereerd heeft, heeft zelf een andere sleutel om te decoderen. Deze sleutel is een extra getal dat kan berekend worden uit de klantsleutel 7, 323 maar enkel indien je de priemfactoren kent van 323. Zonder die priemfactoren kan het niet. Dus om de code te breken moet je het tweede deel van de klantsleutel kunnen ontbinden in factoren, en voor een product van twee erg grote priemgetallen, zeg zo'n 300 cijfers elk, is dat op dit ogenblik onmogelijk.
De bank heeft in dit geval sleutel 247. (Waar die vandaan komt, dat laten we in het midden. Maar het bepalen ervan veronderstelt kennis van de ontbinding 323=17 × 19.)
Om de boodschap te decoderen doet de bank overigens precies hetzelfde als de klant deed bij versleutelen: het doorgestuurde bericht wordt tot de macht 247 gezet:

73247 = 174...(in totaal 461 cijfers)...897

Opnieuw wordt dan de rest bepaald bij deling van dit getal door 323:

174...897 = 323 × 538...(in totaal 458 cijfers)...321 + 214

En je ziet het: de rest die er uitkomt is precies het getal dat de klant doorstuurde, 214 = BAD, Je kan hiermee zelf gaan experimenteren als je wil: ga naar www.wolframalpha.com, kies een getal kleiner dan 323, verhef het tot de zevende macht en neem de rest bij deling door 323. Dat doe je zo voor 214 in wolframalpha:
214^7 mod 323
Wat er uitkomt verhef je dan op dezelfde manier tot de macht 247. De rest na deling door 323 is je oorspronkelijk getal.
Het heeft iets magisch, en als je een rekenwonder bent, kan je er iedereen mee verbazen. Probeer het zeker ook eens met het woord dat ik eerst had willen nemen, namelijk BED. BED = 254. Er staat je een verrassing te wachten...
Bovenstaande methode wordt RSA genoemd, naar de uitvinders ervan, Rivest, Shamir, Adleman. Bij de banken gaat het er iets anders aan toe, maar dit is wel de basis.



Geschreven in Algemeen | 0 Reacties | Vaste link | Afdrukken


Vakantie? Wiskunst en leesvoer!

16. Juli 2012, 10:17

Nu en dan breekt de zon door de wolken, en lijkt het ons een goed idee even een frisse neus te halen. We reden recht naar het gemeentehuis van De Panne om daar te gaan genieten van een kunstwerk in het kader van Beaufort04. Een eerder wiskundig kunstwerk, wat hadden jullie gedacht? Van de Maltese kunstenaar Norbert Francis Attard (geboren in 1951), met als titel Boundaries of Infinity:

attard


Je ziet er o.a. de rij van Fibonacci, en de gulden spiraal.
Het goede nieuws hier is dat het er ook na Beaufort04 nog blijft staan. 
Een typisch voorbeeld van wisku(n)st. 
Vandaar ging het naar Brugge, waar we bij de echte vader van de Wisconst uitkwamen: Simon Stevin (1548-1620) wiens standbeeld prijkt op het ... Simon Stevinplein. Met de moderne camera kan je zo'n beeld dichterbij brengen, en dus hebben we ook de details kunnen bestuderen:

stevin

Bovenaan rechts zie je een afbeelding die te maken heeft met de hydrostatische paradox, en net daaronder de beroemde Clootcrans (die o.a. door Richard Feynman de hemel werd ingeprezen). Je herkent ook een tekening van de Zeilwagen die door Stevin werd uitgevonden, en die door Nederlandse schrijver Hugo Grotius (1583-1645) als volgt bezongen werd:

Illum qui numeros & rerum pondera novit,
Qui fluxum aequorea comperit unus aquae,
Et motus terrae varios Stevinius auctor
Iussit arenosae credere vela viae.

(mogelijke vertaling, van Prudens Van Duyse uit 1846:
Stevin, wiens geest en yvervolle moed
De Weeg- en Cyferkunst, als schepper, kon verryken -
Stevin, die eerst der zeeën vloed
en ’s aerdrijks omzwaei heeft bevroed
beval het zeil zich d’oever te vertrouwen.)

Maar kan iemand me vertellen wat het onderste detail voorstelt? Graag in een reactie op deze blog!

Vakantie betekent voor mij ook: lezen. Naar jaarlijkse traditie bespreek ik hier dan ook enkele boeken die ik recent met plezier heb gelezen.

Het eerste boek gaat over de wiskunde achter de Sudoku. Maar dan ook alle wiskunde achter de Sudoku.
Wie lost er eens niet graag een Sudoku op?
Hier zie je er alvast een waarvan de vorm ons wel aanstaat. Zien jullie waarom?


Sudoku

In het boek vind je bijvoorbeeld een sudoku voor mensen die het erg druk hebben:

sudoku
  


Taking Sudoku Seriously
Jason Rosenhouse en Laura Taalman, Taking Sudoku Seriously. The Math Behind the World's Most Popular Pencil Puzzle.
Oxford University Press (2011) 214 pagina's. 

Dit is een prachtig, in kleuren uitgegeven boek in verband met sudoku's. Het gaat niet zozeer over hoe je een sudoku moet oplossen, maar wel over allerlei dingen die met sudoku te maken hebben. Hoeveel sudoku's zijn er mogelijk, en hoe bereken je dat aantal? Hoe maak je zelf een sudoku vertrekkend van een 9 bij 9-veld dat volledig leeg is? Wat is het verband met Grieks-Latijnse vierkanten? 
Sudoku's worden ook gebruikt als aanleiding om over wiskunde te praten, meer bepaald over bijvoorbeeld grafentheorie, en over veeltermen.
Het boek is geschreven net voor bewezen werd dat er minstens 17 getallen bij de start moeten ingevuld zijn om een unieke oplossing te hebben (lees meer hier). Op dat punt hadden de auteurs dus pech. 
Het laatste hoofdstuk bevat sudoku-varianten, voor de liefhebbers van het genre. Met oplossingen.

Formuledichtheid: Θ Θ Ο Ο Ο
Moeilijkheidsgraad: Θ Θ Ο Ο Ο
Score: Θ Θ Θ Θ Ο




Dat mathematics en magic goed samengaan, dat weten we al langer, dankzij Martin Gardner bijvoorbeeld. Zelf vind ik het goochelen met speelkaarten erg aantrekkelijk, ook omdat je er weinig meer voor nodig hebt dan een spel kaarten. Een van de bekendste kaarttrucs die gebaseerd is op een wiskundig principe is de truc met de 21 kaarten.


21

Lees meer hier, de eerste truc.
Over de auteurs van het volgende boek valt heel wat te vertellen. Persi Diaconis begon als goochelaar, en ging later wiskunde studeren. Ron Graham was niet alleen president van de American Mathematical Society maar ook van de International Juggler's Association. Beiden hebben ze Erdösgetal 1.



Magical Mathematics
Persi Diaconis en Ron Graham, Magical Mathematics. The Mathematical Ideas that Animate Great Magic Tricks. Princeton University Press (2012) 244 pagina's.

Ook een prachtig boek. Over wiskunde en goocheltrucs, met en zonder speelkaarten. Eerst met. Het eerste hoofdstuk begint met Baby Hummer, een truc genoemd naar de uitvinder ervan, Bob Hummer, en een aanloop naar een uitgebreide versie: Royal Hummer. Hier en daar vind je een stelling, met bewijs. Hoofdstukken 2, 3 en 4 gaan over de Bruijn-rijen, en hoe ze in kaarttrucs nut hebben. Dan is er een hoofdstuk over het geweldige Gilbreath-principe (zie ook het filmpje hier), en het verband met de Mandelbrotverzameling. En een over perfecte en andere shuffles. 
Vervolgens gaan de auteurs op zoek naar de oudste goocheltrucs, bespreken ze de magie in de I Ching, hebben ze het over jongleren en tot slot belichten ze op een persoonlijke manier 7 goochelaars. 

De wiskunde achter de trucs is soms wel lastig, maar je kan die stukken ook gewoon overslaan. De trucs zijn erg leuk.

Formuledichtheid: Θ Ο Ο Ο Ο
Moeilijkheidsgraad: Θ Θ Θ Ο Ο
Score: Θ Θ Θ Ο Ο




Het volgende boek gaat volledig over het Handelsreizigersprobleem (Traveling Salesman Problem of TSP). Het probleem is het volgende: gegeven n steden en de afstanden tussen elk paar van deze steden (via bestaande wegen).

traveling salesman

Een handelsreiziger moet elk van deze steden precies eenmaal bezoeken. Bepaal de kortste weg die hiervoor kan worden gebruikt.
Dit probleem kadert in de grafentheorie, een tak van de wiskunde die geïnitieerd werd door Leonhard Euler met zijn 7 bruggen van Königsberg: de Russische stad Königsberg bestaat uit twee eilanden en een deel van de oevers van de Pregel. Er zijn 7 bruggen die de verschillende delen van de stad met elkaar verbinden. De vraag is of je deze stad kan bezoeken door elke brug precies 1 keer te gebruiken.

Bridges

Het antwoord is: neen.
TSP is gerelateerd aan het P versus NP-probleem, een van de millenniumproblemen.



In Pursuit of The Traveling Salesman
William J. Cook, In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation. Princeton University Press (2012) 228 pagina's.

In dit boek lees je echt alles over wat er op dit ogenblik geweten is in verband met het Handelsreizigersprobleem: geschiedenis, oplossingsmethodes, toepassingen, verbanden met andere disciplines. Omdat de auteur de zaken in detail beschrijft, is dit zeker geen gemakkelijk boek om te lezen. Hier en daar komt er ook wat algebra bij kijken. 
Het boek geeft wel een goed overzicht van deze bloeiende tak van de wiskunde.
 

Formuledichtheid: Θ Θ Ο Ο Ο
Moeilijkheidsgraad: Θ Θ Θ Ο Ο
Score: Θ Θ Ο Ο Ο




Ook elliptische krommen zijn hot topics in de wiskunde, en niet alleen omdat een ander millenniumprobleem, met name het vermoeden van Birch en Swinnerton-Dyer, in deze branche zit. Elliptische krommen worden o.a. gebruikt in de cryptografie, en het zou best kunnen dat je GSM elliptische krommen gebruikt om gegevens mee te versleutelen.



Elliptic Tales
Avner Ash en Robert Gross, Elliptic Tales. Curves, Counting and Number Theory. Princeton University Presss (2012) 253 pagina's. 

Dit boek is te moeilijk voor de leek. Je moet al wel wat wiskunde kennen om het tot het einde toe te kunnen volgen. Maar het loont om door te zetten: als je er doorheen geraakt, dan begrijp je waar het vermoeden van Birch en Swinnerton-Dyer precies over gaat. En je komt op de weg daar naartoe heel wat te weten over elliptische krommen.
De auteurs doen hun best om alles zeer geleidelijk op te bouwen, en ze zeggen wel dat je niet zoveel voorkennis nodig hebt, maar enkele jaren wiskundestudies zijn toch echt wel nodig.

Formuledichtheid: Θ Θ Θ Ο Ο
Moeilijkheidsgraad: Θ Θ Θ Θ Ο
Score: Θ Ο Ο Ο Ο   
Score voor wiskundigen:
Θ Θ Θ Θ Ο




Nog twee te gaan. We beperken ons tot de essentie.



The Universe in Zero Words
Dana Mackenzie, The Universe in Zero Words. The Story of Mathematics as Told through Equations. Princeton University Press (2012) 224 pagina's.

Dit boek is ideaal voor de geïnteresseerde leek die wel wat wiskunde gehad heeft. De titel zegt het al: het gaat om een geschiedenis van de wiskunde verteld aan de hand van de belangrijkste wiskundige formules en vergelijkingen. Het is iets breder: ook belangrijke vergelijkingen uit de fysica, zoals bijvoorbeeld $E=mc^2$, komen aan bod.

Het boek is opgedeeld in vier delen: de oudheid - tot de 19de eeuw - de 19de eeuw - de 20ste eeuw. Korte hoofdstukken, die erg leuk zijn om te lezen. Met mooie illustraties. Een aanrader! Kan zeker ook als coffee table book gebruikt worden.

Formuledichtheid: Θ Θ Ο Ο Ο
Moeilijkheidsgraad: Θ Θ Ο Ο Ο
Score: Θ Θ Θ Θ O




A Wealth of Numbers
Benjamin Wardhaugh, A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing. Princeton University Press (2012) 370 pagina's.

Je zou kunnen denken dat dit boek perfect past in deze blog, die de bedoeling heeft de wiskunde te populariseren (of is het andersom: deze blog past perfect in dit boek?). Het gaat om een anthologie: een bundeling van een aantal teksten die een periode van meer dan 500 jaar omspannen, en die de bedoeling hebben de wiskunde te populariseren. 
De oudste tekst in dit boek dateert van 1481, en is een Engelse vertaling van een deel van een Frans boek uit 1246. Het gaat over vier van de seven vrie consten, o.a. de geometrie en de arithmetica. 
Puzzels, spelletjes, humor, dialogen, gedichten,... voor elk wat wils. 
Het is niet echt een boek dat je van het begin tot het einde doorleest. De teksten die er in voorkomen zijn ook niet altijd echt boeiend.

Formuledichtheid: Θ Θ Ο Ο Ο
Moeilijkheidsgraad: Θ Θ Ο Ο Ο
Score:  Θ Θ Ο Ο Ο






Geschreven in Actuele wiskunde | 5 Reacties | Vaste link | Afdrukken


Lachen met wiskundigen

14. Juni 2012, 10:21

In een periode dat studerend Vlaanderen met proefwerken of examens zit, is het misschien niet zo opportuun veel over wiskunde te schrijven. Daarom gaan we de lichtere toer op door enkele anekdotes over bekende en minder bekende wiskundigen te vertellen. Toch een waarschuwing hierbij: hoewel de foto's die je hieronder vindt de indruk zouden kunnen wekken dat wiskundigen saaie en kleurloze figuren zijn, willen we dat met klem tegenspreken. Moest je denken dat er toch blijkbaar iets mis is met wiskundigen, dan willen we daar tegenoverstellen dat wiskundigen vaak gewoon een ander soort gevoel voor humor hebben. Noodgedwongen moeten we ons tot mannen beperken, niet omdat vrouwelijke wiskundigen eerder schaars zijn, maar omdat ze zich minder laten betrappen op afwijkend gedrag. 


G. H. Hardy

S. Ramanujan
1729 staat bekend als het Ramanujan-Hardy getal.

De Britse wiskundige G. H. Hardy (1877-1947), die gespecialiseerd was in getaltheorie, en vooral bekend is door het feit dat hij het wiskundige wonderkind, de Indier Srinivasa Ramanujan (1887-1920), naar Cambridge haalde, vertelde dat hij op ziekenbezoek ging bij Ramanujan, en dat ze het op een bepaald moment hadden over het nummer van de taxi waarmee Hardy gekomen was. Hardy vond dat nummer, 1729, weinig interessant.
"Helemaal niet", zei Ramanujan daarop, "1729 is het kleinste getal dat op twee verschillende manieren te schrijven is als de som van twee derdemachten."

Inderdaad: $$1729 = 1^3 + 12^3 = 9^3 +10^3 $$

N. Wiener
Norbert Wiener (1894-1964), een toegepast wiskundige, was bekend om zijn verstrooidheid.

Op een dag ging hij naar een conferentie, en parkeerde zijn auto op de (grote) parking van de universiteit. Na de lezingen liep hij terug naar de parking, maar omdat hij vergeten was waar hij zijn auto had gezet, en eigenlijk ook niet meer wist hoe zijn auto eruit zag, was hij genoodzaakt daar te blijven wachten tot alle andere auto's weg waren.

Op een bepaalde ogenblik verhuisde hij met zijn familie naar een ander huis een paar blokken verder. Zijn echtgenote, die wist dat ze aan haar man toch niets had bij zo'n bedoeningen, had hem naar zijn werk gestuurd 's morgens. 's Avonds zou dan wel alles verhuisd zijn. Voor de zekerheid had zij hem een papiertje met het nieuwe adres meegegeven. Na het werk wist Wiener niet meer wat zijn nieuwe adres was, en al evenmin wat er met dat papiertje gebeurd was. Hij ging dus maar gewoon naar zijn oude huis, en zag daar een kind staan waar hij aan vroeg: "Weet jij misschien naar welk adres de Wieners verhuisd zijn?" Waarop het meisje antwoordde: "Ja, papa. Mama dacht wel dat je naar hier zou komen, en heeft mij daarom gestuurd om je de weg te wijzen."

H. Poincare
Henri Poincaré (1854-1912) was een van de grootste Franse wiskundigen. Over hem doet het volgende verhaal de ronde.

Poincaré ging elke dag een brood kopen bij de bakker op de hoek. Hij merkte al snel op dat het brood, dat normaal 1 kg moest wegen, vaak merkelijk veel minder woog, en hij hield dan ook een jaar lang zorgvuldig bij wat het dagelijkse gewicht van het brood was. Hij zette de resultaten hiervan uit op een grafiek, en die bleek een mooie Gausscurve te zijn met als gemiddelde 950 g. Hij diende een klacht in bij de lokale politie, en de bakker kreeg een waarschuwing.

Een jaar later diende Poincaré opnieuw klacht in. Hoewel het brood dat hij kocht bij de bakker nu wel het juiste gewicht had, kon hij bewijzen dat de bakker toch zijn klanten bedroog. De politie confronteerde de bakker met de aanklacht, waarop die de vraag stelde: "Hoe kan Poincare´ nu weten dat mijn broden toch niet het juiste gewicht hebben als er bij hemzelf geen problemen zijn?"
Poincaré antwoordde met deze grafiek.

K. Godel en A. Einstein

K. Godel en A. Einstein
Logicus Kurt Gödel (1906-1978) was niet van deze wereld. In 1939 was hij uitgeweken naar de Verenigde Staten, en na enkele jaren in Princeton besloot hij mee te doen aan het examen om Amerikaans staatsburger te worden.
Bij het bestuderen van de Amerikaanse grondwet ontdekte hij allerlei inconsistenties, en was daardoor erg in de war. Zijn collega John Von Neumann wist hem echter duidelijk te maken dat als je de zaken op een bepaalde manier bekeek, dat er dan geen logische problemen optraden.
De dag van het examen kwam. Albert Einstein (rechtsboven) en Oskar Morgenstern (linksonder) begeleidden hem naar het examen. De rechter die het examen afnam vond het geweldig eens te kunnen praten met een beroemdheid zoals Einstein, en ze hadden het o.a. over Nazi-Duitsland. Op een bepaald ogenblik richt de rechter zich tot Gödel en zegt: "Maar je hebt waarschijnlijk wel gemerkt bij het doornemen van onze grondwet dat zoiets hier nooit kan gebeuren. Waarop Gödel: "Maar ...", en hij kreeg prompt (onder de tafel) een stamp van Morgenstern. Gödel kreeg het staatsburgerschap.

A. Besicovitch
Abram Besicovitch (1891-1970) was een Russisch wiskundige die de wereld rondreisde en in 1927 in Cambridge (Engeland) terechtkwam.

Op een dag ging hij op bezoek bij een collega die enkele honderden kilometers ver woonde. Dit gebeurde in een tijd dat telefoneren om een afspraak te maken erg duur was, dus hij stapte gewoon in zijn auto, reed enkele uren, belde aan en was blij te constateren dat zijn collega thuis was. Al snel ging het over wiskunde, en het was makkelijk Besicovitch te overtuigen om te blijven voor de lunch.
Na de middag werkten ze verder, het werd avond, en Besicovitch's collega nodigde hem uit voor het avondeten. "Maar moet je niet even naar huis bellen om je vrouw te laten weten dat je nog hier bent? Misschien maakt ze zich wel ongerust, of is ze al eten aan het koken." Waarop Besicovitch antwoordt: "Dat is niet nodig. Ze weet dat ik nog hier ben: ze wacht in de auto."

P. Erdos
We sluiten af met Paul Erdös (1913-1996), een van de grootste wiskundigen van de vorige eeuw, die we ook al op deze blog zijn tegengekomen.

Erdös had de gewoonte wiskundecollega's op te bellen, op willekeurige momenten. Hij kende hun telefoonnummers van buiten, maar kende van niemand de voornaam. De enige die hij aansprak met zijn voornaam was Tom Trotter, die hij Bill noemde.

Er
dös ontmoette eens een wiskundige op de een of andere conferentie, en vroeg hem van waar hij was. Toen bleek dat hij werkte in Vancouver, zei Erdös: "Dan ken jij waarschijnlijk mijn goede vriend Elliott Mendelson?"
De ander antwoordde: "Ik BEN je goede vriend Elliott Mendelson."

Zie ook het
Erdös-getal en Erdös-Bacon getal.

Bronnen:

Steven Krantz, Mathematical Apocrypha: Stories and Anecdotes of Mathematicians and the Mathematical, The Mathematical Association of America (2002)

Steven Krantz, Mathematical Apocrypha Redux: More Stories and Anecdotes of Mathematicians and the Mathematical, The Mathematical Association of America (2005)

(over Paul Erdös) Paul Hoffman, The Man Who Loved Only Numbers, Hyperion (1998) of de Nederlandse vertaling bij Bert Bakker (1999)

(over Srinivasa Ramanujan) Robert Kanigel, The Man Who Knew Infinity, Washington Square Press (1992)

(over Srinivasa Ramanujan) David Leavitt, The Indian Clerk, Bloomsbury (2008) of de Nederlandse vertaling bij De Harmonie (2009)

en natuurlijk ook het volgende recent verschenen boek:


HershSteiner


Rueben Hersh en Vera John-Steiner
, Loving + Hating Mathematics. Challenging the Myths of Mathematical Life, Princeton University Press (2011) 416 pagina's. 

Dit boek gaat niet zozeer over wiskunde, maar over wiskundigen, over hoe ze functioneren, wat hen triggert, waarom ze wiskunde doen, hoe ze omgaan met anderen,... Hersh en John-Steiner proberen komaf te maken met een aantal mythes die rond wiskundigen hangen, zoals de mythe dat het eenzaten zijn, en eerder asociale wezens. Ze doen dit met voorbeelden, en proberen hun punt te maken aan de hand van verhalen en anecdotes over wiskundigen.
Een deel van het boek heeft rechtstreeks betrekking op het onderwijssysteem in de Verenigde Staten, en is als dusdanig voor ons niet zo interessant. Maar voor de rest is het zeker een aanrader.

Formuledichtheid: Θ Ο Ο Ο Ο
Moeilijkheidsgraad: Θ Ο Ο Ο Ο
Score: Θ Θ Θ Ο Ο




Geschreven in Actuele wiskunde | 0 Reacties | Vaste link | Afdrukken


De oneindige knuffelfactor van het getal pi

14. Maart 2012, 10:25

Nu de magie van het getal $\pi$ eindelijk is doorgedrongen tot de kring der BV's (bedankt Tom Waes!), en vrienden/familieleden op feestjes spontaan en trots de decimalen ervan beginnen te reciteren, willen we ervoor zorgen dat deze $\pi$-dag zeker niet onopgemerkt voorbij gaat. Naar jaarlijkse traditie hebben we een aantal $\pi$-curiosa bij elkaar gezocht.

pidag

pi

Wist je ...
  • $\ldots$ dat het vandaag 14 maart $\pi$-dag is? Waarom? Omdat in de Amerikaanse schrijfwijze de datum 14 maart genoteerd wordt als 3/14 en 3,14 is een benadering voor het getal $\pi$.
  • $\ldots$ dat veel decimalen van het getal $\pi$ berekenen een manier is om in het Guinness Book of Records te komen? De berekening van decimalen van $\pi$ is een lastige zaak omdat er geen regelmaat in zit.

    pi

  • $\ldots$ dat de Japanse ingenieur Shigeru Kondo in oktober 2011 zijn eigen wereldrecord decimalen-van-$\pi$-berekenen verdubbeld heeft, precies zoals hij dit de vorige keer had aangekondigd ? In totaal werden nu 10 000 000 000 000 decimalen berekend, op zijn zelfgemaakte computer met een harddisk van 48 TB (1,5 keer zo groot als de vorige).
  • $\ldots$ dat het getal $\pi$ ook een belangrijke rol speelde in een aflevering van de tv-reeks Star Trek? Een wezen van een vreemde planeet had de boordcomputer overgenomen. Spock slaagde erin het ding uit de computer te krijgen door deze laatste de opdracht te geven $\pi$ te berekenen tot op de laatste decimaal.

    star trek pi

  • $\ldots$ dat er allerlei mooie wiskundige formules zijn waarin het getal $\pi$ voorkomt? Welke vinden jullie de mooiste? $$ {}\hspace{-0.2cm}\frac{2}{\pi} \!= \textstyle\!\sqrt{\frac{1}{2}} \!\cdot\! \sqrt{\frac{1}{2} \!+\! \frac{1}{2} \!\cdot\! \sqrt{\frac{1}{2}}} \!\cdot\! \sqrt{\frac{1}{2} \!+\! \frac{1}{2} \!\cdot\! \sqrt{\frac{1}{2} \!+\! \frac{1}{2} \!\cdot\! \sqrt{\frac{1}{2}}}} \!\cdot\! \ldots $$ $$\frac{2}{\pi} = \frac{1\cdot 3}{2 \cdot 2} \cdot \frac{3 \cdot 5}{4 \cdot 4} \cdot \frac{5 \cdot 7}{6 \cdot 6} \cdot \ldots $$ $$ \frac{\pi^2}{6} = 1 + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \ldots + \frac{1}{n^2} + \ldots $$ $$ \sqrt{\pi} = \int\limits_{-\infty}^{+\infty} e^{-x^2} \, d x $$ $$ \sqrt{\pi} \cdot \sum_{n=-\infty}^{+\infty} e^{-n^2} = \sum_{n=-\infty}^{+\infty} e^{-n^2\pi^2} $$
  • $\ldots$ dat er ook uitdrukkingen voor het getal $\pi$ ontdekt zijn maar nog niet bewezen? Zoals deze: \[ \frac{32}{\pi^3} = \sum_{n=0}^\infty r(n)^7 (1 + 14 n + 76 n^2 + 168 n^3) \cdot \frac{1}{8^{2n}} \] waarbij \[ r(n) = \frac{(1/2)_{n}}{n!} = \frac{1/2 \cdot 3/2 \cdot \, \ldots \, \cdot (2n-1)/2}{1 \cdot 2 \cdot \ldots \cdot n} \]
  • $\ldots$ dat Albert Einstein geboren werd op 14 maart?
  • $\ldots$ dat er recent een palindroomdag geweest is: 21 februari 2012? Inderdaad: 21022012. Op de volgende is het nog even wachten. Natuurlijk zijn er mensen die op zoek gegaan zijn naar palindromen in de decimale ontwikkeling van $\pi$. Op de 9128219-de plaats na de komma start de rij decimalen 9136319. Beide getallen zijn palindromen, meer nog het zijn ook allebei priemgetallen. We spreken dan van palpriemgetallen. Het zijn zelfs opeenvolgende palpriemgetallen!

  • pi cartoon

  • $\ldots$ dat de recent overleden Poolse dichteres Wislawa Szymborska (1923-2012, Nobelprijs literatuur in 1996) een gedicht heeft geschreven over het getal $\pi$? Het gaat zo:
    Het getal pi
    Het getal pi is bewonderenswaardig
    drie komma een vier een.
    Alle verdere cijfers zijn ook begincijfers,
    vijf negen twee omdat het nooit eindigt.
    Het laat zich zes vijf drie vijf niet vangen in één blik,
    noch acht negen door enige berekening,
    of zeven negen door enige verbeelding,
    en zelfs drie twee drie acht niet door de lach of vergelijking
    vier zes met wat ook maar
    twee zes vier drie ter wereld.
    De grootste slang op aarde houdt na ruim tien meter op.
    Sprookjesslangen doen hetzelfde, al wachten ze wat langer.
    De rij van cijfers die samen het getal pi vormen
    laat zich niet stuiten door de rand van het papier,
    kan verder gaan over de tafel, door de lucht,
    over muur, blad, vogelnest, wolken, recht omhoog,
    dwars door ‘ s hemels opgezwollen bodemloosheid.
    Ach, de staart van een komeet, wat is die kort, een muizenstaartje!
    Wat nietig de straal van een ster die zich in elke ruimte kromt!
    Terwijl hier twee drie vijftien driehonderd negentien
    mijn telefoonnummer jouw maat overhemd
    het jaar negentienhonderddrieënzeventig zes hoog
    het aantal inwoners vijfenzestig cent
    heupmaat twee vingers charade en code
    waarin zing o nachtegaal, zing toch en vlieg,
    maar ook verzoeke de rust te bewaren liggen besloten,
    en hemel en aarde zullen vergaan, maar niet het getal pi, nee, pi zeker niet,
    pi heeft nog altijd een niet onaardige vijf,
    niet de eerste de beste acht,
    zeker niet de minste zeven,
    waarmee het de bloedeloze eeuwigheid aanspoort, ja, aanspoort om maar voort te duren.

    (vertaling G. Rasch)
  • $\ldots$ dat er weinig postzegels te vinden zijn waar het getal $\pi$ op voorkomt? Dit is er een:

    pistamp

  • $\ldots$ dat je op youtube kan luisteren (en kijken) naar een muzikale interpretatie van het getal $\pi$? Meer bepaald hier.
  • $\ldots$ dat je het getal $\pi$ ook kan vieren op 22 juli, omdat 22/7 een benadering geeft voor $\pi$? We noemen deze dag dan ook: pi approximation day. 

    pi

  • $\ldots$ dat de uitvinder van pi-dag een fysicus is? Larry Shaw begon er mee in 1988.
  • $\ldots$ dat we de mooiste formule die $\pi$ bevat tot het einde bewaard hebben?

    pi

We ronden af met een tekening van René Magritte:

piano



Geschreven in Actuele wiskunde | 4 Reacties | Vaste link | Afdrukken


Vrouwen zijn beter in Lie-algebra

22. Februari 2012, 10:18

Deze conclusie kreeg enkele weken geleden de nodige persaandacht. Ze was het gevolg van een vergelijkende studie bij 2500 vrouwen en mannen uitgevoerd door NCP, een Britse uitbater van parkeergarages. Eigenlijk werd de competentie in het parkeren met auto’s getest, maar dit is in wezen hetzelfde als rekenen in een Lie-algebra, zoals direct duidelijk zal worden. Ziehier een overzicht van het bewuste NCP-onderzoek:


Mannen hebben dan wel minder tijd nodig (ze parkeren gemiddeld 5 seconden sneller), de kwaliteit van hun uiteindelijke parkeerresultaat blijkt eveneens minder.  Dit is onder andere te wijten aan het vrouwelijke talent in geduldig over en weer geschuifel om zich juist te positioneren (“reposition shuffle” en “central finish”). Laat het nu juist dit aspect zijn van stuurvaardigheid dat wiskundig beschreven wordt door de Lie-haak, een algebraïsche bewerking ingevoerd door de Noorse wiskundige Sophus Lie.

 

Helaas is de theorie van de Lie-algebra’s een zeldzaamheid in de curricula van onze academische opleidingen. Ingenieursstudenten krijgen het meer niet dan wel voorgeschoteld, en zelfs wiskundestudenten leren het enkel als ze een zuiver wiskundig traject kiezen. Nochtans is het een nuttig gereedschap voor iedere ingenieur die verantwoordelijk is voor de automatisering van robots of autonoom bewegende voertuigen. Laten we dit motiveren a.h.v. het parkeerprobleem.

Een eenvoudig model van een auto is een rechthoek in het vlak waarvan de positie voorgesteld wordt door de coördinaten $(x,y)$ van het centraal punt tussen de achterwielen, en de hoek $\theta$ tussen de centrale as en de horizontale richting (positieve $x$-as). We zeggen dat het voertuig drie vrijheidsgraden heeft: $x$, $y$ en $\theta$.

 

De positie van een auto wordt dus voorgesteld door een punt $(x, y, \theta)$ in een 3-dimensionale ruimte, de configuratieruimte. Merk terzijde op dat deze ruimte gekromd is, omdat de $\theta$-as niet rechtdoor loopt zoals de $x$-as of de $y$-as, maar eerder cirkelvormig is vermits de hoeken 0 en $2\pi$ samenvallen. Wanneer we parkeren, beschrijven we een traject $\gamma$ in deze ruimte, waarbij $x$, $y$ en $\theta$ op een “gladde manier” in de tijd variëren:

$$\gamma(t) = (x(t), y(t), \theta (t) )$$

 

Uit ervaring weten we dat we niet onmiddellijk alle richtingen uit kunnen met de auto. Jammer, want een zijdelingse beweging, loodrecht op de centrale wagenas, had wel handig geweest bij het parkeren. De ogenblikkelijke verandering van onze positie wordt wiskundig beschreven door de afgeleide naar de tijd $t$. Hiermee kunnen we de kinematische beperking van de autobesturing als volgt uitdrukken:

\begin{eqnarray*}(\frac{\mbox{d} x}{\mbox{d} t},\frac{\mbox{d} y}{\mbox{d} t}) &=& v\cdot (\cos\theta, \sin\theta)\\\frac{\mbox{d} \theta}{\mbox{d} t} &=& v\cdot c\end{eqnarray*}

waarbij $v$ de snelheid van het moment is (regelbaar met gaspedaal), en $c$ de kromming van de draaicirkel ($r=1/c$ is de “kromtestraal”, regelbaar met stuur). De eerste vergelijking drukt uit dat het referentiepunt van de auto ogenblikkelijk beweegt in de richting van de centrale wagenas, de tweede dat de snelheid $v$ gelijk is aan de hoeksnelheid vermenigvuldigd met de kromtestraal $r$.

In het kader van de 3-dimensionale configuratieruimte van de auto, geeft dit een beperking voor de afgeleide van het traject $\gamma(t)$ in de huidige positie, of met andere woorden, een beperking op de toegelaten richtingen in de raakruimte aan deze configuratieruimte in de huidige positie.

$$\gamma ‘(t) = \frac{\mbox{d}}{\mbox{d}t} \left(\begin{array}{c}x\\ y\\ \theta \end{array}\right) =\left ( \begin{array}{cc} \cos\theta & 0\\ \sin\theta & 0\\ 0&1 \end{array}\right)\cdot \left(\begin{array}{c} v\\ vc \end{array}\right)$$

 

Een auto mag dan wel 3 positievrijheden bezitten, hij heeft slechts 2 controlevrijheden, $v$ en $c$, wat kan vertaald worden in een tweedimensionaal deel van de raakruimte van uitvoerbare richtingen. Gelukkig bestaat er zoiets als “manoeuvres” (en ook zoiets als vrouwen die er goed in zijn). Deze manoeuvres gebruiken toegelaten raakvectoren en genereren zogenaamde gladde derivaties, die op hun beurt opnieuw realiseerbaar zijn als een stukje traject in de configurateruimte.

Een belangrijke operatie in de raakruimte die realiseerbare manoeuvres oplevert, is nu juist het Lie-product of Lie-haak, gedefinieerd als bewerking op vectorvelden $f$ en $g$:

$$[f, g] = (f\cdot \nabla) g – (g\cdot \nabla) f$$

waar informeel gesproken $(f\cdot\nabla)g$ de “verschuiving van vectorveld $g$ in de richting van $f$” voorstelt. Dankzij de kromming van de configuratieruimte van de auto zijn $(f\cdot\nabla)g$ en $(g\cdot\nabla)f$ niet hetzelfde, wat in een netto-beweging resulteert, die volgens de wiskundige theorie realiseerbaar is als een stukje traject:

Laten we deze Lie-haak eens uitwerken voor $f=(\cos\theta, \sin\theta, c)$ (snelheid $v=1$ en constante hoeksnelheid $c$) en $g=(\cos\theta , \sin\theta, 0)$ (voorwaartse beweging zonder draaien):

  

 

Dan observeren we dat dit “Lie-manoeuvre” een zijwaartse beweging oplevert. Dit vectorveld is bovendien onafhankelijk met de toegelaten ogenblikkelijke bewegingen van de auto, zodat uiteindelijk alle richtingen in de raakruimte realiseerbaar zijn. Hieruit volgt de Parkeerstelling :

Als de plaats groter is dan onze auto, dan kunnen we hem altijd in deze plaats parkeren (met eindig veel manoeuvres).

Deze Lie-algebra-techniek kan uitgebreid worden voor de besturing van wagens met een of meerdere trailers. Een resultaat hiervan kan bijvoorbeeld in onderstaand filmpje bewonderd worden:

Figuren zijn geleend van: “Motion Planning for Nonholonomic Vehicles. An Introduction” van Bill Triggs.



Geschreven in Actuele wiskunde | 0 Reacties | Vaste link | Afdrukken


17, en toch al wiskundig sexy

31. Januari 2012, 13:57

Nieuwsflash 17x17-probleem opgelost! Lees meer hier.

Toen hij 17 jaar was bewees de jonge Carl Friedrich Gauss dat de regelmatige 17-hoek te construeren is met passer en liniaal, een onwaarschijnlijke krachttoer. In 2000 jaar was er namelijk niets interessants gebeurd wat betreft constructies: de oude Grieken hadden geen problemen met regelmatige driehoeken, vierhoeken, vijfhoeken, en ze konden ook een hoek in twee delen, dus zeshoeken, achthoeken, tienhoeken lukten ook. Vijftienhoeken waren een combinatie van driehoek en vijfhoek, ook daar geen probleem. En dan kwam Gauss, en bleek dat de 7-hoek niet maar de 17-hoek wel te construeren was.

Met passer en liniaal betekent eigenlijk: je kan met de passer cirkelbogen trekken, en met het liniaal rechte lijnen tekenen. Maar meten is niet toegestaan. Ik denk dat Gauss het eerder als een puzzel zag, toen hij het probleem aanpakte. Een theoretische puzzel in zijn geval, want een echte constructie volgde pas later:

Constructie 17-hoek

(Gauss was eigenlijk 19 toen hij dit resultaat aantoonde, maar in een blog met deze titel paste dat niet. Zijn geboortejaar begint overigens wel met 17.) 
Gauss had graag gewild dat een regelmatige zeventienhoek zijn graftombe sierde, maar de steenkapper van dienst vond dat geen goed idee. De zeventienhoek lijkt teveel op een cirkel, en de steenkapper vreesde dat hij daardoor als een amateur zou overkomen op de mensen.

Win een biografie van Gauss!
Omdat het een blogpost is over puzzels, hebben we er ook een puzzel ingestoken. Hier en daar staat een cijfer blijkbaar zonder reden in kleur. Als je al deze cijfers achter elkaar zet, dan vind je geboorte- en sterftejaar van een wiskundige waarover we al geblogd hebben en die invloed heeft gehad op het leven van Gauss. Weet je wie het is, mail dan je antwoord naar dit adres. Tussen de deelnemers worden 2 exemplaren van de biografie van Gauss verloot die we al eerder besproken hebben op deze blog. Je kan meedoen tot en met 15 februari.


Puzzels met 17. Daar gaan we het over hebben.


Recent werd door een Iers wiskundige, Gary McGuire, bewezen dat er minstens 17 vakjes moeten ingevuld zijn bij een sudoku, anders heeft deze zeker geen unieke oplossing. Je leest er meer over op kennislink. Hier is er alvast een voor de liefhebbers:

17 vakjes ingevuld

Voor zijn bewijs heeft McGuire de computer ingeschakeld, en daarom staat het nog niet voor 100% vast dat het geldig is. 



17 is ook het aantal kamelen die een sjeik met 3 zonen in zijn testament had staan. Die moesten zo verdeeld worden: de oudste krijgt de helft van de kamelen, de middelste zoon krijgt een derde, en de jongste moet het stellen met het negende deel. Hoe gaan ze dat regelen?



Wisten jullie dat je op de volgende manier kan nagaan of een getal deelbaar is door 17:
neem het laatste cijfer 5 maal, en trek het resultaat af van je oorspronkelijke getal waar je het laatste cijfer van weggelaten hebt.
Dus bijvoorbeeld:
90 826 302 424  wordt  9 082 630 222
want je trekt van 9 082 630 242 het getal 20 (=4 x 5) af.
Herhaal de procedure:
9 082 630 222  wordt  908 263 012
 908 263 012  wordt  90 826 291
 90 826 291  wordt  9 082 624
9 082 624  wordt  908 242
  908 242  wordt  90 814
 90 814  wordt  9 061
 9 061 wordt  901
  901 wordt  85

Dan stopt het. Indien het getal dat overblijft deelbaar is door 17, dan is het startgetal dat ook.
Kan je dit bewijzen? Graag in een reactie!



Dan is er het raadsel van de brug die over 17 minuten zal instorten. Vier jongens moeten nog aan de overkant zien te geraken. Elk van de jongens doet dat aan een ander tempo. Ze hebben respectievelijk 2, 3, 5 en 6 minuten nodig. Maar de brug kan maar twee personen tegelijkertijd aan. Bovendien is het nacht, en donker, en er is maar een zaklamp. Die moet dus telkens als er twee zijn overgestoken worden teruggebracht. Hoe moeten ze het aanpakken?



17 is ook het aantal essentieel verschillende behangpatronen. Met een behangpatroon bedoelen we een patroon dat zich in (minstens) twee verschillende richtingen voortzet. De kristallograaf E. S. Fedorov bewees in 1891 dat het er precies 17 zijn. Escher was een krak in het maken van mooie behangpatronen. Hier zie je er enkele:

vissen

vlinders

Het is voor mij een raadsel hoe je kan bewijzen dat er precies 17 zijn. Ik heb al wel wat bewijzen van dit resultaat gezien, maar niet echt begrepen, en geen enkel dat intuïtief duidelijk is. Ken je er een? Graag in een reactie.



Dan is er natuurlijk ook nog de Onmogelijke Puzzel, gepubliceerd in 1969 door Hans Freudenthal. Hij gaat als volgt.
Twee getallen x en y zijn beide strikt groter dan 1 en de som is maximaal 100. Steven kent enkel de som van deze twee getallen, en Pascale enkel het product. Zowel Steven als Pascale zijn keien in logisch denken.

Pascale zegt: ik kan er niet achterkomen wat x en y zijn
Steven antwoordt: dat wist ik al
Waarop Pascale zegt: maar nu weet ik het wel
Steven repliceert: dan weet ik het nu ook

Bepaal x en y.
Ook deze puzzel heeft met 17 te maken.



Op het zeventiende probleem van Hilbert moet je overigens niet meer zoeken, want dat is ondertussen al opgelost, meer bepaald al in 1(92)7. David Hilbert formuleerde in 1900 23 belangrijke onopgeloste problemen uit de wiskunde met de uitdaging er klaarheid in te scheppen tegen het jaar 2000. Dat is niet gelukt. Voor het 17de wel.

Hilbert

De oplossing van zijn zeventiende probleem is: elke veelterm (in n veranderlijken) die enkel positieve waarden aanneemt (over de reële getallen) kan geschreven worden als som van eindig veel kwadraten van rationale functies. Dit voor de volledigheid.



We zijn nog lang niet aan 17 puzzels, maar met de volgende boeken bij de hand, kom je er zeker... Toch nog even meegeven dat $\pi$ naar het schijnt de 17de letter is in het oorspronkelijke oud-Griekse alfabet. En bekijk ook zeker dit filmpje eens: je ziet er de puzzelontwerper Oskar van Deventer bezig met zijn 17x17x17 Rubik's Cube, gemaakt met een 3D-printer! (Kostprijs: zo'n 1500 euro)

Ken je nog puzzels met 17? Stuur een reactie!



Breinbrekers Moscovich
Ivan Moscovich, Het grote breinbrekerboek. De 1000 beste puzzels, raadsels en doordenkers. 
Lannoo nv, Tielt (2011) 432 pagina's.

Een prachtig boek, met 1000 puzzels, moeilijkheidsgraad varierend van 1 tot 10. Bekijk hier pagina 3 en pagina 357 (weliswaar uit de oorspronkelijke Engelse versie van het boek). Met een voorwoord van Ian Stewart. Ivan Moscovich woont in Nederland. Hij is een van de bekendste bedenkers van puzzels en raadsels. De puzzels zijn gegroepeerd per onderwerp, een beetje zoals in het bekende 536 puzzles & curious problems van die andere puzzelontwerper Henry Dudeney.

Een ideaal boek om a. jezelf cadeau te doen; b. als coffeetablebook te gebruiken; c. in de auto te hebben liggen voor in de files en op vakantie op het strand. Het enige minpunt is dat het boek erg groot is en veel weegt. Het feit alleen al dat er een pagina besteed wordt aan krommen van constante breedte is voor ons voldoende om het boek erg te kunnen waarderen.


Formuledichtheid:  Ο Ο Ο Ο Ο
Moeilijkheidsgraad: niet van toepassing
Score: Θ Θ Θ Θ Θ



Denkwaar Klouwen
Jaap Klouwen, Denkwaar. Spelen met getallen, woorden en vormen. 75 intrigerende breinbrekers. 
Veen Magazines, Diemen (2010) 192 pagina's.

Henry Dudeney komt ook voor in dit boek met 75 puzzels. Een ander concept dan het vorige, de puzzels zijn iets langer maar je vindt er vast je gading, want het gaat van cijferpuzzels (geef acht manieren om met acht achten het getal 1000 te vormen), via vierkante wielen (!), tot een opgave waar gevraagd wordt de vervangingsweerstand van een kubusschakeling te berekenen. Vaak erg originele puzzels, met telkens een leuk verhaaltje erbij.

Iets moeilijker dan het vorige boek, want hier en daar komt er toch wat wiskunde bij kijken (bijvoorbeeld bij de beste baan voor een vierkant wiel). De auteur Jaap Klouwen maakt al 27 jaar puzzels voor enkele bladen van de Universiteit van Amsterdam. Dit boek is een bundeling van de interessantste. Achteraan in het boek staan ook uitgewerkte oplossingen.  


Formuledichtheid: Θ Θ Ο Ο Ο
Moeilijkheidsgraad: niet van toepassing
Score: Θ Θ Θ Θ Ο




Graetzer Train your brain
George Grätzer, Train Your Brain. A Year's Worth of Puzzles.
A K Peters/CRC Press (2010) 235 pagina's.

Sommigen kennen de auteur misschien wel van het boek Math into LaTeX. In dit boek staat een verzameling denkoefeningen om het jaar goed door te komen, en je hersenen te trainen. Er zijn 52 hoofdstukken, voor elke week van het jaar is er een. Voor de eerste 36 weken zijn er telkens 3 puzzels, voor de laatste 16 zijn er 2 black belt opgaven. Ook dit is een erg leuke collectie die wel degelijk de bedoeling heeft de lezer op regelmatige basis te doen nadenken. Bij sommige opgaven kan je ook een hint krijgen, en ook in dit boek staan de oplossingen achteraan. 
Een voorbeeld: twee koppels willen een rivier oversteken. Er is een bootje voor 2 personen. De mannen zijn eerder jaloers en willen niet dat hun vrouw alleen is met de andere man. Hoe gaan ze te werk? Nog een voorbeeld: zelfde vraag maar met drie koppels.

Een leuk boek, met veel afwisseling in de problemen. In het Engels wel.

Formuledichtheid: Ο Ο Ο Ο Ο
Moeilijkheidsgraad: niet van toepassing
Score: Θ Θ Θ Θ Ο

 


Geschreven in Algemeen | 4 Reacties | Vaste link | Afdrukken


1 2 3 4  Volgende»