Kabouters met een mutsprobleem

Drie kabouters zitten in het café. Ieder krijgt van de barman een muts op zijn hoofd. De kleur van de muts – rood of blauw – bepaalt de barman steeds met een muntworp. Niemand ziet zijn eigen kleur muts, alleen de kleuren van de anderen. Zodra de barman een signaal geeft, moeten de kabouters, tegelijkertijd, hun eigen kleur muts raden, maar ze mogen ook „ik pas” zeggen. Enige vorm van communicatie is uiteraard verboden. Ze winnen een meter bier als niemand verkeerd gokt én ten minste één kabouter de kleur van zijn muts goed raadt. Belangrijk: vóórdat de barman de mutsen verdeelt, kunnen de kabouters met elkaar overleggen. Welke strategie maximaliseert de winstkans?

Dit raadsel mag ver van de Grote Wiskundige Problemen – zoals het vermoeden van Goldbach of de Riemann-hypothese – afstaan, het is goudeerlijke wiskunde. De geschiedenis van raadsels waarbij kabouters (of logici, of gevangenen) hun mutskleur moeten raden, gaat terug tot minstens de beginjaren zestig van de vorige eeuw. Toen publiceerde Martin Gardner (1914-2010), de man die het grote publiek won voor de ‘recreatieve wiskunde’, al een mutsenraadsel.

Goudeerlijke wiskunde

Het zojuist beschreven raadsel werd in 1998 geïntroduceerd door informaticus Todd Ebert, als onderdeel van zijn proefschrift. Dat ging niet over mutsen; het was Peter Winkler, wiskundige van Dartmouth College in de Verenigde Staten, die het probleem twee jaar later in een mutsencontext goot, voor een conferentie ter ere van Gardner. Winkler geldt als een expert voor dit soort puzzels.

Het is niet moeilijk om een strategie te bedenken die met een kans van 1/2 (50 procent) tot succes leidt: de drie kabouters (A, B en C) spreken af dat A ‘rood’ zegt, terwijl B en C passen. Als meer dan één kabouter zomaar wat raadt, nemen ze een onnodig risico. Als A en B gokken, terwijl C past, is de winstkans 1/4 (25 procent). En als ze alle drie gokken, wordt de winstkans nog eens gehalveerd: 1/8 (12,5 procent).

Winstkansen opschroeven

Wordt een kabouter wijzer van het kijken naar de mutsen van zijn vrienden? Kunnen ze hun winstkans van 50 procent verhogen? Dat lijkt niet het geval, want de mutskleuren worden met muntworpen, dus onafhankelijk van elkaar, beslist. Maar de kabouters zijn erg slim (dit is bij elk mutsenprobleem een stilzwijgende aanname) en kunnen hun winstkans opschroeven tot 75 procent. Wie eerst zelf over de sublieme strategie die hiertoe leidt wil nadenken, moet nu even stoppen met lezen.

In de overlegtijd spreken de kabouters het volgende af. Wie twee verschillend gekleurde mutsen ziet, past. En wie twee gelijk gekleurde mutsen ziet, roept de kleur die hij niet ziet. Dus als A en B allebei een rode muts op hebben, roept C ‘blauw’. De illustratie in de inzet maakt duidelijk dat de winstkans 75 procent is: er zijn 2³ = 8 mogelijkheden, waarvan er 6 tot winst leiden.

Er is trouwens nog een andere strategie, eveneens in de inzet weergegeven, die ook in 6 van de 8 gevallen winstgevend is.

Geniale kabouterstrategie

De geniale strategie van de drie kabouters heeft twee bijzondere eigenschappen. Ten eerste: als er verloren wordt, wordt er goed verloren. Dat betekent: bij verlies gokken álle kabouters fout. Ten tweede: bij winst wordt er zuinig gewonnen. Dat wil zeggen: één kabouter gokt goed, de rest past. Een strategie met deze eigenschappen heet ‘volmaakt’.

Wiskundigen zoeken graag naar algemene oplossingen. Hoe gaan de kabouters te werk als ze met meer dan drie zijn? Toen het mutsenprobleem rond de eeuwwisseling ruime bekendheid kreeg, werd duidelijk dat het probleem voor een willekeurig aantal kabouters razend lastig is. Het lukte wiskundigen wél om te bewijzen dat een volmaakte strategie alleen bestaat als het aantal kabouters gelijk is aan een macht van twee, min één (dus 2² – 1 = 3, 2³ – 1 = 7, 2⁴ – 1 = 15 enzovoort). De winstkans bij n kabouters is dan n gedeeld door n + 1. Zeven kabouters krijgen hun meter bier dus met een kans van 7/8 (87,5 procent), vijftien kabouters met een kans van 15/16 (93,75 procent) enzovoort.

CD-correcties

Verrassend: de oplossing maakt gebruik van Hammingcodes, vernoemd naar Richard Hamming (1915-1998). De Hammingcode is een van de eerste zogeheten foutcorrigerende codes, die in de praktijk worden gebruikt bij de productie van onder meer cd’s. De codes maken het mogelijk dat je een schijfje ook nog ongestoord kunt afspelen als er een paar krasjes op zitten.

Bij het mutsenraadsel met zeven kabouters worden Hammingcodes als volgt gebruikt. De kabouters nummeren zich van 1 tot en met 7 en noteren hun nummer binair: 001, 010, 011, 100, 101, 110, 111. Elke kabouter telt de binaire getallen van de kabouters met (voor hem zichtbare) rode mutsen bij elkaar op. Niet op de gebruikelijke wijze van optellen, maar cijfer voor cijfer, met de rekenregel 1 + 1 = 0, bijvoorbeeld 010 + 110 = 100. Is de uitkomst 000, roept hij ‘rood’. Is de uitkomst zijn eigen getal, zegt hij ‘blauw’. In alle andere gevallen past hij. Deze strategie is volmaakt en leidt met een kans van 112 op 128, ofwel 87,5 procent, tot winst.

Ook als het aantal kabouters een tweedemacht is, vonden wiskundigen optimale strategieën. Daarvoor gebruikten zij zogeheten ‘verlengde Hammingcodes’. De strategieën die in deze gevallen tot de grootste winstkans leiden, zijn niet volmaakt.

Onzuivere munten

Als de barman de kleur van elke muts bepaalt met een muntworp zijn alle mogelijkheden even waarschijnlijk, aangenomen dat de munt zuiver is. Maar hoe pakken de winstkansen uit bij onzuivere munten? Dit tot voor kort onopgeloste, asymmetrische mutsenprobleem heeft Theo van Uem, docent toegepaste wiskunde aan de faculteit Techniek van de Hogeschool van Amsterdam, nu opgelost. Althans, ten dele. Voor een klein aantal kabouters kon hij met behulp van brute computerrekenkracht enkele openstaande problemen oplossen.

De kans op rood

Een daarvan is de klassieke versie met drie kabouters en twee mutskleuren, waarbij de kans op rood een zekere waarde p heeft en de kans op blauw 1 – p. Het aantal mogelijke scenario’s blijft weliswaar 8, maar deze zijn niet meer – zoals in het symmetrische geval – even waarschijnlijk. Daarom is de winstkans niet eenvoudigweg 6 op 8, ook al leiden 6 van de 8 mogelijkheden tot winst. Van Uem rekende uit dat de optimale winstkans nu gelijk is aan 1 – p + p². De kabouters moeten dan niet meer strategie 1 hanteren. Doen ze dat wel, dan leidt dat bij p = 0,9 tot een winstkans van slechts 27 procent, zo rekende Van Uem uit. Hij liet de computer alle mogelijke strategieën doorrekenen en kwam tot de conclusie dat strategie 2 altijd optimaal is, bij zuivere én onzuivere munten. Als p = 0,9 is de winstkans 1 – 0,9 + 0,92 = 0,91 (91 procent).

Winkler, die het werk van Van Uem heeft bestudeerd, zegt niet te weten of diens formule voor de optimale winstkans ooit eerder is gepubliceerd. Maar het bewijs van de juistheid van de formule is volgens Winkler niet heel moeilijk. „De door Van Uem bedachte methode is er niet voor nodig”, zegt hij in een reactie.

Het wachten is op quantumcomputers

Dat betekent niet dat Van Uems aanpak oninteressant is. Van Uem onderzocht nog enkele specifieke gevallen – vier kabouters, vijf kabouters, of drie kleuren in plaats van twee – en dat leidde tot boeiende resultaten. Toch heeft Van Uems methode, ondanks zijn relatief lage rekenkundige complexiteit, zijn beperkingen. Winkler: „Bij negen kabouters moeten bij Van Uems methode al meer dan 10⁸⁰ strategieën worden doorgerekend, ongeveer even veel als het aantal elementaire deeltjes in ons universum.”

Van Uem beaamt dat: „Ook hier is het wachten op nog veel snellere quantumcomputers.”