BibwijzerLogische raadsels over gekleurde mutsen
Alex van den Brandhof
Prometheus, Amsterdam, ISBN 9 789044 653793
Wellicht ben je al meer dan eens een probleem tegengekomen over gevangen kabouters met gekleurde mutsen. Zij zien hun eigen muts niet, maar door te redeneren op basis van de kleuren van de mutsen die ze wel zien, moeten ze de kleur van hun eigen muts achterhalen. Dit is nodig om vrij te komen.
Alex van den Brandhof is wetenschapsjournalist met een steengoede rubriek in de krant NRC (Nieuwe Rotterdamse Courant) en wiskundeleraar in een secundaire school in Basel (Zwitserland). In het recente boekje De kabouterformule toont hij dat er heel veel dergelijke mutsenproblemen bestaan.
Als voorbeelden halen we hier het eerste, het vijfde, het veertiende en het twintigste (laatste) probleem aan. Bij het eerste probleem (‘de gong’) volstaat logisch nadenken. Bij het vijfde (‘in een kring’) is ook modulorekenen nodig. Het veertiende (‘het Fanovlak’) wordt opgelost met eindige meetkunde en het laatste probleem (‘een oneindige rij’) door te steunen op het ‘keuzeaxioma’. Voor meer details en voor de zestien andere problemen raden we je aan om dit leuke boek te lezen.
Keizer Beulmans houdt zeven kabouters gevangen. Hij heeft twaalf mutsen, zes rode en zes blauwe en dat weten de kabouters. De kabouters krijgen allemaal één van de twaalf mutsen op hun hoofd. Ze zien hun eigen mutskleur niet, maar wel die van alle anderen. Nadat Beulmans drie kabouters een rode muts en vier kabouters een blauwe muts heeft opgezet, zegt hij: ‘Ik sla straks op de gong. Wie weet welke mutskleur hij heeft, mag na die slag opstaan en vertrekken.’ Nadat Beulmans op de gong heeft geslagen, blijven alle kabouters zitten. Een minuut later vervolgt Beulmans: ‘Ik sla zo dadelijk nog eens op de gong. Wie weet welke mutskleur hij heeft, mag dan opstaan en vertrekken.’ Zolang er niemand opstaat, herhaalt Beulmans elke minuut zijn oproep en zijn slag op de gong. Op een gegeven moment staan alle kabouters op en lopen naar de uitgang (waar uiteraard een bewaker staat die verifieert of de kabouters niet bluffen). Wanneer gebeurt dat?
De kabouters weten dat niet alle mutsen dezelfde kleur hebben. Als een kabouter bij al zijn collega’s één zelfde mutskleur zou zien, bv. blauw, dan weet die dus dat hij een rode muts draagt. Een stapje verder: als een kabouter zou zien dat één collega rood draagt en alle andere collega’s blauw, dan weet hij dat, als hij blauw zou dragen, de collega met de rode muts zijn eigen kleur zou kennen.
Laten we nu het probleem van de gong aanpakken, met drie rode en vier blauwe mutsen. Zet je schrap, lezer. Neem als gegeven dat A, B en C een rode muts dragen en D, E, F en G een blauwe muts. A ziet dus twee rode mutsen. Hij maakt de volgende redenering:
”Veronderstel dat ik blauw heb. Dan zien B en C elk maar één rode muts. In dat geval zal B denken:
“Als ik blauw heb, ziet C enkel blauwe mutsen en weet hij dat hij rood heeft. In dat geval zou C bij de eerste gong opstaan. Omdat dit niet gebeurt, weet ik na de eerste gong dat mijn muts rood is. Ik sta op na de tweede gong.”
In deze redenering zijn B en C verwisselbaar. C zou (nog steeds in de veronderstelling dat ik blauw heb) dezelfde redenering maken als B en ook na de tweede gong opstaan. Omdat B en C bij de tweede gong blijven zitten, weet ik (A) dat mijn veronderstelling fout is. Ik heb dus een rode muts op. Na de derde gong sta ik op.”
B en C maken dezelfde redenering als A en staan dus ook na de derde gong op.
D, E, F en G zien dat A, B en C na de derde gong opstaan en weten hiermee dat er maar drie rode mutsen zijn. Ze weten dus dat zij een blauwe muts hebben en staan meteen ook op.
De redenering hierboven is al best pittig. In het boek brengt van den Brandhof de oplossing trager aan, door te beginnen met het analoge probleem met minder kabouters. Hij legt ook de historiek van het probleem uit (het werd in de jaren 1930 bedacht) en veralgemeent tot meer kabouters en meer kleuren.
Keizer Beulmans houdt vier kabouters gevangen. Ze worden in een kring rondom een dikke boom geplaatst, elk met een muts op in de kleur rood, blauw of geel. Elke kabouter kan alleen de mutsen van de twee kabouters naast hem zien; de boom ontneemt het zicht op de kabouter tegenover hem. Zodra Beulmans een signaal geeft, moeten de kabouters, tegelijkertijd, hun eigen mutskleur raden. Ze worden vrijgelaten als ten minste één kabouter het goed heeft. Voordat Beulmans de kabouters in een kring plaatst en de mutsen verdeelt, kunnen de kabouters met elkaar overleggen. Wat moeten ze afspreken om vrij te komen?
We benoemen de vier kabouters zodat ze als de hoekpunten van een vierkant ABCD geplaatst zullen worden, dus zo dat A en C enkel B en D zien en omgekeerd. Ze spreken af om de kleuren te associëren met getallen:
rood = 0, blauw = 1, geel = 2
en met deze getallen te rekenen ‘modulo 3’. In het boek is een korte appendix over modulorekenen voorzien. Noem \(a\) het getal van de kleur van A enz. Ze spreken verder af dat
- A kleur \(b+d\) zal zeggen,
- B kleur \(-a-c\),
- C kleur \(b-d\)
- en D kleur \(c-a\).
Op die manier, zo wordt in het boek netjes bewezen, zal er altijd minstens een kabouter zijn die de juiste kleur zegt. In plaats van het bewijs hier op te nemen, verifiëren we het op een voorbeeld.
Veronderstel dat A een rode muts krijgt, B een gele, C een blauwe en D een gele. Dan is \(a=0, b=2, c=1, d=2\).
- A zegt \(2+2=1\) (blauw, fout).
- B zegt \(-0-1=2\) (geel, juist).
- C zegt \(2-2=0\) (rood, fout).
- D zegt \(1-0=1\) (blauw, fout).
Bij dit voorbeeld zegt één kabouter de juiste kleur geel en worden ze dus vrijgelaten.
Keizer Beulmans houdt zeven kabouters gevangen. Hij heeft mutsen in zeven kleuren. De kabouters kennen die zeven kleuren. Van elke kleur heeft de keizer drie mutsen. Hij geeft elke kabouter een muts, allemaal van een verschillende kleur. Voordat de kabouters hun mutsen opzetten, mogen ze de kleur ervan bekijken. Terwijl Beulmans de resterende veertien mutsen op tafel legt, zegt hij: ‘Straks pakken jullie, één voor één, twee mutsen van tafel en zetten die op, zodat iedereen drie mutsen op zijn hoofd heeft. Daarna wijs ik twee kabouters aan. Als ze ten minste één gemeenschappelijk mutskleur hebben, laat ik jullie allemaal vrij. Voordat Beulmans elke kabouter een muts geeft, kunnen de kabouters met elkaar overleggen. Wat moeten ze afspreken om vrij te komen?
De kabouters gebruiken het Fanovlak. In dit ‘eindig projectief vlak’ zijn er zeven punten en zeven lijnen. In figuur 1 wordt ook de cirkel als een lijn bekeken. (Daarom schrijf ik net als de Nederlanders `lijn’ en niet `rechte’.) Op elke lijn liggen juist drie punten en door elk punt gaan juist drie lijnen. Elk paar punten bepaalt juist één lijn en elk paar lijnen heeft juist één snijpunt. De kabouters kleuren op voorhand de punten en de lijnen in de zeven kleuren van de beschikbare mutsen. Ze leren figuur 1 uit het hoofd.
Figuur 1 Vlak van Fano in de kleuren van de mutsen
De kleur van de muts die ze krijgen, is de kleur van één van de zeven lijnen. Op deze lijn ligt alvast een stip met dezelfde kleur als de lijn. Er blijven nog twee stippen met een andere kleur op deze lijn over. Als tweede en derde muts nemen ze die van de twee andere punten op die lijn.
Bijvoorbeeld: de kabouter die de gele muts kreeg, neemt de donkerblauwe en de rode muts.
Welk kabouterpaar Beulmans ook kiest, die twee hebben altijd een gemeenschappelijke kleur, namelijk de kleur van het snijpunt van de twee lijnen bepaald door de kleuren van hun eerste mutsen.
Bijvoorbeeld: neemt hij de kabouter die de oranje muts kreeg en de kabouter die de donkerblauwe muts kreeg, dan is lichtblauw de gemeenschappelijke kleur.
In het boek verneem je verder voor welke andere aantallen kabouters en kleuren er zo’n oplossing met een eindig projectief vlak mogelijk is.
Keizer Beulmans houdt oneindig veel kabouters gevangen. Ze worden achter elkaar in een rij geplaatst, elk met een muts op in de kleur rood of blauw. Elke kabouter kan alleen de mutsen van de kabouters vóór hem zien. Er is één kabouter die helemaal achteraan in de rij staat; die ziet al zijn collega’s. Vóór elke kabouter staan oneindig veel kabouters. Elke kabouter kent zijn plaats in de rij. Zodra Beulmans een signaal geeft, moeten de kabouters tegelijkertijd hun eigen mutskleur raden. Ze worden vrijgelaten indien slechts eindig veel kabouters verkeerd gokken. Voordat Beulmans de mutsen verdeelt, kunnen de kabouters met elkaar overleggen. Wat moeten ze afspreken om vrij te komen?
Merk op: het volstaat niet dat oneindig veel kabouters juist gokken; er mag maar een eindig aantal kabouters fout gokken.
De kabouters delen de mogelijke oneindige rijen van rood en blauw op in klassen. Twee rijen die op slechts een eindig aantal plaatsen verschillend zijn, behoren tot dezelfde klasse. Twee rijen die op oneindig veel plaatsen verschillend zijn, behoren tot verschillende klassen.
Tijdens hun overleg kiezen ze uit elke klasse een representant. Nadat de mutsen verdeeld zijn, herkennen de kabouters de klasse waarin hun mutsenrij zich bevindt. Hiervoor is het genoeg dat elke kabouter de mutsen vóór hem ziet, want op een eindig aantal mutsen komt het niet aan. De kabouter die op de \(n\)-de plaats in de rij staat, noemt de kleur die hoort bij de \(n\)-de plaats van de representant. Omdat de werkelijke rij en de representant slechts op een eindig aantal plaatsen verschillend zijn, zal maar een eindig aantal kabouters fout gokken en worden alle kabouters vrijgelaten.
Het is natuurlijk verre van realistisch dat er oneindig veel kabouters zijn, dat die kabouters oneindig veel mutsen kunnen zien en dat ze herkennen van welke klasse die rij is. Maar wiskundig gezien is er nog een fundamenteler probleem: er zijn oneindig veel klassen van rijen en er bestaat geen voor de hand liggend recept om uit elk van deze klassen een representant te kiezen. Je kunt niet één voor één een representant uit alle klassen kiezen, want de klassen kunnen niet op een rij worden gezet. Hun aantal is overaftelbaar. Toch moeten ze uit elke klasse een representant kiezen (en die onthouden). Dit brengt de kabouters tot in de fundamenten van de wiskunde!
Het wiskundig postulaat dat zegt dat je bij oneindig veel verzamelingen altijd uit elke verzameling één element kunt kiezen, is het zogenaamde keuzeaxioma, geformuleerd door Ernst Zermelo in 1904. Het keuzeaxioma is geen gevolg van de andere axioma’s van de verzamelingenleer (de axioma’s van Zermelo-Frænkel). Je kunt het keuzeaxioma aannemen en werken in het systeem van Zermelo-Frænkel met het keuzeaxioma erbij, of het niet aannemen. Je kunt dit vergelijken met het parallellenpostulaat in de meetkunde: je kunt het aannemen en dan zit je in de euclidische meetkunde, maar er is ook niet-euclidische meetkunde…
Laten we hopen dat de kabouters het keuzeaxioma aanvaarden… en ook dat ze niet kleurenblind zijn.