La tâche du puzzle «tag» est d'organiser les tuiles numérotées. Aujourd'hui, les mathématiciens ont résolu le problème inverse - comment mélanger le puzzle.Vous avez probablement joué au tag. C'est un jeu frustrant mais addictif composé de 15 tuiles et d'un espace vide, disposées dans une grille 4 x 4. La tâche consiste à déplacer les tuiles et à les disposer par ordre croissant de nombres ou, dans certaines versions, à assembler une image à partir de celles-ci.
Après son apparition dans les années 1870, il est entré dans l'ensemble de jeux standard. De plus, il a attiré l'attention des mathématiciens qui étudient des puzzles de différentes tailles et configurations initiales depuis plus d'un siècle.
Aujourd'hui,
il existe de nouvelles preuves d'une solution au «jeu à 15» , mais dans l'ordre inverse. Les mathématiciens Yoon Chu et
Robert Howe de l'Université de Stony Brook ont déterminé le nombre de mouvements nécessaires pour transformer un champ ordonné en champ aléatoire.
Percy Deaconess a proposé une version du problème du «tag» avec randomisation en 1988. Il a suggéré que les puzzles aléatoires de n'importe quelle taille nécessitaient environ
3 mouvements. C'est-à-dire que pour un champ de 4 x 4, 4
3 ou 64 mouvements seront nécessaires et pour un champ de 10 x 10, 10
3 ou 1 000 mouvements. (Bien qu'ils soient toujours appelés «quinze», les champs peuvent avoir un nombre quelconque d'espaces qui composent le carré correct.)
Le mathématicien de l'Université de Stanford, Deaconess, a suggéré que sa version du problème des «15 jeux» est représentative d'une large classe de problèmes de randomisation similaires. Beaucoup de ces tâches sont liées aux caractéristiques fondamentales de la nature, par exemple, au changement de lieux des paires de bases d'ADN qui provoquent une mutation génétique, et à la façon dont les molécules sont séparées les unes des autres et deviennent désordonnées - cela se produit lorsque la glace fond.
La diaconesse espérait qu'ayant compris le problème de l'enchevêtrement des «taches», nous pourrions comprendre comment les systèmes ordonnés dans leur ensemble se transforment en un état uniformément mixte.
Dans des situations comme le "tag", le caractère aléatoire se développe une étape à la fois. Imaginez un champ entièrement ordonné, avec une unité en haut à gauche et un espace vide en bas à droite. Nous déplaçons les tuiles de sorte que l'espace vide se déplace d'un carré dans l'une des quatre directions possibles: haut, bas, gauche ou droite. (Par souci d'élégance mathématique, Chu et Howe ont considéré un champ dont les bords sont reliés les uns aux autres dans un anneau, de sorte que les carreaux ne se coincent jamais dans les coins.) Faisons un choix aléatoire. Maintenant, le champ est dans une nouvelle configuration - pas tout à fait dans un ordre, mais pas loin de là. Répétez ce processus. Si vous continuez à déplacer la case vide, le champ s'éloignera de plus en plus de l'emplacement d'origine commandé.
Une caractéristique importante de ce processus est qu'à chaque étape, la configuration de champ suivante dépend uniquement de la configuration actuelle. Cela rappelle un jeu dans Monopoly: la probabilité de lancer des dés et de déplacer deux cases de Park Place à Boardwalk ne dépend pas des rouleaux qui nous ont conduits à la cage de Park Place.
Les Quinze Rampes rampent progressivement vers le trouble, une étape à la fois. De nombreux autres systèmes, comme la fonte des glaces, sont randomisés de la même manière. Les mathématiciens étudient ce phénomène à l'aide de modèles appelés «chaînes de Markov». Les chaînes de Markov sont un moyen formel d'étudier tout processus de randomisation dans lequel la configuration système suivante dépend uniquement de la configuration actuelle. Ils sont à la pointe d'une compréhension mathématique du hasard.
"Les chaînes de Markov sont dans le juste milieu - d'une part, nous pouvons encore les analyser, d'autre part, elles décrivent de nombreux phénomènes qui nous intéressent", explique le mathématicien Yuval Perez, qui a effectué d'importants travaux en théorie des probabilités.
Dans leur nouveau travail, Chu et Howe ont travaillé avec la randomisation de "tag" comme avec la chaîne de Markov. En particulier, ils ont considéré un ensemble de nombres appelé «matrice de transition» de la chaîne de Markov. La matrice de transition est un ensemble étendu de nombres qui détermine la probabilité qu'un «jeu à 15» passe d'une configuration à une autre si nous décidons de déplacer un espace vide de manière aléatoire.
La compréhension de la matrice de transition est la clé pour calculer le nombre de mouvements nécessaires pour randomiser ou mélanger un champ ordonné. En particulier, Chu et Hou se sont concentrés sur la définition de l'ensemble des nombres qui caractérisent la matrice de transition - des nombres appelés «valeurs propres».
«En collectant suffisamment d'informations sur les valeurs propres, nous pouvons obtenir des informations de mélange très précises», explique Howe.
La matrice de transition pour les «spots» contient une énorme quantité d'informations qui reflète des milliers de milliards de configurations différentes que même un petit champ de 4 x 4 peut créer. C'est plus d'informations que les mathématiciens ne peuvent traiter directement. Par conséquent, au lieu d'analyser la matrice de transition à chaque étape du chemin du champ vers la randomisation, Chu et Howe ont découvert comment caractériser le comportement moyen de la matrice de transition entière tout au long du voyage.
Leur approche est similaire à la façon dont vous pouvez découvrir où nous sommes le plus susceptibles de se retrouver sur le terrain du monopole après 1000 lancers de dés: vous pouvez réellement lancer les dés tant de fois, ou simplement prendre la moyenne de plusieurs lancers et les extrapoler.
En utilisant cette technique, Chu et Howe ont calculé les valeurs propres de la matrice de transition, qui leur ont indiqué combien de mouvements devaient être effectués pour randomiser les «taches». Ils ont même reçu deux réponses basées sur deux définitions différentes de l'aléatoire.
Tout d'abord, ils ont considéré un champ aléatoire, sur lequel chaque tuile avec une probabilité égale peut être dans n'importe quel carré du champ. Avec cette définition, ils ont constaté que pour randomiser un champ
n à
n, n 4 mouvements seraient nécessaires (soit 256 pas pour un champ 4 par 4 et 10000 pas pour un champ 10 par 10). C'est plus que ce que Diaconis avait prévu (comme nous nous en souvenons, il a suggéré
n 3 étapes).
La deuxième définition du hasard par Chu et Hou était plus stricte. Ils ont considéré un champ randomisé qui, avec une probabilité égale, pourrait se trouver dans l'une de ses nombreuses configurations possibles. Ils ont prouvé qu'un peu plus d'étapes seraient nécessaires pour parvenir à une telle définition de l'aléatoire - pas plus d'environ
n 4 log
n mouvements.
Chu et Howe ont démontré que la randomisation du «jeu de 15» est plus difficile que prévu par Diaconis; dans un certain sens, cela suggère qu'il faut plus de temps que prévu pour éliminer complètement l'ordre dans le système. Grâce à leur travail, le «tag» est devenu l'une des rares tâches de randomisation dans lesquelles, selon Howe, «en fait, le nombre d'étapes nécessaires à la randomisation est connu».
Howe et Perez travaillent actuellement à l'élargissement des preuves. Entre autres choses, ils souhaitent savoir si le champ atteint un état aléatoire avec une taille croissante par un saut brutal. Les systèmes avec ce comportement ne semblent pas du tout aléatoires, et après une seule étape, ils se révèlent soudainement être ainsi.
"Nous ne comprenons pas parfaitement quelles chaînes de Markov font preuve d'une telle soudaineté", explique Perez. "C'est l'un des plus grands mystères dans ce domaine."