211service.com
Kaarttruc leidt tot nieuwe grens aan datacompressie
Hier is een kaarttruc om indruk te maken op je vrienden. Geef een pak kaarten aan een vriend en vraag hem of haar om de stapel uit te snijden, zes kaarten te trekken en hun kleuren op te noemen. Je noemt dan meteen de kaarten die getrokken zijn.
Magie? Niet helemaal. In plaats daarvan is het het op één na beste: wiskunde. De sleutel is om het kaartspel van tevoren zo te rangschikken dat de volgorde van de kaartkleuren een specifiek patroon volgt dat een binaire De Bruijn-cyclus wordt genoemd. Een De Bruijn-reeks is een verzameling uit een alfabet waarin elke mogelijke deelreeks precies één keer voorkomt.
Dus wanneer een pak kaarten aan deze criteria voldoet, definieert het op unieke wijze elke reeks van zes opeenvolgende kaarten. Het enige dat u hoeft te doen om de truc uit te voeren, is de reeksen te onthouden.
Meestal ontstaan dit soort trucs als het resultaat van een nieuwe ontwikkeling in het wiskundig denken. Vandaag draait Travis Gagie van de Universiteit van Chili in Santiago de rollen om. Hij zegt dat deze truc hem heeft geleid tot een nieuwe wiskundige grens op het gebied van datacompressie
Gagie bereikt deze nieuwe grens door een verwante truc te overwegen. In plaats van de kaarten vooraf te rangschikken, schud je het pak en vraag je je vriend om zeven kaarten te trekken. Hij of zij somt vervolgens de kleuren van de kaarten op, plaatst ze terug in het pak en snijdt de stapel uit. Vervolgens onderzoek je de stapel en zeg je welke kaarten er zijn getrokken.
Deze keer vertrouw je op waarschijnlijkheid om het juiste antwoord te krijgen. Het is niet moeilijk om aan te tonen dat de kans dat twee zevenvoudige kaarten dezelfde kleuren in dezelfde volgorde hebben, hoogstens 1/128 is, zeg Gagie.
Hij gaat verder met de waarschijnlijkheid van het correct voorspellen van de reeks kaarten die willekeurig uit een stapel van een bepaalde grootte worden getrokken en na een paar extra stappen vindt hij een ondergrens voor de kans om dit correct te doen.
Dit blijkt nauw verband te houden met verschillende problemen van datacompressie en leidt tot een ondergrens dan met andere middelen is gevonden.
We kennen geen eerdere ondergrenzen die vergelijkbaar zijn met [deze], zegt hij.
Dat is indrukwekkend, een heel leuke truc op zich.
Referentie: arxiv.org/abs/1011.4609 : Grenzen van een kaarttruc