05 Augustus 2010, 11:56
Martin Gardner mag gerust een blogger van het eerste uur genoemd worden. Welk onderwerp we in deze blog ook willen toelichten, Gardner heeft er wel iets over geschreven. Vandaag gaat het hier over dissectie-puzzels. Hier zie je een klassiek voorbeeld van Henry Dudeney, uit zijn boek Amusements in Mathematics:
Als je problemen hebt met de oplossing ervan, klik dan even op de figuur.
Van dit soort puzzels zijn er veel te vinden, bijvoorbeeld in Gardner's boeken die zijn columns in de Scientific American bundelen. In Penrose tiles to trapdoor ciphers vind je de volgende opgave. Verdeel deze figuur in twee gelijke delen.

Geschreven in Algemeen  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

28 Mei 2010, 11:57
Martin Gardner, de wiskundige puzzelaar bij uitstek, is deze week op 95-jarige leeftijd overleden.

Vorig jaar verschenen er nog twee nieuwe boeken van hem, wat het totaal op zo'n 70 brengt. Voor wie Gardner niet kent, hij is bekend geworden door zijn column Mathematical Games in de Scientific American. Die column (1956-1981) werd gretig gelezen, en heeft de recreatieve wiskunde tot een wetenschap gemaakt. Gardner haalde zelfs wiskundige aprilgrappen uit met zijn lezers: op 1 april 1975 publiceerde hij een landkaart die niet met vier kleuren te kleuren viel. Dit zou dan in tegenspraak zijn met een vermoeden van Francis Guthrie uit 1852 dat je elke landkaart (die aan bepaalde voorwaarden voldoet) kan inkleuren met vier kleuren op zo'n manier dat aangrenzende landen een verschillende kleur krijgen. Dit resultaat staat nu bekend als de Vierkleurenstelling - op twijfelachtige wijze bewezen in 1976).  Hier zie je de kaart:

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

04 Mei 2010, 13:52

Meestal begint het met artisjokken en eindigt het met wc-papier, maar het kan ook omgekeerd. Dit verhaal begint in een supermarkt van Delhaize waar we gisteren deze rol toiletpapier vonden:

Voortaan kunnen we ons dus schoonvegen met vergelijkingen van Maxwell en formules van andere helden. De psychologische gevolgen voor de mensheid in het algemeen, en voor jonge wetenschappers en fysicastudenten in het bijzonder, zijn voorlopig niet te overzien.

 

Nu, als toiletpapier arrogant uit de hoek komt, voelen we ons uitgedaagd en gaan we in de tegenaanval. Het viel ons namelijk op dat de manier waarop papierrollen doorgaans verpakt worden, meer winkelruimte verspilt dan nodig. Van bovenuit gezien lijkt een pak wc-rollen op identieke cirkels die het vlak opvullen:

Gewoonlijk opteert de fabrikant helaas voor het "vierkantpatroon".
De verpakkingsdichtheid, gedefinieerd als de fractie van het vlak dat door de cirkels ingenomen wordt, kan eenvoudig berekend worden als de oppervlakte van de cirkel gedeeld door de oppervlakte van een omgeschreven vierkant.

In dit geval vinden we dus:

                             pi/4 ≈ 0,785

Meer dan 21% ruimte blijft dus onbenut.

Nochtans kondigde Axel Thue al in 1890 zijn theorema aan: de meest optimale manier om met cirkels het vlak op te vullen gebeurt volgens een "zeshoekpatroon":

Nu zijn de cirkels ingeschreven in regelmatige zeshoeken die het vlak betegelen. De verpakkingsdichtheid is dan de fractie van de oppervlakte die binnen de zeshoek bedekt wordt door een cirkel:

                   pi/√(12) ≈ 0,907

We hoeven dus niet meer dan 10% ruimte verspillen!

Merk op dat de middelpunten van de gestapelde cirkels (wc-rollen) op een regelmatig rooster liggen, zowel bij het vierkantpatroon als bij het zeshoekpatroon. Inderdaad, als we de middelpunten van drie elkaar wederzijds rakende cirkels coördinaten (0,0), (1,0) en (0,1) geven, dan liggen de andere middelpunten op (m,n) met m en n gehele getallen (let op, het assenstelsel is enkel rechthoekig in geval van het vierkantpatroon). Carl Friedrich Gauss bewees al eerder dat het zeshoekpatroon de hoogste dichtheid heeft als we ons beperken tot cirkels op een regelmatig rooster, maar het Theorema van Thue is algemener.

Denk in bovenstaande optimale cirkelconfiguratie de cirkels even weg, zodat enkel de zeshoeken overblijven. We herkennen onmiddellijk de structuur van de honingraat.

Wat is er zo speciaal aan zeshoeken dat ze zo geliefd zijn door bijen (en over het hoofd gezien door toiletpapier-verpakkers)?

Om te beginnen zijn er niet zo veel regelmatige veelhoeken waarmee het vlak kan betegeld worden. Gelijkzijdige driehoeken, vierkanten en regelmatige zeshoeken, en dan hebben we het gehad.

Maar waarom kiezen bijen dan niet voor de driehoek, het vierkant, of misschien een andere niet-veelhoekige vorm?

Dit brengt ons bij het befaamde honingraatvermoeden :

"Van alle mogelijke vlakverdelingen in cellen met gelijke oppervlakte gebruikt de honingraat het minste materiaal (dus, de totale omtrek van de celranden is minimaal als we voor regelmatige zeshoeken kiezen)"

In 1943 gaf Lázló Fejes Tóth hiervoor een bewijs in de veronderstelling dat de cellen convexe veelhoeken zijn, Pappus van Alexandrië wist dit al in het geval de cellen regelmatige veelhoeken zijn, maar in 1999 bewees Thomas C. Hales het vermoeden in volle algemeenheid, vanaf toen de honingraatstelling.

Het voorgaande probleem heeft een boeiende 3D-versie: hoe kunnen we de ruimte in cellen van gelijk volume verdelen zodat de oppervlakte van de celranden geminimaliseerd worden? Dit staat bekend als het probleem van Kelvin. Uit wat ze tot hiertoe geleerd heeft, zou de lezer kunnen concluderen: kijk naar de bijtjes (en vooral niet naar verpakkers van papierrollen).

Inderdaad, eigenlijk bestaat een honingraat uit 3D-cellen:


Meetkundig worden deze honingraatcellen gevormd door een combinatie van een zeshoekig prisma en een "ruitdodecaheder".

 

 

Maar L.F. Tóth ontdekte in 1965 dat de natuur in deze kwestie een  steekje had laten vallen: de honingraatcel is niet de oplossing van Kelvin's probleem. De boog kan niet altijd gespannen staan, moeten de anders zo ijverige bijen ditmaal gedacht hebben. Lord Kelvin zelf suggereerde een oplossing, gebaseerd op een "gesnoeide octaheder", maar in 1994 spatte dit vermoeden als een zeepbel uit elkaar toen D. Phelan en R. Weaire "schuim" ontdekten met gelijk volume maar kleinere oppervlakte dan het Kelvinschuim.

 
Op het einde van de zestiende eeuw, het tijdperk van kapers en zeevaarders, stelde Thomas Harriot formules op voor het aantal kanonskogels in een piramidevormige stapel.

Deze manier van bolstapeling kan in heel de ruimte voortgezet worden. Als we een horizontale laag doorsnijden met een vlak door alle middelpunten, dan vinden we onze optimale vlakke cirkelstapeling terug (zeshoekpatroon). De volgende laag is een halve boldiameter verschoven zodat de kogels in de kuiltjes van de vorige laag passen, maar zodanig dat ze precies boven de kogels liggen van twee lagen eronder. Scheikundigen kennen dit als een "kubisch vlakkengecentreerde atoomstructuur", fruitkramers als de voor de hand liggende manier om sinaasappels in een hoop te leggen. Op deze manier wordt 26% ruimte verloren. Meer bepaald, de dichtheid van deze "kanonkogelstapeling" is gelijk aan

                   pi/√(18) ≈  0,74 

In 1611 beweerde Johannes Kepler dat geen enkele bolstapeling een efficiëntere dichtheid kon hebben dan deze pi/√(18), maar kon het niet bewijzen. Deze bewering staat sinds dan bekend als het vermoeden van Kepler. Er zijn nog enkele andere stapelingen bekend die even opvullend zijn, telkens opgebouwd uit lagen die het zeshoekpatroon volgen. Hieronder zie je een veelgebruikt alternatief (de "hexagonaal compacte stapeling"):

In 1831 bewees Gauss dat pi/√(18) de grootst mogelijke dichtheid is voor een bolstapeling met middelpunten op een regelmatig rooster. Maar dit sloot het bestaan niet uit van onregelmatige compactere stapels. In het vlak zijn de dingen veel eenvoudiger. Rond iedere cirkel kunnen we precies zes identieke cirkels leggen, die de gegeven cirkel allemaal raken. Probeer dit maar uit met euromunten. Wiskundigen zeggen dat het vlak kusgetal zes heeft. Dit verklaart waarom het zeshoekpatroon werkt bij cirkels in het vlak. Het ruimtelijke kusgetal is gelijk aan twaalf; twaalf identieke bollen kunnen een bol met dezelfde straal simultaan raken, en voor een dertiende is er geen plaats (deze observatie gaat terug tot Newton). Maar in tegenstelling tot het vlak is het kussen nu geen starre aangelegenheid: de rakende bollen kunnen nog een beetje bewegen relatief t.o.v. elkaar. Dit leidt tot heel veel mogelijkheden van "lokaal compacte situaties".

In 1998 stuurde Thomas Hales (jawel, de man van het honingraatvermoeden) het bericht de wereld rond dat hij het vermoeden van Kepler bewezen had. Hij had het probleem eerst herleid tot ongeveer 5000 mogelijk kanshebbers, die daarna een voor een uitgesloten werden met behulp van de computer (en zijn student Ferguson). Dit doet onwillekeurig denken aan het bewijs van Appel en Haken voor het vierkleurenprobleem. Het nadeel van dergelijke computerbewijzen is dat ze moeilijk controleerbaar zijn. In 2003 werd het resultaat van T. Hales dan toch gepubliceerd, maar met een kanttekening van de uitgevers waarbij ze de correctheid niet garandeerden. Dit was de aanleiding voor Hales en Ferguson om het Flyspeck project te starten ("Formal Proof for Kepler").

Stapelproblemen kunnen ook statistisch bekeken worden. Als we knikkers willekeurig stapelen dan mogen we een dichtheid van ongeveer 60% verwachten. Na het schudden van de doos knikkers wordt de stapeling lokaal geoptimaliseerd, wat gemiddeld een dichtheid van 65% oplevert. Iedereen heeft dit fenomeen al waargenomen bij een doos met keukenzout. Als je nu geduldig alle zoutkorrels stapelt als kanonkogels dan zou dit een extra winst van 9% geven. 

Stanislaw Ulam vermoedde dat iedere hoop van identieke convexe objecten zodanig kan gestapeld worden dat de dichtheid groter is dan die van een stapel kanonkogels. Bij mijn weten is dit vermoeden nog niet bewezen. Even leek het erop dat regelmatige tetraeders nog slechter te stapelen zijn dan bollen. Sinds John Conway in 2006 de race naar compacte tetraederstapels gestart heeft, zijn al een hele reeks verbeteringen gepubliceerd. Het huidige record geeft een dichtheid van 85,63% (ver boven de 74% van een kanonkogelstapel, conform met het vermoeden van Ulam) en staat sinds dit jaar op naam van Chen, Engel en Glotzer.

In ieder geval hebben de wiskundigen nog genoeg problemen op stapel staan. Wat dacht je bijvoorbeeld van de volgende uitdaging, een e-mail die Thomas Hales van een groenteboer kreeg net nadat hij het probleem van Kepler opgelost had: "We need you down here right away. We can stack the oranges, but we're having trouble with the artichokes."?

 

Verder lezen:  (met aandrang aanbevolen)

"Cannonballs and honeycombs" door Thomas Hales.

G. Szpiro, Kepler's Conjecture: How Some of the Greatest Minds in History Helped Solve One of the Oldest Math Problems in the World, John Wiley & Sons, 2003.

 

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (2)
• Geef uw reactie!
• Print dit artikel

10 April 2010, 10:30

Elke maand is er wel iets wiskundigs. Nu gaat het niet om 1 april, maar om de volledige maand april. Die is in de USA uitgeroepen tot Mathematics Awareness Month of MAM. Oftewel de maand van het zich bewust zijn van de wiskunde. Hiermee wordt waarschijnlijk niet bedoeld wat Thomas Pynchon een van de figuren in zijn roman Against The Day laat zeggen:

Ik citeer de website:

Its goal is to increase public understanding of and appreciation for mathematics.

En daar kunnen we in deze blog wel achter staan. In April 2010 is het thema van de MAM Wiskunde en Sport, wat natuurlijk twee keer precies hetzelfde is.

Ik stel voor dat we dan nu wat wiskunde doen, en wel in de vorm van enkele Sangaku's. Een Sangaku is een plaatje dat een wiskundige stelling voorstelt. Opdracht is je bewust worden om welke stelling het gaat, en ze dan even bewijzen. Sangaku's komen uit Japan. Een beetje wiskunde zal nodig zijn, maar we zullen die beperken tot wat rekenen met  breuken en wortels, de stelling van Pythagoras, en de merkwaardige producten (x + y)² = x² + 2xy + y² en (x - y)² = x² - 2xy + y².

We beginnen met deze:

Wat willen we weten? Je kan je dadelijk de vraag stellen: hoe tekenen we dit? Vertrekkend van twee cirkels en een lijn, hoe kunnen we de twee cirkels op die lijn leggen zodat ze elkaar raken? Stel dat de cirkels straal R₁ en R₂ hebben, dan is het voldoende dat we de afstand tussen de twee streepjes op de gegeven rechte kennen. Noem die x. De stelling van Pythagoras geeft dan het antwoord:

 

 

We zien inderdaad dat x² + (R₁ - R₂)² = (R₁ + R₂)². Haakjes uitwerken, vereenvoudigen en een wortel nemen resulteert in een eerste stelling:

 

We zijn nu klaar voor de tweede:

Let op de vorm: in dit schema hoort bij een breuk met noemer N blijkbaar een cirkel met als straal 1/(2N²).
Dit inzicht laat ons toe verder te gaan. Als we starten met twee cirkels bij de breuken a/b = 0/1 en c/d = 1/1, dan kunnen we (zoals hierboven) nieuwe cirkels blijven toevoegen, en dit levert de volgende figuur op:

We zijn nu al ver doorgedrongen in de wiskunde. De cirkels in de vorige figuur worden Ford cirkels genoemd. En voor de liefhebbers, ze kunnen in verband gebracht worden met de Riemann zeta functie: de totale oppervlakte van de getekende cirkels, in de veronderstelling dat we oneindig lang cirkels blijven toevoegen, is precies gelijk aan 

De laatste figuur toont wel wat gelijkenis met deze mooie Sangaku uit 1788:

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

08 Maart 2010, 17:48

Allicht wist je dat het op zondag 14 maart π-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 π. We hebben hierover vroeger al geschreven, i.v.m. graancirkels en ook hier.

Toevallig is het ook dit jaar precies 400 jaar geleden dat Ludolf Van Ceulen, die vooral bekend (gebleven) is door zijn berekening van het getal π tot op 35 decimalen, stierf. In zijn boek Vanden Circkel heeft hij de berekening van de eerste 20 decimalen beschreven. Je ziet hier een uittreksel uit de tweede editie van 1615: 

Maar wist je ook ...

... dat op 31 december 2009 een nieuw wereldrecord  decimalen-van-π-berekenen is gevestigd door Fabrice Bellard? In totaal werden 2 699 999 990 000 decimalen berekend, op een gewone desktop computer. De berekening is gedaan met wat bekend staat als de Chudnovsky reeks:

... dat de volgende prachtige formule in de notaboekjes van Ramanujan te vinden is?

... dat Andriy Tychonovych Slyusarchuk, een Oekraïense neurochirurg en professor, in juni 2009 beweerde dat hij de nieuwe wereldrecordhouder decimalen-van-π-uit-het-hoofd-kennen was, omdat hij 30 miljoen decimalen gememoriseerd had. Die 30 miljoen decimalen stonden in 20 boeken. Hoewel hij niet al die decimalen heeft opgezegd, is zijn bewering toch geverifieerd door een jury. Deze jury koos willekeurige passages uit de 20 boeken, en Slyusarchuk kon inderdaad de decimalen op de gekozen pagina's reciteren. 

... dat in de Disney-film High School Musical, die zich afspeelt in een school, in een bepaalde scene een reeks voor π van de hand van Ramanujan te zien is op het schoolbord? Een van de leerlingen vraagt aan de lerares: "Moet in die tweede vergelijking niet staan zestien gedeeld door pi?". Waarop de lerares haar rekentoestel bovenhaalt, begint te rekenen, en de fout verbetert.

... dat de studie van het maken en gebruiken van mnemotechnische middelen om de decimalen van π te memoriseren, een speciale naam heeft? We noemen het de pifilologie. (Let op het mooie samengaan van π en het getal van de gulden snede φ in deze naam;-) In de pifilologie zijn pidichten (in het Engels piems) erg belangrijk. Pidichten zijn gedichten die het getal π op de volgende manier voorstellen: het aantal letters in elk woord geeft een decimaal aan van π. Hier is bijvoorbeeld een Engels pidicht:

How I wish I could enumerate pi easily, since all these bullshit
mnemonics prevent recalling any of pi's sequence more simply.

... dat er veel pandigitale benaderingen zijn voor π? Pandigitaal betekent dat elk cijfer van 1 tot 9 er precies 1 keer in voorkomt. Hier is een voorbeeld. Het getal


... dat in de 21ste aflevering ("Marge in de boeien") van het vierde seizoen van de reeks The Simpsons de eigenaar van de Springfieldse Kwik-E-Mart Apu Nahasapeemapetilon in de rechtbank zegt dat hij in staat is 40000 decimalen van het getal π op te zeggen? Apu merkt verder terecht op dat het 40000ste cijfer gelijk is aan 1. Blijkbaar hebben de schrijvers van deze aflevering deze scene voorbereid door aan de NASA te vragen wat de 40000ste decimaal van π is. NASA heeft hen dan een uitprint gestuurd van de eerste 40000 cijfers.

... dat het naaldenexperiment van Buffon niet de enige vreemde methode is om een benadering te vinden voor het getal π? Botsingen tellen in een eenvoudig dynamisch systeem met twee bollen kan ook. Het verschil met Buffon is dat deze methode volledig deterministisch is, en dat je er π mee kan berekenen tot op gelijk welke nauwkeurigheid. Hier zie je de opstelling:



... dat e^{π √ 163} en e^π-π twee bekende voorbeelden zijn van getallen die bijna geheel zijn (almost integer)?

(http://www.xkcd.com)

Hier vind je deze informatie in flyer-vorm, ter lering en vermaak van vrienden en/of collega's.

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (2)
• Geef uw reactie!
• Print dit artikel

19 Januari 2010, 12:04
Wiskunde heeft nu eenmaal een niet al te beste naam bij veel mensen, en dit om allerlei redenen. Wat men zeker niet kan zeggen van wiskunde, is dat het iets saais is.  Bewijs daarvan zijn de talloze verrassende dingen die je als wiskundige tegenkomt. Ik bedoel met verrassend bijvoorbeeld tegenintuïtief, of ook paradoxaal klinkend. Een typevoorbeeld hiervan is de zogenaamde paradox van Banach-Tarski uit 1924. Het gaat hier om een stelling die paradoxaal klinkt, maar toch wel degelijk bewezen is (weliswaar gebruik makend van een axioma, maar dat gebeurt wel vaker in de wiskunde). De stelling zegt bijvoorbeeld dat je een massieve bol in 5 stukken kan verdelen en die aan elkaar kan passen zodat je twee bollen hebt die net zo groot en net zo massief zijn als de oorspronkelijke bol.


Zie ook de boekbespreking enige tijd geleden in deze blog.

Iets anders nu. Bekijk even de volgende figuur.


In de figuur wordt verondersteld dat de gekleurde gebroken lijnen trapvormig van het ene hoekpunt naar het andere lopen. Stel verder dat het omgeschreven vierkant zijde 1 heeft. Het is dan eenvoudig in te zien dat de totale lengte van zo'n gekleurde lijn gelijk is aan de som van twee zijden van het vierkant, dus gelijk is aan 2. Dat geldt zowel voor de rode, als voor de groene en voor de blauwe lijn. Dus de blauwe lijn heeft ook totale lengte 2. Als we zo steeds fijner en fijner werken, dan zal het resultaat steeds meer gaan lijken op de diagonaal van het vierkant. Hoe fijn we ook werken, de lengte van zo'n 'traplijn' zal steeds 2 zijn. Maar... de lengte van de diagonaal van het vierkant is wel gelijk aan √2 . Hoe zit dat dan?
Dit is de bekende Diagonaalparadox (niet te verwarren met de diagonaalparadox van Cantor).

Nummer 3. In de volgende figuur veronderstellen we dat het rode vlakdeel naar rechts verder loopt tot op oneindig.

We kunnen wiskundig bewijzen (met een integraal) dat de totale oppervlakte van het rode vlakdeel oneindig groot is.
We wentelen nu dit vlakdeel om zijn symmetrie-as. Het resultaat ziet er ongeveer zo uit:

Van deze 3d-figuur kunnen we de inhoud berekenen (opnieuw met een integraal). Blijkt dat deze inhoud eindig groot is (meer bepaald pi m³ als we de eenheden in m uitdrukken).
Kan dit wel? De resulterende figuur wordt de Hoorn van Gabriel (of de Trompet van Torricelli) genoemd. Zie ook de paradox van de schilder die verwant is met dit probleem:

Paradox van de schilder (Je kan bewijzen dat de manteloppervlakte van de hoorn van Gabriel oneindig groot is. De inhoud van de hoorn is gelijk aan pi.) Een schilder wil de binnenkant van de hoorn geel schilderen. Omdat de oppervlakte die geschilderd moet worden oneindig groot is, ziet de schilder het niet zitten. De schildersgast komt met een goed idee: omdat de inhoud van de hoorn eindig groot is, kunnen we hem volledig vullen met verf. Dan is de binnenkant ineens mee geschilderd.   Hoe zit dit eigenlijk?

 

Een overzicht geven van alle bekende paradoxen is onbegonnen werk. Daarom volgt hier een bloemlezing.
De beroemdste zijn natuurlijk die van Zeno (490-430) (bijvoorbeeld die van Achilles en de schildpad, maar er zijn er meer).

Achilles en de schildpad Achilles en de schildpad houden een loopwedstrijd. De schildpad krijgt hierbij een voorsprong. Achilles zal de schildpad echter nooit kunnen inhalen want telkens als hij de afstand tot de schildpad heeft overbrugd, is de schildpad weer een eindje verder geraakt.

Ook de paradox van de kapper is algemeen bekend:

Paradox van de kapper De kapper van het dorp scheert alle mannen die zichzelf niet scheren. Vraag is, scheert hij zichzelf?   Als het antwoord op deze vraag ja is, dan scheert hij zichzelf niet: een contradictie. Is het antwoord neen, dan moet hij zichzelf scheren: opnieuw een contradictie.

En je kent waarschijnlijk wel de paradox van de leugenaar (die aan de basis ligt van de onvolledigheidsstelling van Kurt Gödel), hier te zien in een variant:

Paradox van de leugenaar

En dan heb je bijvoorbeeld ook nog de paradox van Berry, de paradox van de onverwachte toets,...
Bij de paradox van de kapper en de leugenaar speelt het begrip zelfreferentie een grote rol. Een beroemd voorbeeld van zelfreferentie vinden we in het schilderij van René Magritte Ceci n'est pas une pipe. Ook in de Prentengalerij van Escher, in de vorm van het Droste-effect.

Een leuk voorbeeld vinden we ook in het boek Finite Dimensional Vector Spaces van Paul Halmos.
Daar staat op p. 198 in de index: Hochschild, G.P. ... 198.

Zelfreferentie leidt vaak tot logische problemen. zoals bijvoorbeeld in de klassenparadox van Bertrand Russell (1872-1970). We kunnen deze als volgt kaderen.

De bibliothecaris in de bibliotheek van Babel vindt dat je niet genoeg kan classificeren. Hij heeft dan ook in de loop der jaren allerlei indexen gemaakt  in boekvorm met de bedoeling een boek gemakkelijk te kunnen terugvinden in de reusachtige bibliotheek. Zo heeft hij een boek waarin alle boeken (en hun plaats in de bib) zijn opgenomen die een rode omslag hebben. Niet toevallig heeft deze index zelf ook een rode kaft.
Hij heeft bijvoorbeeld ook een boek gemaakt dat alle boeken van meer dan 3000 pagina's oplijst. Dit boek is niet al te dik.
Nu vindt de bibliothecaris dat hij ook een index moet maken met daarin alle boeken die zichzelf vermelden zoals het rode boek over de rode boeken. Noem deze index Z.
En dan ook een index met boeken die zichzelf niet vermelden (zoals het >3000 p. boek). Noem deze NZ.
Deze twee boeken bevatten samen alle boeken van de bibliotheek van Babel.

De klassenparadox van Russell In welk van deze beide boeken moet hij het boek NZ vermelden? Is het antwoord op deze vraag NZ, dan staat het boek NZ in NZ en hoort het te staan in Z. Dus moet het staan in boek Z, maar in Z staan enkel de boeken die zichzelf vermelden: een contradictie.

Russell was filosoof en wiskundige. Hij vond deze paradox in 1901, toen hij al bezig was aan zijn magnum opus, de Principia Mathematica. Deze paradox deed de wiskunde, meer bepaald de verzamelingenleer, op haar grondvesten beven.  Meer over deze periode kan je lezen in het erg leuke stripverhaal Logicomix.

---

Apostolos Doxiadis, Christos H. Papadimitriou, Alecos Papadatos, Annie Di Donna, Logicomix. Een epische zoektocht naar de waarheid.  De Vliegende Hollander (2009) 345 pagina's. Dit stripverhaal over de beginselen van de wiskunde en de vragen en problemen waarmee de wiskundigen van het begin van de twintigste eeuw geconfronteerd werden, kent een enorm succes. De figuur van Bertrand Russell staat centraal.  De Engelse versie van dit boek komt voor in verschillende lijstjes bij de 10 beste boeken van 2009. Een aanrader. Apostolos Doxiadis is bij ons bekend van zijn roman Oom Petros en het vermoeden van Goldbach. Formuledichtheid: Ο Ο Ο Ο Ο Moeilijkheidsgraad: Θ Θ Ο Ο Ο Score: Θ Θ Θ Θ Θ

 

---

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (1)
• Geef uw reactie!
• Print dit artikel

21 December 2009, 14:36

Deze combinatie doet me dadelijk denken aan het boek Frøken Smillas fornemmelse for sne (Smilla's gevoel voor sneeuw) uit 1992 van de Deense auteur Peter Høeg waarin de hoofdrolspeelster Smilla op een bepaald ogenblik zegt ”Het valt me makkelijker me voor de wiskunde te interesseren dan van mijn medemensen te houden”. (Nu ik terugdenk aan dit boek, weet ik plots weer waar ik de sfeer uit het boek De eenzaamheid van de priemgetallen van Paolo Giordano van ken.)

In deze uitspraak worden twee zaken met elkaar in verband gebracht waarvan ik liever heb dat ze niet samen genoemd worden. Het staat er wel niet letterlijk, maar het beeld van de mensenschuwe wiskundige is dichtbij. 

Mensenschuw en sneeuwpret liggen dan gelukkig weer mijlenver uit elkaar. Stan Wagon, een wiskundige (en o.a. auteur van het boek The Banach-Tarski Paradox), en een aantal collega's laten de sneeuw in elk geval niet liggen. Elk jaar doen ze mee aan een internationale sneeuwsculptuurwedstrijd in Breckenridge (Colorado). Ze maken dan samen een wiskundige sneeuwsculptuur (en halen er nog prijzen mee binnen ook). Zoals de bovenstaande uit 2003, met de naam Whirled White Web (pdf, 2.7 MB). Zilveren medaille.

In het jaar 2000 maakten ze een Enneper-oppervlak, een oppervlak genoemd naar de Duitse wiskundige Alfred Enneper (1830-1885) (waar waarschijnlijk niemand die dit leest al ooit van gehoord heeft). Hier zie je wat meer ervan: in volgorde Enneper zelf, een stelsel parametervergelijkingen van het bewuste oppervlak en de sneeuwsculptuur van Team Minnesota. Zilveren medaille.

Het gaat om een zogenaamd minimaaloppervlak. Minimaaloppervlakken kom je (behalve als sneeuwsculpturen) in de natuur wel vaker tegen, bijvoorbeeld bij zeepbellen. Ook in de kunst duiken ze op. Het oppervlak van Enneper deed me denken aan het kunstwerk dat ik recent nog gezien heb, naar aanleiding van het bezoek van Erik Demaine aan België. Hij neemt een ringvormig stuk karton en maakt daarin (met veel geduld) cirkelvormige plooien. Als hij dan de zwaartekracht haar werk laat doen na het plooien, dan is bijvoorbeeld dit het resultaat:

Mensenschuw kan je wiskundige Demaine zeker niet noemen, als je kijkt naar zijn indrukwekkende lijst co-auteurs.

Lees het artikel 'De Mozarts van de wskunde' (pdf) over Erik en Martin Demaine (Eos-magazine, februari 2009, door wiskundige Dirk Huylebrouck)

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

30 Oktober 2009, 16:37
Zouden er in Vlaanderen mensen rondlopen die niet weten wat de stelling van Pythagoras is? Misschien wel, maar waarschijnlijk hebben die dan al wel ooit gehóórd van die stelling. Bij de BW's bekleedt Pythagoras ongetwijfeld een ereplaats.
Of de benaming hypotenusa nog lang gebezigd zal worden, dat is een andere vraag. De stelling is in elk geval zo bekend dat ze kan gebruikt worden in cartoons, of moppen. En er is (was?) ook een strip die Pythagoras als held heeft. Ook bekend is natuurlijk het gelijknamige wiskundetijdschrift voor jongeren.
 
Pythagoras van Samos werd rond 580 voor Christus geboren op het gelijknamige eiland.

Geschreven in Algemeen  Vaste link 

Reacties :
• (24)
• Geef uw reactie!
• Print dit artikel

20 September 2009, 15:26

Vorige week donderdag veroorzaakte een klein artikeltje in de krant een glimlach op het gezicht van menig wiskundige. De lottotrekking van 10/09 in Bulgarije gaf als uitslag

4, 15, 23, 24, 35 en 42

Op zich niets speciaals, ware het niet dat bij de trekking hiervoor, op 06/09, juist dezelfde balletjes uit de draaiende trommel vielen (weliswaar niet in dezelfde volgorde).

Grote opschudding bij de Bulgaren, met als gevolg dat experten nu onderzoeken of het toeval niet een beetje gemanipuleerd werd. De organisatie van de Bulgaarse lotto is verontwaardigd over deze verontwaardiging en sluit formeel iedere vorm van fraude uit.

Wat is de kans dat deze week bij de lotto dezelfde cijfers worden getrokken als vorige week? Iedere wiskundige zal hierop antwoorden dat deze kans gelijk is aan 1 op 5245786 (omdat er juist zoveel combinaties zijn van 6 getallen uit 42). Behalve dan de Bulgaarse wiskundige Konstantinov volgens het artikel in De Morgen, maar deze arme kerel werd allicht verkeerd geciteerd door de krant (dan haal je als wiskundige eens de internationale pers). De kans dat zoiets gebeurt is inderdaad microscopisch klein, maar het is even onwaarschijnlijk dat deze week de combinatie die u ingevuld hebt uit de bus komt. Lottoballetjes hebben immers geen geheugen, en door het systeem van de draaiende trommel garandeert de organisatie dat iedere keuze van zes getallen evenveel kans heeft. Ook deze van vorige week.

Surf tijdens uw lunchpauze eens naar de website van Lotto.  Daar kan je statistieken opvragen over de frequentie van de getrokken getallen van 1978 tot nu. Het bijbelse geluksgetal 7 blijkt het meest populair, en is bijna 28% meer uit de trommel gevallen dan het meest zeldzame getal, namelijk 41, toevallig een Sophie-Germainpriemgetal (lees onze bijdrage over dit wiskundemeisje). Duidt dit dan toch op een manipulatie van het toeval? Zouden na vele jaren van lottotrekkingen niet alle frequenties ongeveer gelijk moeten zijn? Belangrijk in deze bewering is natuurlijk wat men bedoelt met "vele jaren" en "ongeveer gelijk". De beroemde wet van de grote getallen (of beter: grote aantallen) stelt wel dat een uniforme verdeling voor de getrokken getallen van 1 tot 42 met de tijd waarschijnlijker wordt, maar ze sluit helemaal niet uit dat af en toe de grilligheden van het lot roet in het uniforme eten gooien. Elke wiskundeleraar die met kanssimulaties experimenteert in de klas, maakt soms tot zijn grote frustratie mee dat het frequentiehistogram na 500 dobbelsteenworpen beter de uniforme verdeling benaderde dan na 1000 worpen.

Nog een toepassing van de wet van de grote getallen:

 

De menselijke intuïtie neigt naar een overdreven patroonherkenning in de willekeur van het toeval. Een kanstheoreticus maakt gemakkelijk het onderscheid tussen een rij van 200 echte muntstuktossen en een door de mens bedachte rij. De Psychology of Randomness is in dit verband een leuk artikel. Nee, er is niets aan de hand met onze lotto, en er is niets speciaal met 7 of 41 (toch niet in deze context).

Dus, lach je collega nooit uit als hij op zijn lottoformulier de winnende combinatie van vorige week invult. Hij getuigt dan enkel van een gezond kanstheoretisch inzicht. Dit kan ook gezegd worden van de 18 Bulgaarse winnaars bij de bewuste trekking van 10/09. Achttien! Dit is pas een statistische uitschieter (in Bulgarije zijn er zeker niet meer deelnemers dan in België of Nederland). De verklaring ligt natuurlijk in de menselijke psychologie, en niet in de kanstheorie. Balletjes hebben dan wel geen geheugen, maar mensen wel. En dus waren 4, 15, 23, 24, 35 en 42 niet zo maar willekeurige getallen. De dag dat 1, 2, 3, 4, 5 en 6 uit de trommel vallen, voorspel ik ook verbazend veel winnaars, omdat deze combinatie voor ons mensen een speciaal patroon vormt (en dus is de kans groter dat meer mensen hiervoor kiezen).

Besluit: Wiskundigen kunnen je niet helpen bij het invullen van je lottoformulier, ze kunnen je alleen vertellen hoe klein je winstkans is (bekijk deze cartoon). Maar dat was ze ook voor de winnaar van deze week.
(RP)

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

28 Augustus 2009, 10:22

Dit vroegen velen zich onlangs af na het lezen van de bestseller “De eenzaamheid van de priemgetallen”, of gewoon nadat ze de titel hoorden. We zijn intussen bekomen van de steek van jaloersheid (waarom bedenken wij niet zulke titels?) en gaan laaghartig in de tegenaanval. Want, beste mensen, eigenlijk hebben de priemgetallen niet zo te klagen over eenzaamheid. Priemtweelingen, priemneven en zelfs de zogenaamde sexy priemgetallen hebben het best gezellig samen. Nee, dan leiden bijvoorbeeld de Mersenne-priemgetallen of de Andersen-getallen een veel schraler bestaan, om nog maar te zwijgen over sociale gevallen zoals de priemvampiergetallen.

Toegegeven, naarmate we oprukken in de rij der getallen worden de priemgetallen steeds zeldzamer. Inderdaad, uit de priemgetallenstelling volgt dat voor een (groot) priemgetal x de afstand tot het volgende priemgetal gemiddeld ln(x) bedraagt (lees onze bijdrage op deze blog over Het Bewijzenboek). Hierbij is ln(x) het natuurlijke logaritme (staat op het meest eenvoudige rekentoestel). Maar dit betekent ook dat voor een priemgetal met bijvoorbeeld 5 cijfers het verschil tot het dichtstbijzijnde priemgetal gemiddeld 13 bedraagt. Dit is geen onoverbrugbare kloof als je het ons vraagt, dus wat die zogenaamde eenzaamheid betreft, zal het wel best meevallen. En dan zwijgen we nog discreet over promiscue voorvallen zoals priemtweelingen (het verschil is slechts 2, bijvoorbeeld 11 en 13), priemneven (het verschil is slechts 4, bijvoorbeeld 43 en 47) of sexy priemgetallen (het verschil is slechts 6, bijvoorbeeld 97 en 103).

Anderzijds kan je wel pech hebben als priemgetal, want de afstand tot het volgende priemgetal kan soms ver boven het gemiddelde liggen. Bijvoorbeeld, na het priemgetal 1425172824437699411 gaapt een gat van lengte 1476 (tot het volgende priemgetal), meer dan 35 keer de verwachte opening ln(1425172824437699411). Dit priemgat is dit jaar gespot door Tomás Oliveira e Silva. De zoektocht naar grote priemgaten heeft al een hele reeks records opgeleverd. Verbaas u hierover op de website van Jens Andersen. We weten wel dat willekeurig grote priemgaten kunnen optreden, maar het blijkt niet eenvoudig om effectief een priemgat te vinden en te verifiëren dat het er een is (alle getallen in het gat moeten ontbindbaar zijn en de eindpunten niet). Toen J. Andersen en T. Alm in 2004 een priemgat van lengte 337446 ontdekten, was dit dankzij de nodige slimme wiskundige software. Dat sommige wiskundigen hun dagen vullen met het opsporen van priemgaten, zoals sommige astronomen zwarte gaten in het heelal zoeken, lijkt op het eerste zicht de wereldvreemdheid van het vak te bevestigen. Op het tweede zicht ook. Al kan het tegenover de belastingbetaler verdedigd worden met het excuus dat dit soort onderzoek bijdraagt tot het inzicht in hoe priemgetallen zich verspreiden tussen de andere getallen, en priemgetallen zijn per slot van rekening de bouwstenen van de getaltheorie. Hetzelfde argument legt uit waarom het zo belangrijk is dat eindelijk eens iemand het Vermoeden van Riemann bewijst.

Maar we wijken af, want we hadden het eigenlijk over eenzame priemgetallen. De omkeerbare priemgetallen zijn redelijk dun gezaaid. Zo is 13 bijvoorbeeld een omkeerbaar priemgetal, want 31 is ook een priemgetal. Met hoeveel ze zijn, eventueel oneindig veel, kan voorlopig niemand zeggen. Als een priemgetal een palindroom is, dan is het natuurlijk vanzelf omkeerbaar, bijvoorbeeld 10301. Het grootste palindroompriemgetal dat we vandaag kennen, is 10¹⁸⁰⁰⁰⁴ + 248797842 × 10⁸⁹⁹⁹⁸ + 1 (H. Dubner, 2007). Het grootste omkeerbaar priemgetal dat geen palindroom is (in het Engels een “emirp”) staat op naam van Jens Andersen (2007): 10¹⁰⁰⁰⁶+941992101×10⁴⁹⁹⁹+1. Een leuk weetje, handig als het gesprek aan tafel stilvalt, is dat 37 het 12^de priemgetal is, terwijl zijn omgekeerde (73) het 21^ste priemgetal is, en merk op dat 21 het omgekeerde van 12 is!

Duidelijker(?): als de functie P(n) het n-de priemgetal geeft, dan is n=12 een oplossing voor de vergelijking:

                                   P(omgekeerde(n)) = omgekeerde(P(n))

Sinds het artikel van J.L. Pe wordt n=12 een “palin point” voor de functie P genoemd (bij het googlen wel de optie –sarah meegeven). Probeer zelf ook eens een palinpunt voor P(n) te vinden (dit is een geschikt moment om het gezelschap te verlaten en de schotel in de oven te zetten). De enige voorbeelden die een normaal mens kan vinden zijn de voor de hand liggende eerste vijf priemgetallen. Het is opnieuw J. Andersen die als eerste een palinpunt voor P(n) ontdekte groter dan 12: n = 8114118 en P(n)=143787341 (door een gelukkig toeval zijn zowel n als P(n) palindromen). Een meer haalbare puzzel is het zoeken naar palinpunten voor de kwadraatfunctie f(n) = n² (bijvoorbeeld n=13, want 13²=169 en 31²=961).

Als de vorige anekdote uw gasten niet boeit en als hun kaken dreigen te verrekken tijdens het geeuwen,  is het misschien tijd om het probleem van 196 op tafel te gooien. Dit verhaal gaat over algemene palindroomgetallen, niet noodzakelijk priem. Bijvoorbeeld 303, toevallig het aantal palindromen in de Dikke Van Dale (dit laatste kan je met uitgestreken gezicht beweren, want wie gaat zoiets controleren?). Als een getal geen palindroom is, bijvoorbeeld 42, dan tel je hierbij het omgekeerde op, 42+24, en het is goed mogelijk dat je dan wel een palindroom krijgt, zoals hier 66. Maar soms heb je pech, maar dan herhaal je de procedure:

95 + 59 = 154

154 + 451 = 605

605 + 506 = 1111

En uiteindelijk kom je terecht bij een palindroomgetal! Test dit maar zelf uit met enkele willekeurige getallen. Maar tot hiertoe heeft nog niemand kunnen bewijzen dat dit werkelijk bij ieder getal lukt (als je de procedure maar lang genoeg volhoudt). Het is zelfs zo dat sommige getallen zich hardnekkig verzetten om een palindroom te worden. Het kleinste probleemgeval is 196. Wat is er mis met 196? Hele generaties computers hebben steeds het omgekeerde opgeteld bij de uitkomst, startend met 196, maar tot nu toe werd geen palindroom bekomen. Algemeen wordt vermoed dat dit nooit zal gebeuren, maar een wiskundige bewijs is nog niet gevonden.

U merkt hoe moeilijk het is om ons te beheersen en bij de les te blijven. We hadden het dus over eenzame priemgetallen. Een Mersenne-priemgetal M is een priemgetal van de vorm 2ⁿ – 1 (bijvoorbeeld 7 = 2³-1). Het is noodzakelijk dat de macht n zelf priem is, want anders is M zeker ontbindbaar. Helaas is dit niet voldoende: 2¹¹−1 = 2047 = 23×89 is geen priemgetal. Mersenne-priemgetallen zijn zeer zeldzaam en moeilijk te vinden. Tot heden zijn er nog maar 47 gevonden; de laatste hiervan in april van dit jaar door de Noor O. Strindmo. Ook het grootste tot nu gevonden priemgetal is een Mersennegetal: 2^43112609-1 (wat geen toeval is, omdat voor Mersennegetallen een efficiëntere priemtest bestaat dan voor willekeurige getallen). Men vermoedt dat er oneindig veel Mersenne-priemgetallen bestaan, maar zeker is dit (nog) niet. In dit geval zouden er ook oneindig veel perfecte getallen bestaan, want ieder even perfect getal is van de vorm 2^(n-1).(2ⁿ - 1) met 2ⁿ - 1 priem. Een perfect getal is de som van zijn delers (zichzelf niet meegerekend). Bijvoorbeeld 28 = 2²· (2³ – 1) =1+2+4+7+14. Tot de dag van vandaag heeft men nog geen oneven perfect getal gevonden. Perfecte getallen werden reeds in de oudheid bestudeerd en kregen dikwijls een mystieke of religieuze betekenis.

Joseph L. Pe, de man die de term “palinpoints” uitvond, introduceerde het begrip spiegelperfecte getallen (puur voor het puzzelplezier, wat ons inziens een gezonde motivatie is). Neem bijvoorbeeld 10311. Dit getal is niet perfect, want het is niet gelijk aan de som van zijn (echte) delers:

1 + 3 + 7 + 21 + 491 + 1473 + 3437.

Maar als men het spiegelbeeld van deze som beschouwt,

7343 + 3741 + 194 + 12 + 7 + 3 + 1,

dan is de uitkomst gelijk aan 11301, het spiegelbeeld van 10311. We noemen 10311 hierom een spiegelperfect getal. Ook voor deze getallen heeft men nog weinig zicht op hun verspreiding (de “eenzaamheid”)  tussen de andere getallen, en weet men niet of ze oneindig in aantal zijn. Jens Andersen, hij weeral, de man van de grote getallen, heeft een stelling gevonden waarmee gigantisch grote spiegelperfecte getallen kunnen geconstrueerd worden. Eerst zoekt hij een priemgetal van de vorm p=140z10n89, waarbij z een rijtje nullen is (eventueel lengte 0) en n een rijtje negens (eventueel lengte 0). Daarna vermenigvuldigt hij dit priemgetal met 57, en hij heeft bewezen dat de uitkomst (een “Andersen-getal”) altijd spiegelperfect is. Bijvoorbeeld

p = 140000109999989

is toevallig priem. Het bijbehorende Andersen-getal

57 x p = 7980006269999373

is dus spiegelperfect. Misschien moeten we maar eens een boek schrijven met als titel “Het onuitputtelijke puzzelplezier van de priemgetallen”.

(RP)

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

14 Juni 2009, 18:31

De maand juni is voor vele Belgen een zoektocht naar bankattesten, loonafschriften, bewijzen van kinderopvang, en alle andere documenten die nodig zijn om onze belastingsaangifte zo nauwkeurig mogelijk in te vullen. Onze overheid gaat er (terecht) van uit dat niet iedereen al zijn inkomsten aangeeft en dat aldus de staat rechtmatige inkomsten aan haar neus laat voorbijgaan. Daarom worden op willekeurige basis belastingcontroles uitgevoerd. Maar controles kosten dan weer geld, dus is het de kwestie om een evenwicht te vinden: hoe groot moet de fractie van de gecontroleerde aangiftes zijn (en de bijbehorende boetes) om juist de gemiste belastinginkomsten te compenseren? Anderzijds zal deze fractie de pakkans bepalen en dus ook de strategie van de fraudeurs aangaande het bedrag dat “vergeten” wordt aan te geven.

Speltheorie

Binnen de wiskundige economie bestaat een gebied met de vrolijke naam “speltheorie” dat zich bezighoudt met problemen zoals hiervoor beschreven. Deze theorie werd tijdens de Tweede Wereldoorlog ontwikkeld door Oscar Morgenstern (1902–1977) en John von Neumann (1903-1957).

Zij schreven er een boek over, getiteld Theory of Games and Economic Behaviour (1944). Voor bepaalde marktsituaties (of algemener, spelsituaties) worden modellen bestudeerd waarin één of meerdere spelers uit verschillende strategieën kiezen om een persoonlijk of gemeenschappelijk nut te verhogen. Vanuit wiskundig standpunt wordt vooral kanstheorie gebruikt. Varianten van “speltheorie” (of “vertakkingen”, afhankelijk van de geraadpleegde bron) zijn “beslissingstheorie” en “mechanisme-ontwerp”. Bovendien kan de studie van sociale samenlevingsmodellen als bastaard beschouwd worden, geboren uit overspel met de psychologie. In de speltheorie gaan we er namelijk vanuit dat de spelers enkel op rationele gronden beslissen, maar in de praktijk worden we gedreven door meer complexe psychologische motieven.

De shotgun-clausule van de Deense koning

De Sont is de zeestraat tussen Denemarken en Zweden. Tussen 1429 en 1857 werd op buitenlandse schepen die hier passeerden, tol geheven door het Deense koningshuis. Sinds 1567 werd deze Sonttol a ratio van de ladingswaarde berekend. Wat deze waarde betrof, moesten de Denen de schippers op hun woord geloven, want het was praktisch onmogelijk om de hele lading te controleren en te schatten. De Deense koning Frederik II (1534-1588) bedacht hiervoor een eenvoudige maar slimme oplossing. Hij kwam vooraf overeen met de schipper dat de opgegeven waarde voor de lading tegelijkertijd als koopprijs mocht beschouwd worden. Dus, de koning had te allen tijde het recht om de hele lading van de schipper over te nemen tegen het opgegeven bedrag. In sommige economische middens wordt dit de shotgun-clausule genoemd. Fraude wordt inderdaad ontmoedigd als je niet op voorhand weet of het opgegeven bedrag gebruikt wordt om de tol te berekenen, dan wel om je bezittingen op te kopen.

<Stel dat we r noteren voor de Deense tolvoet. Dus, als de schipper zijn lading aangeeft voor een bedrag A, dan is de gevorderde tol gelijk aan rA. Voor de Sonttol was r een waarde tussen 0,01 en 0,02. Stel verder dat de schipper beslist om zijn lading van waarde W te onderwaarderen en aan te geven voor A=W/(1+r). Dan bevindt de koning zich in een “evenwichtige situatie”. Hiermee bedoelen we dat onafhankelijk van zijn beslissing (aangifte aanvaarden of niet) de koning altijd een opbrengst verwerft van

rW/(1+r)

Inderdaad, als hij simpelweg tol heft dan levert hem dit rA=rW/(1+r) op. Maar als hij tot de koop overgaat, dan is zijn winst W-A, wat ook gelijk is aan rW/(1+r).

Als controlestrategie kan de koning beslissen om bij een fractie p=r/(1+r) van alle passerende schepen de lading op te kopen (met r nog steeds de tolvoet). Dit brengt dan weer de schipper in een evenwichtige situatie. Met welke aangifte A < W hij ook voor de dag komt, zijn verwachte kost is altijd dezelfde:

E(kost) = (1-p)rA + p(W-A) = rW/(1+r)

Lees meer over de Sonttol en verwante situaties op Kennislink.

A beautiful mind

Een dergelijke keuze van beslissingen door de spelers waarbij niemand zijn situatie kan verbeteren gegeven de strategie van de ander(en), noemen we een Nash-evenwicht.

John Forbes Nash (1928), wiskundige en econoom, is bij het grote publiek vooral bekend als hoofdpersonage in de film “A beautiful mind”, een film met Russell Crowe uit 2001, vorig weekend nog te zien op televisie. Zijn “evenwichtstheorie” is ontegensprekelijk een belangrijke bijdrage in de speltheorie. In zijn doctoraatsthesis (1950) bewees hij dat onder bepaalde omstandigheden er steeds een Nash-evenwicht bestaat (“voor elk niet-coöperatief spel met gemengde strategieën”). Zoals gekend, kreeg hij voor dit werk de Nobelprijs voor economie (1994). In 2004 kreeg hij een eredoctoraat aan de Universiteit Antwerpen. Lees zeker ook het Interview met John Nash in Eos juni 2007.

Het ultimatumspel  

Een klassiek paradigma beschrijft hoe een vader zijn twee kinderen samen honderd euro geeft, aangenomen dat ze onderling een verdeling overeenkomen. Hierbij mag de oudste juist één voorstel doen aan de jongste. Als deze laatste het hiermee niet eens is, neemt vader het geld terug en krijgen ze allebei niets. Dit wordt soms het “ultimatumspel” genoemd. Vanuit rationeel standpunt zou de jongste ieder voorstel moeten aanvaarden. Dit is de optimale strategie voor zijn persoonlijk nut, maar ook voor de gemeenschap (beide kinderen). Deze situatie is al herhaaldelijk gespeeld met proefpersonen, en het blijkt dat een voorstel van beneden de 20% zelden aanvaard wordt. Ook al blijven de spelers dan met lege handen achter. Misschien wil het “jongste kind” de “oudste” terechtwijzen voor zijn vernederend voorstel in de hoop om de volgende keer een betere verdeling af te dwingen. Maar komt er wel een volgende keer? Is onze psychologie getraind door en dus ook voor herhaalde experimenten? Kunnen wij enkel logisch redeneren op lange termijn, en hebben wij het lastig met de rationaliteit van de eenmalige gebeurtenis? De speltheorie leert ons alvast dat andere strategieën zich opdringen als we een spel meermaals spelen. In de marge doe ik jullie glimlachen met het verslag van een onderzoek van de universiteit van Cambridge. Bij experimenten van het ultimatumspel schijnt dat proefpersonen die onder invloed zijn van chocolade en kippensoep vlugger geneigd zijn om een laag voorstel te aanvaarden. De aanmaak van serotonine zou hiervoor verantwoordelijk zijn.

Het prisoner's dilemma  

Het meest geciteerde voorbeeld uit de speltheorie is ongetwijfeld het “prisoner’s dilemma”. Voor een goede beschrijving verwijzen we naar de website van de Universiteit van Twente. Hieronder zie je het schema voor de dieven Albert en Bob die na een gewapende overval met wapens betrapt worden, maar met geen bewijs voor hun betrokkenheid bij de overval zelf. Als ze dus allebei ontkennen, kan men hen enkel verboden wapenbezit aansmeren, wat 1 jaar gevangenis betekent. Toch geeft ontkennen geen Nash-evenwicht, want als de andere bekent (en jou er inluist) dan heb je 15 jaar aan je been (en gaat de onderkruiper vrijuit). Een Nash-evenwicht ontstaat wel als Bob en Albert allebei bekennen. Zoals bij het ultimatumspel verandert de situatie (en de strategie) wel degelijk als het spel herhaald wordt en als jouw huidige beslissing kan afhangen van de vorige beslissing van de tegenspeler. In het vuur van de koude oorlog bepaalde speltheorie mee de strategie tijdens de wapenwedloop.

Het laatste koekje in de schaal

De modellen in speltheorie hoeven niet noodzakelijk altijd enkel persoonlijk voordeel na te streven. Door het voordeel van anderen in de individuele nutsfunctie in te voegen (meestal met een gewichtsfactor), kunnen ook eigenschappen zoals burgerzin of altruïsme gemodelleerd worden.

Stel even dat onze dieven van het prisoner's dilemma samen uitgenodigd zijn op een communiefeest. Bob en Albert kunnen allebei het laatste koekje in de schaal begeren, maar wie het meeste lef heeft, kan genieten (met een beetje schuldgevoel). Degene die met lege handen achterblijft, moet bovendien toezien hoe de andere smult. Als niemand durft toe te tasten, dan verkommert het koekje in de schaal en blijven ze allebei verstoken van genot, maar ook van het leed om de andere te zien eten. Maar in tegenstelling tot het prisoner’s dilemma is nu galantheid ook een strategie. Bob kan het laatste koekje aanbieden aan Albert. Ook al blijft Bob op zijn honger zitten, hij voelt zich minder een verliezer en zelfs een beetje beloond door zijn altruïsme. Ook Albert zal nu met minder schuldgevoel kunnen genieten dan wanneer hij het koekje zelf botweg genomen had. Het boeiende is dat we niet allemaal goede mensen moeten zijn om deze wereld aangenamer te maken. Want als Bob en Albert allebei het koekje aan de andere aanbieden en blijven volhouden in hun beleefdheid, dan blijft het koekje eveneens in de schaal liggen en scoort niemand met zijn galantheid.

Een Nash-evenwicht wordt in sommige spelen dus enkel bereikt in een gemengde strategie waarbij een van de spelers lief is en de andere egoïstisch.

Welke les we hieruit moeten trekken voor het invullen straks van onze belastingbrief is me een brug te ver voor deze blog.

(RP)

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (2)
• Geef uw reactie!
• Print dit artikel

18 Mei 2009, 20:09

In zijn cultreeks The Hitchhiker's Guide to the Galaxy (een "trilogie" in vijf delen) beschrijft auteur Adam Douglas hoe een pan-dimensionaal hoogbegaafd ras een supercomputer ontwerpt met de naam Deep Thought. Als je deze naam in je zoekmachine intikt (en de vraag van Google negeert of je misschien "deep throat" bedoelt) dan vind je dat IBM de naam "Deep Thought" van Douglas ontleend heeft voor hun fameuze schaakcomputer in de jaren 80 (voorloper van "Deep Blue"). 

De bedoeling van de ontwerpers van "Deep Thought" was om het ultieme antwoord te krijgen "op het leven, op het universum, op alles". Na zeven en een half miljoen jaren van rekenen kwam deze supercomputer met het antwoord 42 . Toen beseften de leiders van dit intelligent ras dat de vraag eigenlijk niet gekend is. Om de bevolking te sussen stelden ze "How many roads must a man walk down?" als mogelijkheid voor, maar dit lukte niet echt. Helaas bleek "Deep Thought" zelf niet bij machte om de ultieme vraag te achterhalen die het ultieme antwoord 42 geeft. Daarom ontwierp "Deep Thought" een nieuwe machine, de "Aarde", met als doelstelling om uiteindelijk de ultieme vraag te kennen. Helaas wordt de Aarde vijf minuten voor het voltooien van de berekening vernield door de "Vogons". Maar lees vooral zelf het boek.

Sinds 18 mei 2009 is de nieuwe internethype Wolfram Alpha officieel opengesteld voor het grote publiek. De makers beschrijven haar als een "Computational Knowledge Engine" met als ambitie om alle menselijke kennis gestructureerd te groeperen. Ze is echter geen zoekmachine zoals Google, maar een superbrein dat meteen het antwoord op je vraag geeft (en dus geen lijst met internetpagina's). Voorlopig kan je alleen Engels met haar praten. Type bijvoorbeeld "Newton" in en ze vraagt of je de eenheid, de persoon of de stad bedoelt. Als gebruiker kan je dan verder specifiëren.
Probeer zeker ook eens je geboortedatum of een moeilijke integraal (bijvoorbeeld integral((sin x)/x) ).

We waren wel een beetje teleurgesteld dat Wolfram Alpha geen weet heeft van het bestaan van Paul Levrie en Rudi Penne (dat ze de laatste met een pastagerecht verwart is enkel zout in de wonde). Ook haar kennis over "Eos" lijkt ons nog te beperkt. Maar we troosten ons met het feit dat ze evenmin Eddy Merckx en dEUS kent. Pater Damiaan en Marc Dutroux staan daarentegen al wel in de gegevensbank. We konden ook niet aan de verleiding weerstaan om te vragen: "How many roads must a man walk down?" Het antwoord verraste, en eigenlijk toch weer niet. 

De Brit Stephen Wolfram is de geestelijke vader van dit superbrein. Hij is onder wiskundigen vooral bekend als schrijver van de software Mathematica, een programma voor wiskundige berekeningen en figuren, dat in staat is tot symbolisch redeneren (vergelijkbaar met "Maple"). Behalve informaticus/wiskundige is hij ook een natuurkundige, en schreef als vijftienjarig wonderkind al een artikel over deeltjesfysica. Zijn bedrijf, dat naast het programma Mathematica en de website MathWorld nu ook Wolfram Alpha heeft gelanceerd, heet Wolfram Research .  Bovendien is hij de auteur van het spraakmakende boek "A new kind of science" .
(RP)

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

16 Mei 2009, 10:50

 

Het mechanisme om een beroemde blogger te worden is eindelijk blootgelegd:

(met dank aan cartoonist Dave Walker)

Geschreven in Algemeen  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

06 Mei 2009, 18:19
Nu de zon weer vaker schijnt kan je overal in de natuur prachtige kaustieken zien. Zoals deze:

of deze, bij een kop koffie:


Je ziet hem niet zo goed, maar als je klikt op de figuur, dan wel. Een verbeterde versie krijg je met behulp van een garnierring:


Het gaat hier om de door de zon getekende kromme die ontstaat door de weerspiegeling van het licht in de cilindervormige garnierring. Hij staat bekend als de Coffeecup Caustic. Deze kromme wordt een katakaustiek genoemd, en is al zeer lang geleden door wiskundigen bestudeerd. Lang heb ik gedacht dat Christiaan Huygens (1629-1695) de eerste was, in zijn Traité de la lumière (1678).
De naam kaustiek is gegeven door Ehrenfried Walter von Tschirnhaus (1651-1708), en is afgeleid van het Griekse woord voor 'branden'. In het Nederlands kunnen we spreken over een brandkromme, naar analogie met het brandpunt van bijvoorbeeld een parabool (waarbij lichtstralen die evenwijdig met de as invallen, weerkaatst worden door dit ene punt, tenminste als de parabool spiegelend is).
Von Tschirnhaus is vooral bekend voor de uitvinding van het porselein, maar hij fabriceerde ook grote 'brandspiegels' met de bedoeling hiermee zeer hoge temperaturen te kunnen voortbrengen. Vandaar zijn interesse voor dit onderwerp.
Dat ook Archimedes oog had voor brandkrommen blijkt uit het verhaal over het beleg van Syracuse in de tweede Punische oorlog, waarin beweerd wordt dat Archimedes de Romeinse vloot in brand stak met behulp van grote bronzen spiegels.

Groot was mijn verbazing toen ik enkele dagen geleden op de volgende figuur stootte:

en wel in een van de notaboekjes van Leonardo Da Vinci (1452-1519), met name de Codex Arundel, uit het begin van de zestiende eeuw. Een moderne versie van deze tekening ziet er zo uit:

Maar om welke kromme gaat het hier? Op de tekening zie je dat de gezochte kromme rakend is aan de weerkaatste stralen. In de wiskunde spreekt men over de omhullende van de weerkaatste stralen. Methodes om de vergelijking van een omhullende te vinden, bestaan al lang. In dit geval blijkt het te gaan om de helft van een nierkromme, of nefroïde, een kromme die thuishoort bij de epicycloïden. Dit zijn krommen die ontstaan indien we een cirkel omheen een vaste cirkel rollen zonder glijden, en we de beweging van een punt op de rand van de rollende cirkel volgen:

Door de eeuwen heen zijn kaustieken bestudeerd door niet de minste wiskundigen, door enkele Bernoulli's bijvoorbeeld, maar ook door Adolphe Quételet (1796-1874), wiskundige van eigen bodem en bekend uit de statistiek en als 'uitvinder' van de body mass index.
Als je er even mee bezig bent, dan kom je al snel terecht in een wereld vol krommen met exotische namen zoals evoluten, evolventen, voetpuntskrommen, orthotomics. Met leuke prentjes ook. De kaustiek van een cycloïde bijvoorbeeld is opnieuw een cycloïde die half zo groot is als het origineel:

En de kaustiek van de bekende exponentiële functie is dan weer een andere beroemde kromme, namelijk de kettinglijn:

Geïnteresseerde lezers kan ik het boek van Johann Bernoulli (1667-1748) aanraden (hier in een Duitse vertaling), de hoofdstukken over kaustieken beginnen op pagina 110, of het eerste echte Calculusboek, van de hand van Guillaume de l'Hospital (1661-1704) (vanaf pagina 148 gaat het over kaustieken). Ook nu nog worden kaustieken bestudeerd, bijvoorbeeld in de branche van de Computer Graphics (waarin collega-blogger Philip Dutré actief is).
Hier zie je een beeld dat volledig door de computer is gegenereerd:

En ook dit past volledig in het kader:

Bronnen/verder lezen

• Een deel van dit materiaal vind je terug in:
  P. L. en H. Missinne, Over grafieken, kaustieken en epicycloïden, Wiskunde en Onderwijs 32 (125), pp. 21-30, 2006.
• Ook hier kan je eens een kijkje nemen: Ch. Ucke en Ch. Engelhardt, Playing with caustic phenomena, en Kaustik in der Kaffeetasse. Op de webpagina van Christian Ucke zijn overigens nog een heleboel andere leuke dingen te lezen.

(PL)

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel

03 April 2009, 11:24

De eerste sudokuhype lijkt een beetje over. Maar vergis u niet, nog steeds is geen trein of wachtzaal veilig voor de eenentachtig vakjes. Bovendien hebben deze puzzels nog lang niet al hun wiskundige geheimen prijsgegeven. En af en toe duiken ze op in het nieuws. Vorige week bijvoorbeeld meldden enkele internetredacties dat een wiskundige, James Crook (what’s in a name?), een formule had uitgevonden om sudoku’s op te lossen. Lees bijvoorbeeld dit. Het bericht werd zelfs overgenomen door de krant De Morgen. Als gevolg lieten her en der liefhebbers hun bezorgdheid horen over het eventueel vergallen van hun puzzelplezier.

 

Zelf ben ik niet zo een puzzelaar, maar sudoku’s stammen nu eenmaal af van Latijnse vierkanten en leveren vaak leuke wiskunde op.  

Dus haastte ik me naar de website van de American Mathematical Society om het bewuste artikel A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles te lezen. De “formule” waarover de nieuwsberichten het hadden, is een algoritme, een strategie in stappen dus. Zowel de publicatie als de media-aandacht van dit artikel lijken me een sterk staaltje marketing. Want James Crook zet gewoon enkele dingen op een rijtje die iedere weekendsudokuliefhebber al lang uit zichzelf doet. De sleutelrol in zijn methode zijn zogenaamde “preemptive sets”. Dit zijn k vakjes in eenzelfde vierkant, kolom of rij, waarin de enige mogelijke nog in te vullen cijfers samen ook juist k in aantal zijn.

 

Hiernaast zien we bijvoorbeeld een deelvierkant met twee ingevulde cijfers en met de openstaande mogelijkheden opgetekend in de andere vakjes. We zien hier een "preemptive set" gevormd door de vier vakjes (7,1), (7,2), (8,3), (9,3), omdat deze samen nog maar vier cijfers toelaten: 3, 4, 5, 9.

Gezond verstand leert ons dat deze 4 cijfers noodzakelijkerwijs over deze 4 vakjes verdeeld worden. Dus mogen we deze cijfers schrappen in de andere vakjes van dit deelvierkant: 

 

 

Nee, als u echt wiskundig relevante dingen over sudoku’s wil lezen, dan kiest u beter uit onderstaand lijstje:
 

• Het boek van Peter Higgins, uitvinder van de cirkel-sudoku, besproken in onze boekenrubriek.
• Biological imaging by soft x-ray diffraction microscopy door Veit Elser en anderen. Verrassende invalshoek: om een deeltje kleiner dan de golflengte van het licht waar te nemen, kan je proberen verstrooide x-stralen opnieuw samen te stellen met behulp van Fouriersynthese. De ongekende faseverschuivingen worden ingevuld door het “difference-map”-algoritme van Elser. Nu blijkt per toeval dit algoritme ook geldig voor het oplossen van sudoku’s.
• Anything but square: from magic squares to Sudoku  door Hardeep Aiden. Dit artikel gaat vooral over tovervierkanten. Maar het behandelt ook de historiek van sudoku’s via o.a. Latijnse vierkanten en Euler’s probleem van de 36 officieren.
• Sudoku Squares and Chromatic Polynomials door Agnes M. Herzberg en M. Ram Murty (zie ook Sudoku en grafentheorie op kennislink). Met behulp van grafentheorie bekijken Herzberg en Murty enkele combinatorische vragen over sudoku’s. Hoeveel oplossingen zijn er bij een gegeven beginsituatie (een goede opgave mag maar 1 oplossing hebben). Hoeveel ingevulde sudoku’s zijn er eigenlijk, eventueel ook van andere afmetingen?
• Sudoku, gerechte designs, resolutions affine space, spreads, reguli and Hamming codes door R. A. Bailey, Peter J. Cameron and Robert Connelly. Leuk leesvoer is dit. Een “gerechte” is in 1956 bedacht door W.U. Behrens en is een veralgemening van een sudoku waarbij de deelvierkanten willekeurige gebieden mogen zijn. De auteurs behandelen ook toepassingen in de statistiek en het opstellen van lessenroosters. Maar hun grootste prestatie is het ontwerpen van mooie sudoku’s met bepaalde symmetrieën via Hamming codes en kwadratische regeloppervlakken over eindige lichamen. Geniet bijvoorbeeld van de "quasi-magische sudoko" hieronder, waarin elk van de negen deelvierkanten quasi-magisch is (rijsommen en kolomsommen zijn steeds dezelfde en gelijk aan 15).

Nu is het wachten op het volgende nieuwsfeit over sudoku’s.  Misschien bewijst iemand binnenkort dat een goede sudoku nooit minder dan 17 startwaarden kan hebben.

Geschreven in Actuele wiskunde  Vaste link 

Reacties :
• (0)
• Geef uw reactie!
• Print dit artikel