Il trucco con le carte porta a un nuovo limite alla compressione dei dati

Ecco un trucco con le carte per impressionare i tuoi amici. Dai un mazzo di carte a un amico e chiedigli di tagliare il mazzo, pescare sei carte ed elencarne i colori. Quindi nomina immediatamente le carte che sono state pescate.

Magia? Non proprio. Invece, è la prossima cosa migliore: la matematica. La chiave è disporre il mazzo in anticipo in modo che la sequenza dei colori delle carte segua uno schema specifico chiamato ciclo binario di De Bruijn. Una sequenza di De Bruijn è un insieme di un alfabeto in cui ogni possibile sottosequenza appare esattamente una volta.

Quindi, quando un mazzo di carte soddisfa questo criterio, definisce in modo univoco qualsiasi sequenza di sei carte consecutive. Tutto quello che devi fare per eseguire il trucco è memorizzare le sequenze.

Di solito questi tipi di trucchi sono il risultato di qualche nuovo sviluppo nel pensiero matematico. Oggi, Travis Gagie dell'Università del Cile a Santiago capovolge la situazione. Dice che questo trucco lo ha portato a un nuovo limite matematico sulla compressione dei dati

Gagie raggiunge questo nuovo limite considerando un trucco correlato. Invece di disporre le carte in anticipo, mescoli il mazzo e poi chiedi al tuo amico di pescare sette carte. Quindi elenca i colori delle carte, le ripone nel mazzo e taglia il mazzo. Quindi esamini il mazzo e dici quali carte sono state pescate.

Questa volta ti affidi alla probabilità per ottenere la risposta giusta. Non è difficile dimostrare che la probabilità che due septupli di carte abbiano gli stessi colori nello stesso ordine è al massimo 1/128, diciamo Gagie.

Passa poi a considerare la probabilità di prevedere correttamente la sequenza di carte estratte a caso da un mazzo di una certa dimensione e dopo qualche passaggio in più, trova un limite inferiore alla probabilità di farlo correttamente.

Questo risulta essere strettamente correlato a vari problemi di compressione dei dati e porta a un limite inferiore rispetto a quanto riscontrato con qualsiasi altro mezzo.

Non conosciamo limiti inferiori precedenti paragonabili a [questo], dice.

È impressionante, un trucco davvero carino in sé.

Rif: arxiv.org/abs/1011.4609 : Limiti da un trucco con le carte

nascondere