Um truque de cartas inspira compressão de dados no computador

Um truque de cartas complicado relacionado às cores das cartas e um ciclo binário de De Bruijn ajudou um matemático a alcançar um novo limite em compressão de dados. Magia e matemática, mais unidas do que você pensa!

O truque não é novo, mas funciona assim: você dá um baralho de cartas a um amigo e pede para ele retirar seis cartas (na sequência) e dizer as cores. Com essa sequência de cores, você pode imediatamente nomear com exatidão as cartas que foram retiradas. Como? Porque cada sequência de cores é única, e só aparece uma vez no baralho (depois de ser previamente organizado para tanto), então se você tiver uma memória insana, você vai saber quais cartas correspondem à sequência.

De acordo com Travis Gagie, da Universidade do Chile em Santiago, o truque está bastante relacionado à compressão de dados:

Gagie alcançou este novo limite [matemático] considerando um truque relacionado. Em vez de pré-arranjar as cartas, você as mistura e então pede a seu amigo para retirar sete cartas. Ele então lista as cores das cartas, substitui-as e corta o baralho. Você então examina o baralho e diz quais cartas foram retiradas. Desta vez você está contando com probabilidades para obter a resposta certa. "Não é difícil mostrar que a probabilidade de dois sétuplos de cartas com a mesma cor, na mesma ordem, é no máximo de 1/128".

Isto parece estar bastante ligado a vários problemas de compressão de dados e leva a um limite mais baixo [de compressão] que eu encontrei de qualquer outra forma.

Mágicos como matemáticos, eu já devia saber. [Technology Review]