Card Trick mène à une nouvelle limite sur la compression de données

Voici un tour de cartes pour impressionner vos amis. Donnez un jeu de cartes à un ami et demandez-lui de couper le jeu, de tirer six cartes et de lister leurs couleurs. Vous nommez alors immédiatement les cartes qui ont été tirées.

La magie? Pas assez. Au lieu de cela, c'est la meilleure chose suivante : les mathématiques. La clé est d'organiser le jeu à l'avance de manière à ce que la séquence des couleurs des cartes suive un modèle spécifique appelé cycle binaire de De Bruijn. Une séquence de De Bruijn est un ensemble d'un alphabet dans lequel chaque sous-séquence possible apparaît exactement une fois.

Ainsi, lorsqu'un jeu de cartes répond à ce critère, il définit de manière unique toute séquence de six cartes consécutives. Tout ce que vous avez à faire pour effectuer le tour est de mémoriser les séquences.

Habituellement, ce genre d'astuces est le résultat d'un nouveau développement de la pensée mathématique. Aujourd'hui, Travis Gagie de l'Université du Chili à Santiago renverse la situation. Il dit que cette astuce l'a conduit à une nouvelle limite mathématique sur la compression de données

Gagie atteint cette nouvelle limite en envisageant une astuce connexe. Au lieu de pré-organiser les cartes, vous mélangez le paquet et demandez ensuite à votre ami de piocher sept cartes. Il liste ensuite les couleurs des cartes, les replace dans le paquet et coupe le paquet. Vous examinez ensuite le jeu et dites quelles cartes ont été tirées.

Cette fois, vous comptez sur la probabilité pour obtenir la bonne réponse. Il n'est pas difficile de montrer que la probabilité que deux septuples de cartes aient les mêmes couleurs dans le même ordre est d'au plus 1/128, disons Gagie.

Il examine ensuite la probabilité de prédire correctement la séquence de cartes tirées au hasard d'un jeu d'une certaine taille et après quelques étapes supplémentaires, trouve une limite inférieure sur la probabilité de le faire correctement.

Ceci s'avère être étroitement lié à divers problèmes de compression de données et conduit à une limite inférieure à celle trouvée par tout autre moyen.

Nous ne connaissons aucune limite inférieure antérieure comparable à [celle-ci], dit-il.

C'est impressionnant, un truc vraiment sympa en soi.

Réf : arxiv.org/abs/1011.4609 : Limites d'un tour de cartes

cacher