Vrijkomen met een slimme truc

Vrijkomen met een slimme truc

In april van dit jaar verscheen in het tijdschrift The American Mathematical Monthly de volgende leuke puzzel. 

De opgave

Vier kaarten liggen op tafel in een rij. Daarvoor zijn 24 mogelijkheden, die hier allemaal zijn opgesomd. Alice mag twee kaarten verwisselen. Als ze dat doet zoals hier aangegeven (rood omcirkeld), kan Bob gegarandeerd de juiste kaart vinden. In de gevallen waarbij de te verwisselen kaarten gestippeld zijn omcirkeld, is de verwisseling niet noodzakelijk – Alice kan de kaarten in die gevallen ook gewoon laten liggen.

In april van dit jaar verscheen in het tijdschrift The American Mathematical Monthly de volgende leuke puzzel.

Alice en Bob zitten onder de hoede van bewaker Charlie in de gevangenis. Alice wordt naar het kantoor van Charlie gebracht. Daar krijgt ze 52 speelkaarten (met de afbeelding naar boven) te zien, die op een rij liggen in willekeurige volgorde. Alice mag twee kaarten verwisselen. Vervolgens draait Charlie alle kaarten om. Alice verlaat dan Charlies kantoor en Bob komt binnen. Charlie roept willekeurig één kaart (bijvoorbeeld ‘ruiten zeven’). Bob moet die kaart nu zoeken. Daartoe mag hij, één voor één, maximaal 26 kaarten omdraaien. Als het hem lukt de door Charlie genoemde kaart te vinden, worden Alice en Bob vrij gelaten. Vind een strategie die ervoor zorgt dat Alice en Bob gegarandeerd vrij komen.

Zoals altijd bij dit soort raadsels, kennen Alice en Bob de spelregels en mogen ze vóóraf overleggen. Vanaf het moment dat Alice Charlies kantoor betreedt, is elke vorm van communicatie verboden.

Het aardige van dit raadsel is dat het er in eerste instantie op lijkt dat de actie die Alice mag uitvoeren – het verwisselen van twee kaarten – volstrekt zinloos is, omdat Alice ná het wisselen geen woord meer met Bob kan uitwisselen. De kaarten liggen bij aanvang in willekeurige volgorde. Hoe kan Alice in hemelsnaam een ordening aanbrengen als ze maar twee kaarten verwisselen mag? Kan zo’n minieme actie ervoor zorgen dat Bob hun vrijlating kan waarborgen?

Advies van Pólya

Bij raadsels waar ik niet direct zie hoe je tot de oplossing komt, volg ik altijd het advies van de Hongaarse wiskundige György Pólya. Die zei: als het je niet lukt een bepaald probleem op te lossen, maak het probleem dan eenvoudiger, zodat je het wél kan oplossen.

Die 52 kaarten zijn er wel heel erg veel. Wat als er nu maar twee kaarten op tafel liggen, Alice ze desgewenst mag verwisselen, en Bob één kaart mag omdraaien? Het raadsel is dan niet zo moeilijk. Stel dat op de kaarten de getallen 1 en 2 staan (als er iets anders op staat, bijvoorbeeld een aap en een geit, dan kun je de kaarten coderen: ‘aap’ = 1, ‘geit’ = 2). Er zijn twee mogelijke volgordes: 1-2 en 2-1. Alice en Bob kunnen het volgende afspreken: als de volgorde 1-2 is, doet Alice niets, en als de volgorde 2-1 is, verwisselt ze de twee kaarten. Bob kan dan zonder te gokken de juiste kaart omdraaien.

We gaan naar de situatie met vier kaarten. Alice mag er twee verwisselen, en Bob mag er maximaal twee (de helft van het totale aantal) omdraaien. Natuurlijk kan Alice er niet met zekerheid voor zorgen dat de kaarten in de volgorde 1-2-3-4 komen te liggen. Dat zou wel lukken als de beginvolgorde bijvoorbeeld 1-2-4-3 is, maar met bijvoorbeeld 4-3-2-1 gaat het niet. Dat geeft echter niet, want Bob mag een foutje begaan: hij hoeft niet direct de goede kaart om te draaien. Hij heeft twee kansen en dat blijkt genoeg te zijn. Als je eerst zelf wilt nadenken over de strategie, moet je nu nog niet verder lezen.

Stel dat Charlie meedeelt dat Bob de kaart met de 1 erop moet vinden, dan draait Bob de eerste kaart om. En als Charlie de kaart met 2, 3 of 4 roept, draait Bob de tweede, derde respectievelijk vierde kaart om. De kans dat Bob goed zit, is één op vier. Als hij het níét goed heeft, mag hij nog een kaart omdraaien. Die moet dan wel goed zijn – daarna is het bekeken. Bob gaat als volgt te werk. Als op de omgedraaide kaart het getal x staat, draait hij de x-de kaart om. Daarmee heeft hij gegarandeerd succes, mits Alice op een slimme manier twee kaarten heeft verwisseld.

Stel dat de beginvolgorde van de kaarten 4-3-2-1 is. Alice verwisselt dan de tweede en de derde kaart, zodat de volgorde 4-2-3-1 wordt. Als Charlie 1 zegt, draait Bob de eerste kaart om. Daar staat een 4 op, dus daarna draait hij de vierde kaart om, en zie: dat is de 1. Als Charlie 2 zegt, draait Bob de tweede kaart om; in één keer goed! Als Charlie 3 zegt, draait Bob de derde kaart om; ook meteen goed! En als Charlie 4 zegt, draait Bob de vierde kaart om. Daar staat een 1 op, dus draait Bob vervolgens de eerste kaart om, en ja hoor: dat is de 4.

Krijgt Alice het bij élke mogelijke beginvolgorde voor elkaar om zodanig twee kaarten om te draaien, dat deze strategie altijd werkt? Ja, kijk maar naar de illustratie. Daarin is voor elke beginvolgorde (er zijn 24 mogelijkheden) aangegeven hoe Alice te werk moet gaan.

Zes kaarten

Met zes kaarten kan Bob drie pogingen doen. Dat betekent dat Alice ervoor moet zorgen dat de kaarten zó liggen, dat ze ‘cyclisch’ liggen waarbij de lengte van elke ‘cykel’ ten hoogste drie is. Met een paar voorbeelden zal ik laten zien wat ik hiermee bedoel.

De cykels in 3-2-5-4-6-1 zijn 1-3-5-6 (lengte vier), 2 (lengte één) en 4 (lengte één). Het rijtje 2-5-4-1-6-3 heeft maar één cykel, namelijk 1-2-5-6-3-4 (lengte zes). De cykels in 2-3-1-6-4-5 zijn 1-2-3 en 4-6-5 (beide lengte drie).

Kan Alice, die twee kaarten mag verwisselen, ervoor zorgen dat er nooit een cykel is die langer is dan drie? Bij 3-2-5-4-6-1 kan ze de derde en de zesde kaart verwisselen: 3-2-1-4-6-5. Er zijn dan vier cykels: 1-3 en 5-6 (beide lengte twee) en 2 en 4 (beide lengte één). Dat gaat dus goed: in dit voorbeeld heeft Bob zijn derde poging niet eens meer nodig.

Met zes kaarten zijn er 720 mogelijke volgordes. Dat is wel erg veel om ze allemaal na te lopen. Gelukkig kun je ook met een slimme redenering aantonen dat het altijd mogelijk is om twee kaarten zó te verwisselen, dat de vrijlating van Alice en Bob verzekerd is. Het idee is als volgt. Alice gaat op zoek naar de langste cykel, zeg c1-c2-…-ck. Ze hoeft alleen twee kaarten te verwisselen als k, de lengte van die cykel, groter is dan 3. In dat geval verwisselt ze de kaarten c1 en c1+k/2 (waarbij k/2 naar boven wordt afgerond indien k oneven is). De langste cykel wordt op die manier gesplitst in twee cykels die ofwel even lang zijn, ofwel slechts 1 verschillen in lengte. Omdat er maar één cykel kan zijn met een lengte van minstens 4, betekent dit dat er na Alice’s actie geen cykel meer is die langer dan 3 is.

De originele vraag

Tot slot de originele opgave, met de 52 speelkaarten. Het is natuurlijk geen probleem om die kaarten te coderen, bijvoorbeeld ‘harten aas’ = 1, ‘harten twee’ = 2, …, ‘schoppen heer’ = 52.

Met 52 kaarten is het al helemaal ondoenlijk om alle mogelijkheden af te gaan. Er zijn 52 × 51 × 50 × 49 × … × 1 mogelijkheden. Dat komt neer op ongeveer 8 × 1067. Ja, dat is een groot getal. Héél groot. Het is zo groot, dat elke persoon die ooit op aarde heeft geleefd de 52 kaarten in een verschillende volgorde zou kunnen vasthouden – en dan nog zouden er een heleboel volgordes overblijven.

Maar je kunt met een redenering die vergelijkbaar is met de redenering die ik voor zes kaarten gaf, aantonen dat het altijd mogelijk is om zodanig twee kaarten te verwisselen, dat alle cykels een lengte van hooguit 26 hebben. En daarmee is de vrijlating van Alice en Bob verzekerd.