Aan het einde van het artikel vroegen we ons af of dezelfde truc ook met een grotere stapel kaarten uitgevoerd kan worden. Dat kan inderdaad! We zullen dat bewijzen, en ook leggen we uit welke afspraken Boris en Annika moeten maken. Maar eerst kijken we naar een iets ander spel om wat meer inzicht te krijgen in wat het theoretische maximum aantal kaarten kan zijn.

Vijf kaarten trekken en alle vijf openleggen

Boris heeft een stapel kaarten, die aan één kant genummerd zijn: $1, 2, 3, \dots, n.$ Hij geeft de stapel aan Isa. Zij schudt ze en trekt er vijf uit, die ze bekijkt en aan Boris geeft. Deze bekijkt ze ook en schrijft dan naar keuze een van de overige getallen uit de dichte stapel op een papiertje, dat hij omgekeerd op tafel legt. Vervolgens legt hij de vijf kaarten in een door hem gekozen volgorde op tafel. Dan komt Annika binnen en zegt na even nadenken welk nummer op het papiertje  staat. En het klopt.

Onze vraag is nu: wat is het maximale aantal kaarten waarmee deze truc lukt?

Dat aantal kunnen we vinden door ons af te vragen hoeveel verschillende informaties Boris op tafel kan leggen door het kiezen van de volgorde van die vijf kaarten. Hij kan dat doen op  $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$ manieren. Annika ziet als ze binnenkomt vijf kaarten met getallen erop open op tafel liggen. Deze zijn van laag naar hoog: $k_1, k_2, k_3, k_4$ en $k_5.$ Boris en Annika hebben vooraf voor elke volgorde van deze vijf kaarten afgesproken met welk getal tussen $1$ en $120$ die correspondeert. Boris heeft er dus voor gezorgd dat Annika weet welk van de getallen $1$ tot en met $120$ bedoeld is.

Maar nu moeten we even opletten: Annika ziet al vijf van de kaarten uit de stapel open op tafel liggen. Die vijf kunnen het dus sowieso niet zijn. Als de rest van de dichte stapel nu precies $120$ kaarten bevat en ze die in gedachten op volgorde legt (waarbij ze de waardes van de open kaarten dus overslaat), kan ze met het aangeleverde getal de juiste kaart kiezen. Als er nog $121$ kaarten of meer dicht liggen, kan Annika niet de juiste kaart kiezen. Het maximaal aantal kaarten is dus $120 + 5 = 125.$

Met dezelfde redenering kun je voor $n$ kaarten trekken uit een grote stapel aantonen dat het maximale aantal gelijk is aan $n! + n.$

Dit is natuurlijk nog een redelijk simpel spel. Maar het wordt beduidend moeilijker.

Vijf kaarten trekken en een dicht en vier openleggen

Blijft het maximale aantal kaarten ook $5! + 5 = 125$ als Boris één van de vijf kaarten naar keuze dicht op tafel legt en de overige vier in een door hem gekozen volgorde open op tafel legt? Het is weliswaar zo dat Boris vijf keuzes heeft voor de dicht te leggen kaart en hij dus samen met de $4! = 24$ mogelijkheden voor de volgorde van de open te leggen kaarten in totaal weer op $120$ mogelijkheden komt. Maar Annika kan er maar vier zien en kan dus maar kiezen uit $4! = 24$ mogelijkheden. Dat lijkt onbegonnen werk, maar we zullen zien dat de keuze van de dicht te leggen kaart zó afgesproken kan worden dat Annika wel degelijk de benodigde extra informatie krijgt.

Echter, één verschil zien we wel direct. Stel je voor dat Annika wel alle informatie krijgt en dus uit de getallen $1$ tot en met $120$ kan kiezen. Dan moet ze echter kiezen uit de $120$ kaarten die nog op de stapel liggen, én de ene kaart die dicht op tafel ligt. Ze moet dus kiezen uit $121$ kaarten. En dat kan niet als je maar $120$ keuzes hebt. Het uiteindelijke theoretische maximum is dus $125 - 1 = 124$ kaarten waarmee het spel gespeeld zou kunnen worden.

Met dezelfde redenering kun je voor $n$ kaarten trekken uit een grote stapel aantonen dat het maximale aantal gelijk is aan $n! + n - 1.$

De cruciale afspraak

De methode die we gaan gebruiken is afkomstig van de Amerikaanse wiskundige Elwyn Berlekamp, die recent is overleden.

Boris krijgt vijf genummerde kaarten met in volgorde van grootte de getallen $k_1, k_2, k_3, k_4$ en $k_5$ erop. Dus: $k_1 < k_2 < k_3 < k_4 < k_5.$ Hij telt ze op $(s = k_1 + k_2 + k_3 + k_4 + k_5)$ en deelt het antwoord door $5.$ De rest $r$ is $1, 2, 3, 4$ of $5$ (als de som deelbaar is door $5$ nemen we als rest niet $0$ maar $5).$ Dus $r \equiv s ($modulo $5).$ Dan legt hij de kaart $k_r$ dicht op tafel. Vervolgens legt hij de andere vier kaarten in een zodanige volgorde dat een van de getallen $1$ tot en met $24$ wordt aangegeven. Annika weet dit alles, want dat is wat ze afgesproken hebben.

Voor we de algemene formulering van de oplossing geven, bespreken we een voorbeeld waarmee we laten zien dat Annika nu inderdaad genoeg weet.

Voorbeeld

We nemen als voorbeeld: $z_1 = 23, z_2 = 55, z_3 = 89, z_4 = 90$ als openliggende (zichtbare) kaarten. Laten we eens nagaan wat Annika nu allemaal weet. Ze kan de som van de openliggende kaarten berekenen:  $23 + 55 + 89 + 90 \equiv 2 ($modulo $5).$ Ze weet echter nog niet wat de $r$ is die Boris bepaald heeft en dus ook niet welke vier van de vijf kaarten $k_1, k_2, k_3, k_4$ en $k_5$ de zichtbare getallen $z_1, z_2, z_3$ en $z_4$ zijn.

Stel nou dat de dichte kaart $k_1$ was. Dan heeft Boris uit zijn som modulo $5$ dus een rest van $1$ gekregen. En dan is $k_1$ kleiner dan $23,$ want $23$ is dan uiteraard $k_2.$ Welke getallen kan $k_1$ dan zijn? Er moet gelden dat $k_1 + 23 + 55 + 89 + 90 \equiv 1 ($modulo $5)$ is. Dat is alleen zo als $k_1$ gelijk is aan één van de volgende getallen: $4, 9, 14$ of $19.$ Het volgende mogelijke getal zou $24$ zijn, maar dat is groter dan $23.$

Zo kunnen we verder redeneren voor de andere opties. Als de dichte kaart $k_2$ is, dan geldt $k_1 = 23, k_3 = 55$ en dan heeft Boris $r = 2$ gevonden. Dus dan geldt dat $k_2 + 23 + 55 + 89 + 90 \equiv 2 ($modulo $5)$ is en dat $k_2$ tussen $23$ en $55$ ligt. De opties daarvoor zijn: $25, 30, 35, 40, 45$ en $50.$

Zo verder redenerend vinden we precies $24$ mogelijke getallen die het zouden kunnen zijn. Zij zijn hieronder $\color{red}{rood}$ afgedrukt in de rij $(1,\dots 124).$ De mogelijke kaarten zijn in vijftallen geordend tussen haakjes (de setjes waar een openliggende kaart tussen zit zijn aangegeven door die getallen $\color{blue}{blauw}$ toe te voegen, die zijn het uiteraard sowieso niet).

De gehele rij ziet er dan als volgt uit:

$(1,\dots,{\color{red}4},5), (6,\dots,{\color{red}9},10), (11,\dots,{\color{red}{14}},15), (16,\dots,{\color{red}{19}},20), (21,22,z_1={\color{blue}{23}},24,{\color{red}{25}},26),$

$(27,\dots,{\color{red}{30}},31), (32,\dots,{\color{red}{35}},36), (37,\dots,{\color{red}{40}},41), (42,\dots,{\color{red}{45}},46), (47,\dots,{\color{red}{50}},51),$

$(52,53,54,z_2={\color{blue}{55}},{\color{red}{56}},57), (58,\dots,{\color{red}{61}},62), (63,\dots,{\color{red}{66}},67), (68,\dots,{\color{red}{71}},72), (73,\dots,{\color{red}{76}},77),$

$(78,\dots,{\color{red}{81}},82), (83,\dots,{\color{red}{86}},87), (88,z_3={\color{blue}{89}},z_4={\color{blue}{90}},91,92,{\color{red}{93}},94), (95,\dots,{\color{red}{98}},99), (100,\dots,{\color{red}{103}},104), $

$(105,\dots,{\color{red}{108}},109), (110,\dots,{\color{red}{113}},114), (115,\dots,{\color{red}{118}},119), (120,\dots,{\color{red}{123}},124).$

In totaal zijn er dus precies $24$ mogelijke kaarten die dicht op tafel kunnen liggen, niet meer en niet minder.

Het zijn: $4, 9, 14, 19, 25, 30, 35, 40, 45, 50, 56, 61, 66, 71, 76, 81, 86, 93, 98, 103, 108, 113, 118, 123.$

De algemene aanpak

We moeten natuurlijk nog beredeneren waarom er altijd precies $24$ opties ontstaan, al geeft bovenstaand voorbeeld daar al wel een soort idee van. Annika denkt in het algemeen als volgt na:

• Zij vraagt zich af: welke getallen zijn opties als de dichte kaart $k_1$ is? De getallen waar ze dan uit kan kiezen zijn de getallen $1$ t/m $z_1-1.$ Omdat Boris blijkbaar $k_1$ gekozen heeft, weet Annika ook nog dat voor alle mogelijke getallen $g$ geldt dat $g + z_1 + z_2 + z_3 + z_4 \equiv 1 ($modulo $5).$ Het kleinste getal dat rest $1$ geeft, noemen we $h.$ Dan weten we dat $h+1, h+2, h+3$ en $h+4$ allemaal niet rest $1$ geven als we ze optellen bij $z_1 + z_2 + z_3 + z_4,$ want zij geven dan rest $2, 3, 4$ en $5,$ respectievelijk. Het volgende getal dat wel weer kan kloppen is $h+5.$
  Enzovoorts. Kortom: in elk vijftal getallen kleiner dan $z_1$ zit precies één getal dat klopt.
• Er is uiteraard ook een grootste getal $H$ kleiner dan $z_1$ dat rest $r=1$ geeft. Dan bekijken we het rijtje $H+1, H+2, H+3, H+4, H+5, H+6.$ Van dit rijtje weten we een paar dingen. Ten eerste: het getal $z_1$ komt in dit rijtje voor, want $H$ is kleiner dan $z_1$ en $H+5$ is groter dan $z_1$ (anders zou $H+5$ het grootste getal kleiner dan $z_1$ zijn met de juiste rest, tenslotte). Ook weten we dat $H$ en $H+5$ rest $1$ geven bij deling door $5.$ Vanaf $z_1$ hebben we echter niet meer rest $1,$ maar rest $2$ nodig. Als $H+5$ rest $1$ geeft, geeft $H+6$ rest $2.$ Dat betekent dat in het vijftal dat overblijft uit het zestal $H+1, H+2, H+3, H+4, H+5, H+6$ als we $z_1$ wegdenken, weer precies één mogelijk getal voorkomt. En in elk volgend vijftal zit weer zo'n getal met rest $2$ (op dezelfde plek), tot we bij het grootste mogelijke getal kleiner dan $z_2$ komen.
• Zo passeren we ook de overige grenswaarden $z_2, z_3$ en $z_4.$ In elk vijftal (als we de grenswaarden $z_1, z_2, z_3$ en $z_4$ overslaan) zit dus een waarde die Boris gekozen kan hebben. We hebben dan precies $(124 - 4)/5 = 24$ vijftallen en dus $24$ waarden die Boris dicht op tafel gelegd kan hebben.
  En met de volgorde van de vier open kaarten kan Boris volgens afspraak de getallen $1$ tot en met $24$ aangeven en daarmee aan Annika duidelijk maken welke kaart hij dicht heeft neergelegd.
• Ten slotte kan het natuurlijk zo zijn dat er heel kleine gebieden $z_j, \dots, z_{j+1}$ zijn of dat twee of meer $z_j$’s naast elkaar liggen. In dat geval nemen we bij de overgang een groep van zeven of meer en vinden we in het volgende gebied van vijf (zonder de $z_j$’s) het eerste getal met de juiste volgende rest. In het voorbeeld hierboven is dat ook gebeurd, zoals je ziet.

Hoe de afspraken in praktijk te brengen

Stel nu eens voor dat Boris kaart $71$ dicht heeft neergelegd, de derde kaart, want $23 + 55 + 71 + 89 + 90 = 3 ($modulo $5).$ Omdat het tussen $z_2 = 55$ en $z_3 = 89$ in ligt, is $71$ het 14^e getal in de rij mogelijkheden (want $4 + 13 \times 5 + 2 = 71).$ Dat rekent Boris eenvoudig uit het hoofd uit. Boris weet dus dat hij met de volgorde van de vier open te leggen kaarten $14$ moet aangeven. Dat kan hij op meerdere manieren doen. Een van de mogelijkheden is: van laag naar hoog legt hij het volgende neer $55, 90, 23, 89.$ De betekenis die ze hebben afgesproken is:

Het laagste getal $(23)$ staat op plaats 3 Dat betekent: $14$ zit in het derde 6-tal van de $24 ($dus in $13, 14, 15, 16, 17, 18).$

Het volgende getal $(55)$ staat op plaats 1 van de overige drie getallen. Dat betekent $14$ zit in het eerste 2-tal van het al aangegeven 6-tal (dus in $13, 14).$

Het volgende getal $(89)$ staat op plaats 2 van de overige twee getallen. Dat betekent $14$ zit in het tweede 1-tal van het al aangeven 2-tal (dus $14).$

Daarmee weet Annika dat ze het 14^e getal van de $24$ mogelijkheden moet kiezen. Het eerste is $4.$ Dus, zonder rekening te houden met de $k_j$’s, komt ze op $4 + 13 \times 5 = 69.$ Maar dan zijn er twee waarden, $z_1$ en $z_2$ gepasseerd. Dus het getal dat ze noemt is $69 + 2 = 71.$

Met een beetje oefening kunnen Boris en Annika dus grote indruk maken op Isa en de overige vriendinnen en vrienden.