Het probleem van de gevangenen

Een cipier legt twee gevangenen de volgende situatie voor. Hij zegt: ik heb buiten een vierkant gemaakt van zestien tegels en op iedere tegel ligt een munt. Iedere munt ligt volkomen willekeurig met kop of munt naar boven gericht en onder een van de zestien tegels ligt de sleutel van jullie cel. Straks neem ik een van jullie mee naar buiten, ik vertel hem onder welke tegel de sleutel ligt en daarna mag hij één munt omkeren als hint voor de ander. Vervolgens haal ik de ander op en is het aan die ander om de correcte tegel op te lichten en de sleutel te pakken. Vindt hij de sleutel dan zijn jullie allebei vrij, vindt hij de sleutel niet bij de eerste poging dan blijven jullie levenslang opgesloten. Jullie mogen nu overleggen wat jullie gaan doen.

De sleutel van de beide cellen
In eerste instantie lijken de gevangenen voor een hopeloze opgave te staan. De zestien munten zijn geheel willekeurig neergelegd en er is dus geen enkele regelmaat te vinden in de verdeling van de koppen en munten. Hoe verstop je daar dan een hint in? Hoe verstop je een cruciaal stuk informatie in een chaotisch patroon? En dan ook nog door maar één munt om te keren? Toch is er wel degelijk een uitweg (letterlijk en figuurlijk) uit dit probleem en de beide gevangenen gaan na intensief overleg de uitdaging aan. Hieronder volgt hun strategie.

Om te beginnen maak ik een plaatje van het veld met de zestien tegels.
Op iedere tegel ligt een munt en de verdeling van koppen en munten is willekeurig.

Rood = kop en groen = munt
(maar het mag ook andersom, dat maakt uiteindelijk niets uit,
en nee, hier zit geen vooropgezet plan in, ze liggen echt willekeurig)
Ik kies ook nog een tegel waar de sleutel onder ligt.
Ik ga alle tegels nummeren en ik heb goede redenen (zoals later zal blijken) om bij nul te beginnen.
Ik ga een tabel maken. De eerste rij geeft de nummers van de tegels en de tweede rij geeft aan of er kop of munt ligt op die betreffende tegel.
0001020304050607 0809101112131415
KMKKKKKM MKMKMKMK
Vervolgens ga ik die tweede regel opdelen in twee gelijke groepen en ik noteer aan het eind van de regel het aantal malen kruis in de oneven groep, de eerste groep dus (die heb ik geel gemaakt).
0001020304050607 0809101112131415 # kruis
KMKK KKKM MKMK MKMK 6
Ik doe dit nog een keer, maar nu verdeel ik de regel in vier (= 2 × 2) gelijke groepen. Wederom noteer ik aan het eind van de regel het aantal malen kruis in de oneven groepen, de eerste - en de derde groep (de gele groepen).
0001020304050607 0809101112131415 # kruis
KMKK KKKM MKMK MKMK 5
Je voelt het wellicht al aankomen, ik doe dit ook een keer met acht (= 2 × 2 × 2) gelijke groepen. Aan het eind van de regel noteer ik het aantal malen kruis in de oneven groepen (de gele groepen).
0001020304050607 0809101112131415 # kruis
KMKK KKKM MKMK MKMK 5
En tenslotte nog een keer met zestien (= 2 × 2 × 2 × 2) groepen.
0001020304050607 0809101112131415 # kruis
KMKK KKKM MKMK MKMK 4
De voorgaande vier tabellen voeg ik samen.
0001020304050607 0809101112131415 # kruis
KMKK KKKM MKMK MKMK 6
KMKK KKKM MKMK MKMK 5
KMKK KKKM MKMK MKMK 5
KMKK KKKM MKMK MKMK 4
Ik ga nog een kolom toevoegen en daarin noteer ik een één wanneer het aantal malen kruis oneven is, in het andere geval (een even aantal kruizen) noteer ik een nul.
0001020304050607 0809101112131415 # kruisOneven
KMKK KKKM MKMK MKMK 60
KMKK KKKM MKMK MKMK 51
KMKK KKKM MKMK MKMK 51
KMKK KKKM MKMK MKMK 40
Deze laatste kolom wordt de informatieoverbrenger tussen de eerste - en de tweede gevangene door dit als een tegelnummer te beschouwen in binaire vorm. In ons dagelijks leven denken en rekenen wij decimaal (tien cijfers, nul tot en met negen), maar zoals je wellicht weet denken en rekenen computers binair (twee cijfers, nul en één). Een decimaal getal van vijf cijfers, bijvoorbeeld 12345, interpreteer je zo: Een binair getal van vijf cijfers, bijvoorbeeld 10101, interpreteer je zo: Waaruit volgt dat 10101 (binair) gelijk is aan 16 + 0 + 4 + 0 + 1 = 21 (decimaal). De omrekentabel tussen decimaal en binair ziet er zo uit (alleen het begin natuurlijk, want de tabel gaat oneindig lang door).
DecimaalBinair
000000
010001
020010
030011
040100
050101
060110
070111
081000
091001
101010
111011
121100
131101
141110
151111
......
In de kolom die even of oneven aangeeft staat nu 0110 (van boven naar beneden). In bovenstaande tabel zien we dat dat decimaal het getal zes voorstelt. De sleutel ligt echter onder tegel elf en dat is binair 1011. Oftewel, 0110 moet veranderd worden in 1011. Het eerste, tweede en vierde cijfer moeten daarom veranderen. Wanneer ik in de samengestelde tabel kijk met al die gele en paarse hokjes, dan zie ik dat de munt op tegel twee precies de enige is die invloed uitoefent op het eerste, tweede en vierde cijfer. Conclusie: de munt op tegel nummer twee moet omgekeerd worden! Door dat te doen, de munt op tegel twee gaat van kruis naar munt, ontstaat deze tabel.
0001020304050607 0809101112131415 # kruisOneven
KMMK KKKM MKMK MKMK 51
KMMK KKKM MKMK MKMK 40
KMMK KKKM MKMK MKMK 51
KMMK KKKM MKMK MKMK 31
De laatste kolom geeft nu 1011 aan (van boven naar beneden) hetgeen overeenkomt met elf in het decimale stelsel. Indien de eerste gevangene zijn huiswerk foutloos volbrengt dan keert hij de munt op tegel twee om. Indien vervolgens de tweede gevangene zijn huiswerk foutloos volbrengt dan weet hij dat de sleutel onder tegel elf ligt en zijn ze allebei vrij. Hoera!

Enkele opmerkingen tot slot: