Een paar jaar geleden verscheen het boek Maths isn’t just for textbooks. Een van de artikelen ging over een wiskundige kaarttruc. De goochelaar toont het publiek een volledig spel kaarten (52 stuks). Iemand uit het publiek mag een opeenvolgende reeks van zes kaarten uit de stapel trekken. Als diegene vervolgens de kleuren (niet ♥, ♣, ♦ en ♠, maar enkel rood en zwart) van deze kaarten in de juiste volgorde opnoemt, kan de goochelaar precies vertellen welke zes kaarten hij in zijn handen heeft.
De sleutel ligt in de ordening van de kaarten en – ook niet onbelangrijk – in het geheugen van de goochelaar. Het is zaak dat de goochelaar de 52 kaarten vooraf zodanig op een stapel legt, dat elk rijtje van zes achtereenvolgende kleuren (bijvoorbeeld rrzrzr of zrzzzr) hooguit één keer voorkomt in de reeks van 52 kaarten. Een goochelaar met een feilloos geheugen (hij moet de volgorde van de 52 kaarten van buiten kennen) kan vervolgens precies vertellen om welke zes kaarten het gaat; het opgenoemde kleurenrijtje komt immers maar één keer voor in de hele reeks.
Dat het überhaupt mogelijk is om de 52 kaarten zodanig neer te leggen dat elk rijtje van zes kleuren niet vaker dan één keer voorkomt, bewees de Nederlandse wiskundige N.G. de Bruijn.
De Bruijn-rijen
De Nederlandse wiskundige N.G. de Bruijn werd geboren in 1918. Hij heeft baanbrekend werk gedaan over de volle breedte van de wiskunde, onder meer in de combinatoriek: de theorie van het tellen. In zijn vakgebied werd hij onder meer beroemd met een speciale soort rijen, die inmiddels zijn naam dragen: De Bruijn-rijen.
Stel je daar een ‘alfabet’ bij voor dat bestaat uit k karakters. Een De Bruijn-rij is een cyclische rij waarin elk deelrijtje van lengte n precies één keer voorkomt. Stel dat het alfabet uit twee karakters bestaat: 0 en 1. Dan zijn er twee De Bruijn-rijen waarin elk deelrijtje van lengte 3 precies één keer voorkomt, namelijk 00010111 en 11101000. Het deelrijtje 110 komt ook voor in de eerstgenoemde rij: de laatste twee enen en de eerste nul (vandaar dat we van een cyclische rij spreken). Het aantal De Bruijn-rijen met deelrijtjes van lengte 5 is maar liefst 2048.
In het algemeen geldt dat het aantal De Bruijn-rijen met deelrijtjes van lengte n en een alfabet ter grootte k gelijk is aan k!a/kn, waarbij a = kn-1; de lengte van elke rij is kn.
Datacompressie
Travis Gagie is een wiskundige aan de universiteit van Chili in Santiago. De kaarttruc bracht Gagie op het idee om de achterliggende theorie te gebruiken bij datacompressie.
Gagie paste de kaarttruc een beetje aan: de goochelaar ordent het pak kaarten niet van tevoren en laat iemand uit het publiek – nadat die eventueel het pak zelf nog eens geschud heeft – zeven achtereenvolgende kaarten trekken. Deze noemt de zeven kleuren en stopt de kaarten vervolgens weer terug in het pak kaarten. De goochelaar bekijkt het pak kaarten en zegt vervolgens om welke kaarten het ging.
Bij deze ‘truc’ moet je wel een beetje geluk hebben: de kans dat twee rijtjes van zeven kaarten dezelfde kleuren (in dezelfde volgorde) hebben, is ten hoogste 1 op 128; er is dus een kleine kans dat de goochelaar moet gokken.
Gagie vond uit dat deze bovengrens van 1 op 128 (of in het algemeen, bij k kleuren en rijtjes van lengte n: 1 op kn) een belangrijke rol speelt bij de zogeheten entropie van Markovbronnen. Entropie is oorspronkelijk een begrip uit de thermodynamica, maar heeft tegenwoordig ook betekenis in de informatietheorie; het is een maat voor de hoeveelheid wanorde in een of ander systeem.
Met Gagie’s ontdekking moet het in de toekomst mogelijk zijn om computerbestanden nog verder te comprimeren. Een speelfilm comprimeren tot 1 megabyte zal niet lukken: er zit nou eenmaal een theoretische ondergrens aan een compressiefactor. Maar elke afname van de bestandsgrootte is meegenomen, ook als het maar om een klein beetje gaat.
Het artikel van Travis Gagie is hier te downloaden in pdf-formaat. Het is niet lang, maar wel technisch!