211service.com
Korttrick fører til ny binding af datakomprimering
Her er et korttrick til at imponere dine venner. Giv et sæt kort til en ven, og bed ham eller hende om at skære i bunken, træk seks kort og angiv deres farver. Du navngiver derefter straks de kort, der er blevet trukket.
Magi? Ikke helt. I stedet er det den næstbedste ting: matematik. Nøglen er at arrangere bunken på forhånd, så sekvensen af kortfarverne følger et bestemt mønster kaldet en binær De Bruijn-cyklus. En De Bruijn-sekvens er et sæt fra et alfabet, hvor enhver mulig undersekvens optræder nøjagtigt én gang.
Så når et sæt kort opfylder disse kriterier, definerer det entydigt enhver sekvens af seks på hinanden følgende kort. Alt du skal gøre for at udføre tricket er at huske sekvenserne.
Normalt opstår denne slags tricks som et resultat af en ny udvikling inden for matematisk tænkning. I dag vender Travis Gagie fra University of Chile i Santiago sagen. Han siger, at dette trick har ført ham til en ny matematisk binding til datakomprimering
Gagie opnår denne nye binding ved at overveje et relateret trick. I stedet for at arrangere kortene på forhånd, blander du pakken og beder derefter din ven om at trække syv kort. Han eller hun lister derefter kortens farver, erstatter dem i pakken og skærer bunken. Du undersøger derefter bunken og siger, hvilke kort der blev trukket.
Denne gang er du afhængig af sandsynlighed for at få det rigtige svar. Det er ikke svært at vise, at sandsynligheden for, at to septupler kort har de samme farver i samme rækkefølge, højst er 1/128, siger Gagie.
Han fortsætter med at overveje sandsynligheden for korrekt at forudsige rækkefølgen af kort, der trækkes tilfældigt fra et spil af en vis størrelse, og efter et par ekstra trin finder han en nedre grænse for sandsynligheden for at gøre dette korrekt.
Dette viser sig at være tæt forbundet med forskellige problemer med datakomprimering og fører til en lavere grænse, end man har fundet på nogen anden måde.
Vi kender ingen tidligere nedre grænser, der kan sammenlignes med [denne], siger han.
Det er imponerende, et rigtig lækkert trick i sig selv.
Ref: arxiv.org/abs/1011.4609 : Grænser fra et korttrick