211service.com
Korttrick leder till ny gräns för datakomprimering
Här är ett korttrick för att imponera på dina vänner. Ge en kortlek till en kompis och be honom eller henne att klippa kortleken, dra sex kort och lista deras färger. Du namnger då direkt de kort som har dragits.
Magi? Inte riktigt. Istället är det det näst bästa: matematik. Nyckeln är att ordna kortleken i förväg så att sekvensen av kortfärgerna följer ett specifikt mönster som kallas en binär De Bruijn-cykel. En De Bruijn-sekvens är en uppsättning från ett alfabet där varje möjlig delsekvens förekommer exakt en gång.
Så när en kortlek uppfyller dessa kriterier, definierar den unikt alla sekvenser av sex på varandra följande kort. Allt du behöver göra för att utföra tricket är att memorera sekvenserna.
Vanligtvis kommer dessa typer av tricks till som ett resultat av någon ny utveckling inom matematiskt tänkande. Idag vänder Travis Gagie från University of Chile i Santiago på steken. Han säger att detta trick har lett honom till en ny matematisk gräns för datakomprimering
Gagie uppnår denna nya gräns genom att överväga ett relaterat trick. Istället för att förbereda korten blandar du paketet och ber sedan din vän att dra sju kort. Han eller hon listar sedan kortens färger, sätter tillbaka dem i förpackningen och klipper kortleken. Du undersöker sedan leken och säger vilka kort som drogs.
Den här gången förlitar du dig på sannolikhet för att få rätt svar. Det är inte svårt att visa att sannolikheten för att två septuplar av kort har samma färger i samma ordning är högst 1/128, säg Gagie.
Han fortsätter med att överväga sannolikheten att korrekt förutsäga sekvensen av kort som dras slumpmässigt från en kortlek av en viss storlek och efter några extra steg, hittar han en nedre gräns för sannolikheten att göra detta korrekt.
Detta visar sig vara nära relaterat till olika problem med datakomprimering och leder till en lägre gräns än vad som har hittats på något annat sätt.
Vi känner inte till några tidigare lägre gränser som kan jämföras med [denna], säger han.
Det är imponerande, ett riktigt snyggt trick i sig.
Ref: arxiv.org/abs/1011.4609 : Gränser från ett korttrick