Sztuczka z kartą prowadzi do nowego ograniczenia kompresji danych

Oto sztuczka karciana, która zaimponuje znajomym. Daj koledze talię kart i poproś go, aby przeciął talię, dobrał sześć kart i wymienił ich kolory. Następnie natychmiast wymieniasz karty, które zostały wylosowane.

Magia? Nie do końca. Zamiast tego jest to kolejna najlepsza rzecz: matematyka. Kluczem jest ułożenie talii z wyprzedzeniem, tak aby kolejność kolorów kart była zgodna z określonym wzorem zwanym binarnym cyklem De Bruijna. Sekwencja De Bruijna to zbiór alfabetu, w którym każdy możliwy podciąg występuje dokładnie raz.

Tak więc, gdy talia kart spełnia te kryteria, jednoznacznie definiuje dowolne sekwencje sześciu kolejnych kart. Wszystko, co musisz zrobić, aby wykonać trik, to zapamiętać sekwencje.

Zazwyczaj tego rodzaju sztuczki pojawiają się w wyniku nowych postępów w myśleniu matematycznym. Dziś sytuacja odwraca Travis Gagie z Uniwersytetu Chile w Santiago. Mówi, że ta sztuczka doprowadziła go do nowego matematycznego powiązania kompresji danych

Gagie osiąga tę nową więź, rozważając pokrewną sztuczkę. Zamiast wcześniej układać karty, tasujesz talię, a następnie prosisz znajomego o dobranie siedmiu kart. Następnie wymienia kolory kart, wymienia je w talii i przecina talię. Następnie sprawdzasz talię i mówisz, które karty zostały wylosowane.

Tym razem polegasz na prawdopodobieństwie, aby uzyskać właściwą odpowiedź. Nietrudno wykazać, że prawdopodobieństwo dwóch siódemek kart mających te same kolory w tej samej kolejności wynosi co najwyżej 1/128, powiedzmy Gagie.

Następnie rozważa prawdopodobieństwo poprawnego przewidzenia sekwencji losowych kart wyciągniętych z talii o określonym rozmiarze i po kilku dodatkowych krokach znajduje dolne ograniczenie prawdopodobieństwa wykonania tego poprawnie.

Okazuje się, że jest to ściśle związane z różnymi problemami kompresji danych i prowadzi do dolnej granicy, niż stwierdzono w jakikolwiek inny sposób.

Nie znamy poprzednich dolnych granic porównywalnych z [tym], mówi.

To imponujące, naprawdę fajna sztuczka sama w sobie.

Nr ref.: arxiv.org/abs/1011.4609 : Granice z karty sztuczki

ukryć