Recent heb ik met veel plezier een voorstelling van de film The Imitation Game bijgewoond. Over Alan Turing, die het kraken van de code van de Enigmamachines als één grote puzzel bekeek. Ik ben zelf ook altijd erg geïnteresseerd geweest in puzzels, en dan vooral dat soort puzzels waar je de volgende 2 vragen bij hebt: (1) ontbreekt er niet een gegeven in de opgave? en (2) hoe begin je nu aan zoiets? Hier is een voorbeeld dat ik al heel lang ken:

Het raadsel van de monniken

In een klooster waar de monniken een gelofte van stilte hebben afgelegd, doet de abt op een bepaalde dag een aankondiging. Hij vertelt dat een aantal monniken een ziekte hebben opgelopen en dat deze ziekte zich uit door vlekken in het aangezicht. Hij vraagt dan ook aan de besmette monniken om het klooster te verlaten om zich te laten behandelen. Omdat er in het klooster geen spiegels zijn en de monniken ook niet met elkaar mogen communiceren, kunnen de monniken niet uit zichzelf ontdekken of ze de ziekte hebben. De monniken zien elkaar wel één keer per dag bij het ochtendgebed. De dag na de aankondiging zijn alle monniken er nog, de tweede dag ook, en dat gaat zo verder, tot en met de negende dag. Op de tiende dag na de aankondiging is er bij het ochtendgebed geen spoor meer van de besmette monniken. Hoeveel besmette monniken waren er dan?

Ik ga het antwoord hier niet verklappen, denk er zelf eerst over na. Één ding wil ik wel zeggen: om het raadsel te kunnen oplossen moet je jezelf als het ware in de plaats van een van de monniken stellen. En je mag daarbij veronderstellen dat de monniken perfect logisch kunnen redeneren.

Terwijl ik vorig jaar in de maand augustus meedeed aan de Vakantiecursus Wiskunde georganiseerd door het Platform Wiskunde Nederland, een twee dagen durende cursus voor leraren secundair onderwijs (altijd de moeite waard overigens!), kwam ik in contact met Hans van Ditmarsch, die er een voordracht verzorgde, en net een boek uit had met de intrigerende titel: 100 gevangenen en een gloeilamp. Het boek bevat allerlei gelijkaardige logische puzzels. O.a. deze, waar het boek zijn titel vandaan haalt:

Honderd gevangenen en een gloeilamp

Aan een groep van honderd gevangenen, gezamenlijk in de gevangeniskantine, wordt medegedeeld dat ze allemaal in isolatiecellen geplaatst zullen worden en daarna één voor één ondervraagd, in een kamer met een lamp met een aan-uitschakelaar. De gevangenen kunnen met elkaar communiceren door de lamp aan of uit te doen (dat is de enige manier waarop ze kunnen communiceren). De lamp is aan het begin uit. Er is geen vaste volgorde van ondervraging, er is geen standaard tijdsduur tussen de ondervragingen, en dezelfde gevangene kan best meerdere keren na elkaar ondervraagd worden. Als een gevangene ondervraagd wordt, kan deze: niets doen, de lamp uitdoen, de lamp aandoen, of verklaren dat iedereen (tenminste een keer) ondervraagd is. Als dit waar is, worden alle gevangenen vrijgelaten. Anders worden ze allemaal opgehangen. Kunnen de gevangenen, zolang ze nog bij elkaar zijn in de kantine en niet naar de isolatiecellen gebracht zijn, een protocol overeenkomen waardoor ze vrijgelaten worden?

Het antwoord is ja. Hoe moeten ze dat dan doen? Weet je een goede strategie, aarzel niet om ze te delen met ons, als reactie op deze blog.

Hans van Ditmarsch en Barteld Kooi, Honderd gevangenen en een gloeilamp, Epsilon Uitgaven, Utrecht (2013) 105 pagina's.

Dit boek bevat 9 logische puzzels. Niet alleen de twee die je hierboven vindt, maar ook bijvoorbeeld het drie-deurenprobleem van Monty Hall, dat recent weer werd bovengehaald op deze blogsite: hier en hier. Elk van de negen puzzels wordt eerst voorgesteld, soms in deelpuzzels opgesplitst, en uiteindelijk opgelost. De lezer krijgt het antwoord niet zomaar, hij moet er voor werken. Vaak worden er varianten besproken, en je komt ook veel te weten over de origine van de puzzels. Zo blijkt dat de puzzel van de 100 gevangenen voor het eerst opduikt (op het internet) in 2002.

Achteraan in het boek vind je de oplossingen van de deelpuzzels.

Wat er typisch is aan de puzzels in dit boek, dat verwoorden de auteurs zelf zo in de inleiding: de puzzels waarom het hier gaat hebben alle als speciaal aspect dat je moet nadenken over wat een ander denkt, of, preciezer, dat ze gaan over wat jij weet over wat een ander weet.

Binnenkort verschijnt er een Engelse vertaling van dit boek.

Een verrassend boek.

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

Nog wat boeken

In de reeks Wetenschappelijke biografie van Veen Media zijn recent weer een paar biografieën verschenen die je als wiskundige gelezen moet hebben.

Het eerste boek gaat over John Von Neumann (1903-1957), een van de grootste wiskundigen van de vorige eeuw. Er is een bekende anekdote over hem en die gaat over de oplossing van het probleem van de jetvlieg:

Twee treinen rijden op hetzelfde spoor in elkaars richting, tegen een snelheid van 50 km/u. Op het ogenblik dat ze op 100 km van elkaar zijn, vertrekt een vlieg tegen 75 km/u aan de voorzijde van de ene trein, vliegt naar de andere trein, daar aangekomen draait ze om, vliegt terug, en dat gaat zo verder tot ze geplet wordt bij de botsing van de twee treinen. Hoeveel kilometer heeft de vlieg dan afgelegd?

Toen deze puzzel aan Von Neumann werd voorgelegd, gaf hij onmiddellijk het juiste antwoord: 75 km. Toen hem gevraagd werd hoe hij dat dan precies had gedaan, antwoordde hij: ik heb de reeks gesommeerd. Inderdaad, als je de som berekent van alle afstanden heen en weer die de vlieg aflegt, dan bevat die som oneindig veel termen, en het eindresultaat is 75 km. Maar dit is niet de kortste manier om dit probleem op te lossen. Von Neumann was een rekenwonder, met een ijzersterk geheugen.

Von Neumann is vooral bekend door zijn rol in het Manhattan Project, in de ontwikkeling van de speltheorie, en bij de bouw van de eerste elektronische computer (ENIAC). En door enkele uitspraken:

Young man, in mathematics you don't understand things. You just get used to them.

If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is.

There probably is a God. Many things are easier to explain if there is than if there isn't.

Giorgio Israel en Ana Millán Gasca, Von Neumann. Het rijke leven van een wiskundige duizendpoot. Veen Media (2014) 160 pagina's.

Zoals we het gewoon zijn in deze reeks ook nu weer een gedegen biografie van wonderkind John Von Neumann, een erg belangrijke figuur in de wiskunde van de twintigste eeuw. Het boek leest niet zo vlot, en er is niet zoveel plaats voor de vele anekdotes die bekend zijn over Von Neumann. Lees hiervoor zeker het boek Prisoner's Dilemma van William Poundstone uit 1992.

Mooi geïllustreerd boek.

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

Jean Le Rond d'Alembert (1717-1783) is vooral bekend als encyclopedist. Samen met Diderot gaf hij een van de eerste encyclopediën uit, de Encyclopédie ou dictionnaire raisonné des sciences, des arts et des métiers.

Onze studenten kennen hem van het Convergentiekenmerk van d'Alembert, een stelling waarmee je de convergentie van een bepaald type getallenreeksen kan nagaan. Ook wordt hij vaak genoemd in verband met de belangrijke Hoofdstelling van de algebra, die zegt dat elke niet-constante veelterm van graad n met complexe coëfficiënten en met 1 veranderlijke ten minste 1 complex nulpunt heeft. d'Alembert was de eerste die een poging deed om dit te bewijzen, maar zijn bewijs was onvolledig.

In de mechanica staat hij bekend voor het Principe van d’Alembert. Meer over hem kan je lezen in het volgende boek.

Pierre Crépel e.a., D'Alembert. Begenadigd wiskundige van de Verlichting, Veen Media (2014) 160 pagina's.

Jean Le Rond d’Alembert (1717-1783) leefde in een zeer interessante periode, met tijdgenoten zoals Leonhard Euler en Daniel Bernoulli. Deze biografie belicht de verschillende kanten van deze persoonlijkheid. Je leest er bijvoorbeeld dat d’Alembert de eerste was die de beweging van een trillende snaar wiskundig wist te beschrijven (met behulp van een partiële differentiaalvergelijking), maar evengoed dat hij met iedereen ruzie maakte.

Het boek is erg mooi geïllustreerd, met vooraan een tijdsband met daarop de belangrijkste gebeurtenissen tijdens zijn leven.

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

En dit is pas binnengekomen:

Julian Havil, John Napier. Life, logarithms and legacy, Princeton University Press (2014) 279 pagina's.

Een boek over de Schotse wiskundige John Napier (1550-1617), de man van de Neperiaanse logaritme. John Napier was een veelzijdig man. Het eerste boek dat hij schreef was een grondige ontleding van het Bijbelboek Openbaring, waarbij hij liet zien dat het katholicisme inslecht was en de paus de antichrist. Napier zelf was protestant.

Zijn volgende boek was Mirifici Logarithmorum Canonis Descriptio (1614), waarin hij een methode beschrijft om het vermenigvuldigen van getallen te reduceren tot het berekenen van sommen. Napier was de vader van de logaritmentafels, die tot voor kort nog effectief werden gebruikt.

Hij was ook de uitvinder van de Napier Bones, een analoge computer avant la lettre.

Lees dit boek, je zal er van genieten. Het hoofdstuk over de Openbaring kan je eventueel overslaan.
De auteur Julian Havil zijn we al vaker tegengekomen in deze blog.

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

Hier vind je de oplossingen van de raadsels bovenaan.

Het raadsel van de monniken

In een klooster waar de monniken een gelofte van stilte hebben afgelegd, doet de abt op een bepaalde dag een aankondiging. Hij vertelt dat een aantal monniken een ziekte hebben opgelopen en dat deze ziekte zich uit door vlekken in het aangezicht. Hij vraagt dan ook aan de besmette monniken om het klooster te verlaten om zich te laten behandelen. Omdat er in het klooster geen spiegels zijn en de monniken ook niet met elkaar mogen communiceren, kunnen de monniken niet uit zichzelf ontdekken of ze de ziekte hebben. De monniken zien elkaar wel één keer per dag bij het ochtendgebed. De dag na de aankondiging zijn alle monniken er nog, de tweede dag ook, en dat gaat zo verder, tot en met de negende dag. Op de tiende dag na de aankondiging is er bij het ochtendgebed geen spoor meer van de besmette monniken. Hoeveel besmette monniken waren er dan?

De oplossing

Dag 0, de dag van de aankondiging.

Veronderstel dat er maar één zieke monnik was. Dan zou deze het klooster al dadelijk verlaten hebben: hij ziet namelijk enkel gezonde monikken. Er zijn dus zekere meerdere zieke monniken.

Dag 1, de dag na de aankondiging.
Stel dat er twee zieke monniken waren. Die twee monniken zagen op Dag 0 precies één zieke collega, en dachten bij zichzelf: die zien we morgen niet meer terug. Maar de volgende dag blijkt de monnik in kwestie nog steeds paraat. Het enige besluit dat ze dan kunnen trekken is: er is nog een tweede monnik ziek, en dat ben ikzelf.
In de loop van de dag verlaten beide monniken dan ook het klooster.

Dag 2.
Stel dat er drie zieke monniken waren. Die drie monniken zien op Dag 0 en op Dag 1 twee besmette collega's en redeneren feilloos (zoals hierboven): vóór Dag 2 zijn ze weg. Als de twee nog steeds in het klooster rondlopen op Dag 2, dan weten ze dat er nog een besmette monnik moet zijn, en dat kunnen ze enkel zelf zijn. Ze stappen dan ook alle drie diezelfde dag nog op.

En dat gaat zo voort.

Dag 9.
Enkel als er minstens tien monniken ziek waren, is het klooster nog niet kiemvrij op Dag 9. Inderdaad, bij negen of minder waren ze door bovenstaande redenering allemaal voor het ochtendgebed van Dag 9 weg.
Indien het er precies tien waren, ziet elk van deze monniken op Dagen 0 t.e.m 8 negen andere zieke monniken. Alle tien denken ze op Dag 8: morgen zijn ze er niet meer. En dan blijkt dat niet waar te zijn. Het enige besluit dat ze kunnen trekken is dat ze zelf ook besmet zijn. In de loop van dag 9 verlaten ze alle tien het klooster.

Het antwoord is dus: er waren 10 besmette monniken.

100 gevangenen en een gloeilamp

Aan een groep van honderd gevangenen, gezamenlijk in de gevangeniskantine, wordt medegedeeld dat ze allemaal in isolatiecellen geplaatst zullen worden en daarna één voor één ondervraagd, in een kamer met een lamp met een aan-uitschakelaar. De gevangenen kunnen met elkaar communiceren door de lamp aan of uit te doen (dat is de enige manier waarop ze kunnen communiceren). De lamp is aan het begin uit. Er is geen vaste volgorde van ondervraging, er is geen standaard tijdsduur tussen de ondervragingen, en dezelfde gevangene kan best meerdere keren na elkaar ondervraagd worden. Als een gevangene ondervraagd wordt, kan deze: niets doen, de lamp uitdoen, de lamp aandoen, of verklaren dat iedereen (tenminste een keer) ondervraagd is. Als dit waar is, worden alle gevangenen vrijgelaten. Anders worden ze allemaal opgehangen. Kunnen de gevangenen, zolang ze nog bij elkaar zijn in de kantine en niet naar de isolatiecellen gebracht zijn, een protocol overeenkomen waardoor ze vrijgelaten worden?

De oplossing

De gevangenen duiden onder elkaar iemand aan die we vanaf nu de Teller zullen noemen.
Voor alle gevangenen behalve de Teller geldt dan het volgende protocol:

• als je ondervraagd wordt en de lamp is uit en je hebt hem nog niet eerder aangedaan, doe hem dan aan;
• als je ondervraagd wordt en de lamp is uit en je hebt hem al eerder aangedaan, doe dan niets;
• als je ondervraagd wordt en de lamp is aan, doe dan niets.

Voor de Teller is dit het protocol:

• als je ondervraagd wordt en de lamp is uit, doe dan niets;
• als je ondervraagd wordt en de lamp is aan, doe hem dan uit – houd bij hoe vaak je dat doet;
• als je de lamp 99 keer hebt uitgedaan, verklaar dan dat alle 100 gevangenen ondervraagd zijn.

In essentie betekent dit dat elke gevangene behalve de Teller precies één keer de lamp aan doet, nl. de eerste keer dat ie ondervraagd wordt als de lamp uit is. De Teller doet telkens de lamp uit als ze aan is, en telt hoeveel keer dat al gebeurd is. Omdat elke gevangene slechts één keer de lamp aansteekt, wordt zo bijgehouden hoeveel gevangenen al ondervraagd zijn op een bepaald moment. Als de Teller ondervraagd wordt en ondertussen al 99 keer de lamp heeft uitgedaan, dan zijn alle gevangenen ondervraagd.

Noot: als er per dag precies één gevangene wordt ondervraagd, dan duurt het gemiddeld 28,5 jaar voor de teller op 99 komt!