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.

Om 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:

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 2^p-1(2^p-1):


Helaas liep het mis bij p = 11. Inderdaad, 2¹⁰(2¹¹-1) is niet volmaakt. De reden van het falen is dat 2¹¹−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:

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 = 2^p-1(2^p-1). Mersenne had ook nog M₆₇, M₁₂₇ en M₂₅₇ in zijn lijst opgenomen, maar hiervan ontdekte men achteraf dat M₆₇ en M₂₅₇ samengestelde getallen zijn. Onze monnik had dus geen foutloos werk afgeleverd, en had bovendien M₆₁, M₈₉ en M₁₀₇ 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.

Juist 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: 2^57.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 M_p = 2^p-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 × 10¹² 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.

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:

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


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:

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

Geschreven in Algemeen | 0 Reacties | Vaste link | Afdrukken

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:

(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:

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:
want je trekt van 9 082 630 242 het getal 20 (=4 x 5) af.
Herhaal de procedure:

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:


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.

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.

---

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!

---

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: Θ Θ Θ Θ Θ

---

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: Θ Θ Θ Θ Ο

---

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

16. Oktober 2010, 18:48

Zouden we in plaats van de lege momenten op te vullen met het invullen van de cijfers van 1 tot 9 in een vierkant van 9 op 9 opgebouwd uit 9 kleinere vierkanten van 3 op 3 de zaak niet wat moeilijker kunnen maken door ons toe te leggen op het zoeken naar wat bekend staat als de voorloper van de Sudoku, namelijk de magische vierkanten? Ook hierop zijn interessante puzzels gebaseerd, die iets meer wiskunde vergen. Hier zie je er eentje:

Het probleem hier is het volgende. Vul in de lege vakken getallen in, en wel zodanig dat de som van alle getallen in een rij of kolom steeds gelijk is aan 90. Bovendien moet ook de som van de getallen op elk van de diagonalen (van linksboven naar rechtsonder en van rechtsboven naar linksonder) gelijk zijn aan 90.
Probeer het eens. De juiste oplossing vind je door op de figuur te klikken.
Voor meer puzzels: klik hier.
Wat er in dit geval gevraagd wordt is precies de definitie van magisch vierkant: de getallen op rijen, kolommen en diagonalen hebben dezelfde som, de magische som genoemd, in het voorbeeld is het 90.

Het oudste bekende magische vierkant staat bekend als de LoShu, en er hoort ook een legende met een schildpad bij, die dateert uit 2800 v. C. in China. Hier zie je het vierkant in kwestie, en in dit geval is de magische som gelijk aan 15.

Dit is een voorbeeld van een zuiver magisch vierkant, omdat het opgebouwd is met opeenvolgende getallen beginnend bij 1.
Magische vierkanten worden al eeuwenlang bestudeerd, en je komt ze ook soms tegen in de schilderkunst, en de bouwkunst. De bekendste voorbeelden zijn de ets Melencolia van Albrecht Dürer, waarvan je hier een detail ziet:


Dürer slaagt erin het jaartal waarin hij de ets maakte, namelijk 1514, te verwerken in het magische vierkant. De magische som is hier 34.
Ook bekend is het magisch vierkant op de Sagrada Familia in Barcelona:

een aangepaste versie van het vierkant van Dürer zoals je kan zien. De magische som is nu 33 (en dat is precies de leeftijd die Christus had toen hij stierf aan het kruis; rechts zie je een uitbeelding van de Judaskus - het is tenslotte een kathedraal).

Het maken van magische vierkanten en varianten ervan met bijkomende eigenschappen is een kunst. In de volgende figuur zie je er vier-in-een:

Niet alleen het volledige vierkant is magisch, maar ook het deelvierkant met de lichtblauwe rand, ook het geel met rode vierkant, en als je de figuur over 45 graden draait, dan ook het rode vierkant.
Kijk nog even terug naar de oplossing van de puzzel boven, en je zal merken dat naast de opgelegde eisen voor de sommen er nog heel wat andere groepen van vier getallen als som de magische som 90 hebben: gebroken diagonalen, 2 bij 2 deelvierkanten, de hoekpunten van 3 bij 3 vierkanten,...  Zo'n magisch vierkant wordt ook wel een duivels vierkant genoemd.
Er zijn dus allerlei varianten, een bespreking van een aantal ervan vind je bijvoorbeeld in dit document.

De grote specialist op gebied van magische vierkanten was zonder twijfel Benjamin Franklin. Franklin had blijkbaar een methode om snel magische vierkanten te maken. In een van zijn brieven lees je dat hij op een dag aan een kennis beloofde dat hij 's avonds wel eens een magisch vierkant in elkaar zou steken. De volgende dag stuurde hij hem het volgende op:

(klik voor een vergroting). Dit 16 bij 16 vierkant heeft naast de gewone eigenschappen (som van rijen, kolommen, diagonalen is 2056) ook nog opmerkelijk veel andere kenmerken. De gelijkgekleurde vakjes in de figuur hebben bijvoorbeeld ook als som 2056. Franklin noemt het in zijn brieven the most magically magical of any magic square ever made by any magician.
Wat de methode is die Franklin gebruikt heeft bij de constructie van zijn magische vierkanten, dat blijft tot op heden een raadsel.


Ook mijn lievelingswiskundige Leonhard Euler heeft een belangrijke rol gespeeld in de ontwikkeling van de magische vierkanten. Hij liet zien hoe je zuivere magische vierkanten kan maken met behulp van Latijnse vierkanten. Een Latijns vierkant van n bij n is een vierkant dat opgevuld is met n verschillende symbolen zodat in elke rij en kolom elk symbool precies eenmaal voorkomt. Een voorbeeld zie je hier: in dit 4 bij 4 Latijns vierkant vind je in elke rij en kolom boer (=1), dame (=2), heer (=3), aas (=4).


Merk op dat ook de vier kleuren ruiten (=1), harten (=2), schoppen (=3), klaveren (=4) in elke rij en elke kolom precies eenmaal voorkomen. Dit zijn dus in feite twee Latijnse vierkanten die over elkaar gelegd werden. Als we de zaak even symbolisch voorstellen m.b.v. getallen van twee cijfers, het eerste cijfer geeft de waarde van de kaart, het tweede cijfer de kleur (cijfers van 1 tot 4, zoals hierboven tussen de haakjes), dan krijg je dit beeld:


Het feit dat elke opeenvolging van twee cijfers uit 1, 2, 3, en 4 precies een keer voorkomt, maakt van dit vierkant een Grieks-Latijns vierkant (van orde 4), of Euler vierkant. Het leuke is dat het nu ook een magisch vierkant geworden is, met magische som 110, zoals je kan zien op de figuur.
In dit kader is het interessant het vermoeden van Euler te vermelden: Euler slaagde er niet in Grieks-Latijnse vierkanten van orde 6, 10, 14, 18,... te vinden, en hij formuleerde dan ook het vermoeden dat die niet bestaan.
In 1901 bewees G. Tarry dat een Grieks-Latijns vierkant van orde 6 inderdaad niet bestaat. Maar in 1959 vonden Parker, Bose and Shrikhande toch tegenvoorbeelden van het vermoeden van Euler, o.a. een Grieks-Latijns vierkant van orde 10, waarvan je hier een voorstelling ziet:


Voor een keer had Euler het bij het verkeerde eind!
Merk op dat de stap van Latijns vierkant naar Sudoku niet groot is.
  

---

Paul C. Pasles, Benjamin Franklin's Numbers. An Unsung Mathematical Odyssey. Princeton University Press (2008) 254 pagina's. Wil je vooral meer weten over Benjamin Franklin, en over zijn magische vierkanten, dan is dit het ideale boek. Het gaat echter niet enkel over deze passie van Franklin, waarvan hij zelf zei dat er nooit een nuttige toepassing van gevonden kon worden (een uitspraak die overigens absoluut niet juist blijkt te zijn).  Formuledichtheid: Θ Ο Ο Ο Ο  (wel veel getallen!) Moeilijkheidsgraad: Θ Θ Ο Ο Ο Score: Θ Θ Θ Θ Ο

---

Seymour S. Block, Santiago A. Tavares, Before Sudoku. The World of Magic Squares. Oxford University Press (2009) 239 pagina's. In dit boek vind je naast een beknopte geschiedenis een heleboel informatie over magische vierkanten in twee, drie en zelfs vier dimensies. Elke bladzijde verbaast je met nieuwe vormen van magische vierkanten die allerlei nieuwe kenmerken hebben, om maar enkele voorbeelden te geven: je leest er bijvoorbeeld over palindromische magische vierkanten die opgebouwd zijn uit palindromen, of magische vierkanten met enkel priemgetallen. Formuledichtheid: Θ Ο Ο Ο Ο Moeilijkheidsgraad: Θ Θ Ο Ο Ο Score: Θ Θ Ο Ο Ο

---

Arno van den Essen, Magische vierkanten. De wonderbaarlijke geschiedenis van wiskundige puzzels. Van Lo-Shu tot sudoku. Veen Magazines (2006) 238 pagina's. Het enige Nederlandstalige boek van de drie is zeker een aanrader. Je vindt hier een bespreking van de hand van Ionica Smeets, een van de wiskundemeisjes (toch spijtig dat ze gestopt zijn met hun blog!). Het 8 bij 8 vierkant in het artikel van Ionica staat ook op de postzegel die je iets hoger vindt. Als je er op klikt, dan krijg je meer detail. Formuledichtheid: Θ Ο Ο Ο Ο Moeilijkheidsgraad: Θ Θ Ο Ο Ο Score: Θ Θ Θ Θ Ο

---

Geschreven in Algemeen | 3 Reacties | Vaste link | Afdrukken

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 | 0 Reacties | Vaste link | Afdrukken

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 | 24 Reacties | Vaste link | Afdrukken

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 | 0 Reacties | Vaste link | Afdrukken

07. Januari 2009, 17:15

Mijn vrouw heeft zeven (7!) schoenenwinkels in de stad waar ze wel eens komt en haar smaak vindt. Vandaag vergezel ik haar omdat het nieuwe paar mijn nieuwjaarscadeau voor haar zal zijn. Het belooft dus een lange dagvullende vergelijkende studie te worden. De kunst is om overtuigend te klinken bij het aanprijzen van kandidaat-schoenen, zodat het niet klinkt alsof ik me er vlug van wil afmaken.

In de eerste winkel ziet ze al direct een mooi paar. Maar uiteraard wil ze “nog wat verder kijken”. Ik zeg dat ze hier misschien nog spijt van krijgt, omdat het niet zeker is dat ze er nog mooier vindt. Ze weet dat ze me nooit zal kunnen overtuigen om straks in deze eindejaarsdrukte terug te keren naar een eerder bezochte winkel. Het bijbelse getal zeven volstaat om mijn liefde te bewijzen, herhalingen zouden overdreven zijn. Als ze me tot de laatste winkel meesleurt, zal ze daar haar schoenen moeten kopen.

De schoenen in de tweede winkel kunnen niet tippen aan die van de vorige winkel. Mijn vrouw is er niet meer gerust in. “Ik koop vanaf nu het eerste paar dat mooier is dan dat van de eerste winkel,” beslist ze.

Hieruit blijkt nogmaals hoe sterk de vrouwelijke intuïtie is als het over kanstheorie gaat.

Het secretaresseprobleem

De hierboven geschetste situatie is een voorbeeld van het secretaresseprobleem en is vooral bekend geworden door het artikel in Scientific American van Martin Gardner in februari 1960. Sindsdien verschijnen regelmatig uitbreidingen en varianten van dit probleem in statistische of wiskundige tijdschriften. Andere namen waaronder dit vraagstuk gepubliceerd werd: het googolspel, het huwelijksprobleem, het bruidschatprobleem van de sultan, of het taartenprobleem.

De uitdaging is om een optimale keuze te maken uit een (eindige) rij van mogelijkheden: het goedkoopste tankstation vóór de grens, de mooiste schoenen, de meest bekwame secretaresse, het lief dat het best bij u past,… Kenmerkend is telkens dat de mogelijkheden zich sequentieel aanbieden, dat iedere kandidaat kan geëvalueerd worden in vergelijking met de voorgaande, maar op een verzaakte keuze kan nooit teruggekomen worden.

Natuurlijk zijn we in deze situatie nooit helemaal zeker dat we de beste keuze gemaakt hebben, want om dit te weten, moeten we alle mogelijkheden beoordeeld hebben, en de twijfelaar die wacht tot de laatste kandidaat moet deze noodgedwongen kiezen. Maar we kunnen wel een strategie bepalen die de kans maximaliseert om de beste keuze te maken.

De optimale strategie

Stel dat we de beste uit n mogelijkheden moeten kiezen, dan is het altijd slim om de eerste r gewoon te bekijken en te laten passeren (0 ≤ r < n), en ons vanaf kandidaat r+1 voor te nemen om te kiezen voor de beste tot hiertoe. Als we pech hebben, bevindt de beste keuze zich in de eerste r gepasseerde mogelijkheden, en zullen we met deze strategie altijd doorgaan tot de laatste mogelijkheid (die we dan noodgedwongen selecteren).

De hamvraag is natuurlijk, hoe groot moet r zijn om de kans op het kiezen van de beste kandidaat te maximaliseren?

Met behulp van fundamentele kanstheorie rekenen we de kans P(n,r) uit dat we de beste keuze maken volgens bovenstaande strategie. We nemen aan dat de volgorde waarin we de kandidaten beoordelen willekeurig is. Het is geen slecht idee om eerst P(n,r,k) te berekenen, de kans op succes bij onze strategie op voorwaarde dat de beste kandidaat op de k-de plaats komt in de beschouwde rij (1 ≤ k ≤ n). Dan zien we:

                           P(n,r,k)=0 als k ≤ r

                           P(n,r,k)=1 als k = r+1

Bovendien, als k=r+2 dan missen we de optimale keuze enkel als de (r+1)-ste mogelijkheid beter is dan de eerste r mogelijkheden, dus

                           P(n,r,r+2) = r/(r+1)

Algemeen:

                           P(n,r,k)=r/(r+k-1) als  r < k ≤ n

Omdat de rangorde van deze optimale keuze willekeurig is, hebben we telkens een kans 1/n dat deze zich op plaats k bevindt, voor iedere k. We besluiten:

                           P(n,r) = 1/n [1 + r/(r+1) + r/(r+2) + … + r/(n-1)]

Merk op dat P(n,0)=P(n,n-1)=1/n, wat logisch is, want dan volgen we een strategie die ofwel altijd de eerste ofwel altijd de laatste mogelijkheid selecteert.

Als we nu terugkeren naar het verhaaltje van de schoenwinkels (n=7), dan vinden we de volgende succeskansen:

P(7,0) = 0,142857

P(7,1) = 0,35

P(7,2) = 0,414286

P(7,3) = 0,407143

P(7,4) = 0,352381

P(7,5) = 0,261905

P(7,6) = 0,142857

Omdat P(7,2) de grootste waarde geeft, is het inderdaad het slimste om in de eerste twee winkels enkel wat rond te kijken, en vanaf de derde winkel tot kopen over te gaan (als daar schoenen liggen die mooier zijn dan alle vorige kandidaten).

Het asymptotische gedrag

Stel in het voorgaande x = r/n, de fractie van de keuzemogelijkheden die we sowieso aan ons laten voorbijgaan. Als n nu voldoende groot is, dan kunnen we P(n,r) benaderen door

                           P(n,r) ≈ -x . ln(x)

welke maximaal wordt voor x = 1/e≈0.36788 (met e het getal van Euler). Bovendien is deze maximale kans dan ook gelijk aan 1/e.

Besluit: Als we dus de beste uit een lange rij van mogelijkheden willen kiezen, aangenomen dat we een niet geselecteerde kandidaat niet meer kunnen terugroepen, dan laten we best ongeveer 37% kandidaten passeren en kiezen vanaf dan de beste. We hebben dan ongeveer 37% kans dat we met deze strategie effectief de beste er hebben uitgepikt. Trouw dus niet met je eerste liefje, maar wacht ook niet te lang.

Varianten

Gilbert en Mosteller bestudeerden een versie van het secretaresseprobleem waarbij de kandidaten numeriek kunnen voorgesteld worden door een rij van getallen die onafhankelijk en uniform tussen 0 en 1 geselecteerd worden. In dit geval kan het grootste getal met een kans van ongeveer 58% gevonden worden (voor kleine waarden van n is de kans zelfs groter).

We kunnen ook streven om een zo goed mogelijke secretaresse uit de rij van kandidaten te pikken, zelfs al is het niet de beste. Hier veronderstellen we dat we een numerieke evaluatie voor de kandidaten ter beschikking hebben. In 2006 publiceerde Bearden een optimale strategie die gemiddeld de hoogste score haalt (opnieuw met de veronderstelling dat de waarden onafhankelijk en uniform uit [0,1] geselecteerd werden). Het blijkt dat we nu pas vanaf kandidaat √n de maximale waarde moeten selecteren, nadat we de voorgaande mogelijkheden hebben laten passeren.

Verder lezen

• Een goede plaats om te beginnen is "Who solved the secretary problem?" van Thomas S. Ferguson (Statistical Science 4(3), 282-296, 1989). Hij geeft een historisch overzicht van de verschillende versies van het probleem in de literatuur, en wie de oplossingen publiceerde. Hij citeert o.a. een vraagstuk uit 1875 van Arthur Cayley dat dicht aanleunt bij het secretaresseprobleem. Ferguson gaat zelfs nog verder terug in de tijd en merkt op dat de sterrenkundige J. Kepler voor zijn tweede huwelijk de optimale keuze maakte uit elf kandidaten, namelijk de vierde (Susanna Reuttinger).
  
• Martin Gardner maakte het probleem populair bij het "grote publiek" in 1960 in zijn Scientific American column van februari.
• De eerste geschreven bron die het secretaresseprobleem in onze versie formuleert (met tevens een vermelding van de optimale strategie) is een brief van Merril Flood in 1958.
  
• Een klassiek artikel in deze materie is "Recognizing the maximum of a sequence" van J. Gilbert en F. Mosteller (J. Amer. Statist. Assoc. 61, 35-73, 1966). Verschillende veralgemeningen en varianten van het probleem worden hier behandeld, o.a. wanneer de rij getallen uit een gekende verdeling komt.
• J. N. Bearden publiceerde vrij recent zijn oplossing in het geval het niet alleen om de beste keuze gaat maar om een zo goed mogelijke keuze: "A new secretary problem with rank-based selection and cardinal payoffs" (Journal of Mathematical Psychology 50, 58-59, 2006).
• Ondertussen heeft het secretaresseprobleem ook haar plaats gevonden binnen gebieden zoals "psychologische beslissingstheorie", "bestuurswetenschappen" of "gedragsmatig operationeel onderzoek". Zie bijvoorbeeld het werk van D. Seale en A. Rapoport.
• Tenslotte raden we u zeker Hoofdstuk 14 aan uit het boek "Impossible" van Julian Havil, dat volledig gewijd is aan het maken van de beste keuze (zie onze boekenrubriek).

Geschreven in Algemeen | 0 Reacties | Vaste link | Afdrukken

27. November 2008, 16:30

Neem de proef op de som, bekijk of verzamel zelf een grote lijst met getallen. Bijvoorbeeld de maandsalarissen in uw gemeente of de aandeelkoersen op de beurspagina van uw krant. Natuurlijk, sommige van deze getallen beginnen met een 2, maar dat zullen er aanzienlijk minder zijn dan de getallen die met een 1 beginnen. Het begincijfer 3 blijkt nog zeldzamer, en uiteindelijk vormen de getallen die met een 9 beginnen een kleine minderheid.

 

Verfrommelde pagina's

Dit is verrassend omdat we van willekeurige getallen zouden verwachten dat de cijfers van 1 tot 9 evenveel kans hebben om als begincijfer op te treden. Al in 1881 observeerde Simon Newcomb dit fenomeen. Deze wiskundige astronoom ontleende een veelgebruikt boekje met logaritmetafels uit de universiteitsbibliotheek, en hij observeerde dat vooral de pagina’s met getallen met begincijfer 1 er verfrommeld uitzagen. Hij publiceerde zelfs een artikel waarin hij de volgende formule voorstelde:

 

 

 

waar "log" hier voor het logaritme met grondtal 10 staat.

De wet van Benford

In 1938 kwam de natuurkundige Frank Benford tot dezelfde bevinding, onbewust van de eerdere observatie door Newcomb. Het verschil was dat hij zich baseerde op meer dan twintigduizend getallen, willekeurig geplukt uit kranten en edities van Reader’s Digest. Sinds zijn publicatie refereert iedereen naar deze formule als “de wet van Benford”.

 

 

 

Als je de wet toepast op een grote lijst met getallen dan betekent dit voor de verschillende begincijfers de volgende fracties:

 

 

1 : 30,1%
2 : 17,6%
3 : 12,5%
4 : 9,7%
5 : 7,9%
6 : 6,7%
7 : 5,8%
8 : 5,1%
9 : 4,6%

 

 

 

Bovendien blijkt Benford’s wet “schaalinvariant” te zijn. De bovenstaande percentages blijven bijvoorbeeld geldig voor beursnoteringen ongeacht we euro’s, dollars of Zwitserse franken gebruiken.

 

Maar zolang een wet niet verklaard of bewezen wordt, neemt ze een folkloristische plaats in naast de wetten van Murphy, Moore,... Dit veranderde toen de kanstheoreticus Ted Hill de zaak ernstig begon te nemen in de jaren 90 van de vorige eeuw.  In 1994 toonden zijn simulaties aan dat de wet van Benford eveneens opgaat in andere talstelsels, dus dat ze onafhankelijk is van de gekozen basis b (b=2 voor binaire getallen, b=10 voor decimale getallen, b=16 voor hexadecimale getallen, enz…), op voorwaarde dat je in de formule het logaritme in dezelfde basis b beschouwt.

 

Maar het echte nieuws kwam in 1996 toen Hill een formeel wiskundig bewijs vond voor de wet van Benford. De cruciale voorwaarde in zijn bewijs is dat de getallen willekeurig uit verschillende kansverdelingen gekozen worden, met dus ook een variërend bereik (zoals dit het geval was bij de gegevens waarop Benford zich gebaseerd had). Bijvoorbeeld, de getallen op de beurspagina in de krant betreffen aandelen uit verschillende marktsectoren.

 

Een goede illustratie is de verzameling van alle huisnummers in een stad. Als we ons beperken tot een straat met juist 99 huizen dan is de wet van Benford duidelijk niet juist, want dan geldt de uniforme verdeling (elke cijfer treedt exact 11 keer als begincijfer op). Maar in een stad zijn vele straten, met wisselende lengtes, dus is het na enige reflectie helemaal geen verrassing dat meer huisnummers met een 1 beginnen dan met een 9. De verdienste van Hill is natuurlijk dat hij juist de voorspelde frequenties van Newcomb en Benford kon aantonen.

Fraudebestrijding

Sinds het resultaat van Hill wordt de wet van Benford in enkele praktische toepassingen gebruikt om een “niet-natuurlijk” patroon in numerieke gegevens te detecteren, zeg maar om fraude te ontmaskeren. Het schijnt dat in sommige staten van de VS de belastingaangiften en boekhoudingen van grote bedrijven getest worden op hun Benford-frequenties opdat gemanipuleerde bedragen door de mand zouden vallen. Zelfs de belastingaangifte van Bill Clinton zou op deze manier op onregelmatigheden gecontroleerd zijn (maar ze passeerde gelukkig de Benford-test). Op de website van Georgia Tech kan je lezen dat ook het Internationaal Instituut voor Ontwikkeling van Geneesmiddelen in Brussel zijn toevlucht zoekt tot de wet van Benford om echte klinische resultaten te scheiden van verzonnen cijfermateriaal.

Logaritmische kleuters en indianen

Een verklaring voor de ongelovige reactie van de meeste mensen wanneer je hen met de ongelijke frequenties van begincijfers confronteert, is misschien te vinden in het werk van Stanislas Dehaene en zijn medewerkers. Deze Franse wiskundige met belangstelling voor psychologie en neurowetenschap mocht dit jaar op voldoende belangstelling rekenen, zowel in vaktijdschriften als in de populariserende media (zie bijvoorbeeld Science 320).

Zijn stelling is dat onze lineaire visie op de spreiding van de natuurlijke getallen cultureel gevormd werd en tegen-natuurlijk is. Inderdaad, nu vinden we het normaal dat de afstanden tussen de opeenvolgende getallen alle even groot zijn. We situeren bijvoorbeeld het getal 5 juist in het midden van 1 en 9. Maar het is ooit anders geweest, toen we als kleuter nog onbevangen naar de dingen keken. Experimenten bij jonge kinderen, maar ook bij de Mundurucu-indianen in het Amazonewoud, onthullen dat onze aangeboren intuïtie eerder een logaritmische spreiding van de natuurlijke getallen aanneemt. Op de logaritmische schaal liggen getallen dichter bij elkaar naarmate ze groter worden. Iemand die nog niet geïndoctrineerd is door de “lineaire meetlat”, zal geneigd zijn om de afstand naar het volgende getal in te schatten volgens de proportie waarmee het vorige getal vermeerderd wordt. De afstand tussen 1 en N wordt dus gegeven door de harmonische som:

 

 

die asymptotisch benaderd wordt door ln(N).

 

 

Daarom waarschijnlijk dat oudere mensen vinden dat de jaren sneller passeren. Voor een vijftiger heeft een jaar relatief minder te betekenen dan voor een tienjarige. Tja, waarom beginnen niet alle leeftijden met een 1?

 

Verder lezen

• S. Newcomb, Note on the frequency of use of the different digits in natural numbers, American Journal of Mathematics 4, 39-40, 1881.
• F. Benford, The law of anomalous numbers, Proceedings of the American Philosophical Society 78, 551-572, 1938.
• De korte publicatie van Joël Perras in McGill Mathematics Magazine.
• In het boek "Impossible" van Julian Havil staat een heel hoofdstuk over de wet van Benford. Zie onze boekenrubriek
• Dossier Onvermijdelijke Wetmatigheden op de website van Voortschrijdende Inzichten.
• "Benford and your taxes", op de Unreal Blog.
• "Looking out for number one", op de website van Plus Magazine.
• T. Hill, A Statistical Derivation of the Significant-Digit Law, Statistical Science 10, 354-363, 1996. 
• Tamás Lolbert, On the non-existence of a general Benford's law, Mathematical Social Sciences 55, 103-106, 2008.
• S. Dehaene, V. Izard, E. Spelke, P. Pica, Log or linear? Distinct intuitions of the number scale in western and Amazonian Indigene cultures, Science 320 (5880), 1217-1220, 2008.

Geschreven in Algemeen | 3 Reacties | Vaste link | Afdrukken