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.
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
K | M | K | K | K | K | K | M |
M | K | M | K | M | K | M | K |
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).
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
# kruis |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
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).
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
# kruis |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
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).
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
# kruis |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
5 |
En tenslotte nog een keer met zestien (= 2 × 2 × 2 × 2) groepen.
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
# kruis |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
4 |
De voorgaande vier tabellen voeg ik samen.
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
# kruis |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
6 |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
5 |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
5 |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
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.
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
# kruis | Oneven |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
6 | 0 |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
5 | 1 |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
5 | 1 |
K | M | K | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
4 | 0 |
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:
- 12345 = 1 × 10000 + 2 × 1000 + 3 × 100 + 4 × 10 + 5 × 1
= 1 × 104 + 2 × 103 + 3 × 102 + 4 × 101 + 5 × 100
Een binair getal van vijf cijfers, bijvoorbeeld 10101, interpreteer je zo:
- 10101 = 1 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 1 × 1
= 1 × 24 + 0 × 23 + 1 × 22 + 0 × 21 + 1 × 20
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).
Decimaal | Binair |
00 | 0000 |
01 | 0001 |
02 | 0010 |
03 | 0011 |
04 | 0100 |
05 | 0101 |
06 | 0110 |
07 | 0111 |
08 | 1000 |
09 | 1001 |
10 | 1010 |
11 | 1011 |
12 | 1100 |
13 | 1101 |
14 | 1110 |
15 | 1111 |
.. | .... |
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.
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
# kruis | Oneven |
K | M | M | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
5 | 1 |
K | M | M | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
4 | 0 |
K | M | M | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
5 | 1 |
K | M | M | K |
K | K | K | M |
M | K | M | K |
M | K | M | K |
3 | 1 |
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:
- Ik heb het hier uitgewerkt met 16 tegels, maar het kan ook met 32 tegels, of 64, of 128, enzovoort.
Het hoeft dus absoluut geen vierkant veld met tegels te zijn, dat is niet relevant, en er is ook geen bovengrens aan het aantal
tegels (afgezien van het praktische aspect).
Er is maar één ding belangrijk: dat het totale aantal tegels een macht van twee is.
- Het aantal tegels moet een macht van twee zijn, omdat de munten slechts twee toestanden kennen, kop of munt.
Daarom moet alles als het ware vertaald worden naar het binaire systeem.
Indien er in plaats van munten dingen zouden liggen met meer vrijheidsgraden, zoals bijvoorbeeld dobbelstenen, dan wordt het een
ander verhaal.
- Het zou natuurlijk kunnen dat de munten bij het begin al goed liggen en aangeven onder welke tegel de
sleutel ligt (als gevolg van puur toeval).
Indien er dan toch een munt omgekeerd moet worden dan moet dat de munt op de laatste tegel zijn, want dat is de enige munt die geen
invloed heeft op de code die aangeeft waar de sleutel ligt.
Dat zie je in de tabel, omdat onder het nummer van de laatste tegel zich alleen maar paarse vakjes bevinden.
- Omdat de kolom, die aangeeft of het aantal malen kruis even of oneven is, in principe 0000 (= decimaal nul)
kan opleveren heb ik de eerste tegel genummerd met nul.
Diezelfde kolom kan maximaal 1111 (= decimaal vijftien) opleveren, en niet zestien, en daarom is het het handigst om de tegels te
nummeren van nul tot en met vijftien.
De tegels kunnen eventueel wel genummerd worden van één tot en met zestien, maar dat levert dan ergens een extra vertaalslag op
(en extra kans op fouten).