Le Rubik's Cube est l'un des puzzles préférés au monde depuis 40 ans. Plusieurs méthodes différentes ont été conçues pour le résoudre, comme expliqué dans d'innombrables livres. Les "speedcubers" experts peuvent le résoudre en quelques secondes.

En plus de tels exploits d'une dextérité étonnante, il existe de nombreuses questions mathématiques fascinantes liées au Rubik's Cube. Un déplacement du cube consiste à faire pivoter l'une des six faces de 90, 180, ou 270 degrés. Un 43 stupéfiant, 252, 003, 274, 489, 856, 000 états possibles peuvent être obtenus en appliquant des séquences de mouvements à l'état résolu.

Malgré cette complexité, il a été démontré en 2010 que le Rubik's Cube peut toujours être résolu en 20 mouvements ou moins, quel que soit l'état initial. Ce nombre est appelé « nombre de Dieu, " car toutes les méthodes de résolution connues utilisées par les humains utilisent généralement beaucoup plus de mouvements que cette valeur optimale.

Mais qu'en est-il de la question inverse :combien de coups sont nécessaires pour brouiller un cube résolu ? A première vue, cela semble être une question beaucoup plus facile que de calculer le nombre de Dieu. Après tout, contrairement à la résolution d'un cube, brouiller un ne demande aucune compétence.

Des questions similaires ont été répondues avec succès pour le brassage de cartes. Un exemple célèbre est l'étude de 1990 du « riffle shuffle » par les mathématiciens Dave Bayer et Perci Diaconis. Un jeu de cartes est défini comme "mixte" si son ordre est aléatoire, avec chaque ordre possible ayant la même probabilité d'apparaître. Bayer et Diaconis ont montré que sept riffles shuffles sont nécessaires et suffisants pour mélanger approximativement un jeu standard de cartes à jouer.

L'année dernière, mathématiciens ont publié une étude similaire du puzzle 15, qui se compose d'un carré 4x4 rempli de 15 tuiles coulissantes et d'un espace vide.

Qu'est-ce que cela signifie pour un cube d'être brouillé ?

Une personne typique essayant de brouiller un Rubik's Cube effectuerait à plusieurs reprises des mouvements aléatoires dessus. La séquence aléatoire d'états qui en résulte est un cas particulier de ce que les mathématiciens appellent une chaîne de Markov. La propriété clé est que, étant donné l'état actuel, la probabilité de ce que sera le prochain état ne dépend d'aucun des états précédents.

Application de la théorie des chaînes de Markov au brouillage cubique, il s'ensuit que lorsque le nombre de mouvements aléatoires augmente, la probabilité d'être dans l'un quelconque des états possibles devient de plus en plus proche de 1/43, 252, 003, 274, 489, 856, 000. Les mathématiciens appellent cela une "distribution de probabilité uniforme, " car chaque état possible se produit avec la même probabilité.

Après un nombre donné de mouvements aléatoires, l'état du cube sera aléatoire, mais sa distribution de probabilité ne sera pas exactement uniforme; certains états seront plus susceptibles de se produire que d'autres.

Laisser d(t) décrire de combien la distribution de probabilité après t les mouvements aléatoires diffèrent de la distribution de probabilité uniforme. Comme le nombre de mouvements aléatoires ( t ) augmente, la valeur de d(t) diminuera. Le cube brouillé correspond à d(t) étant petit.

Chaîne de Markov Monte Carlo

Dans la théorie des chaînes de Markov, cette baisse de d(t) est appelé "mélange". Outre le brassage des cartes et le brouillage des puzzles, la théorie du mélange de chaînes de Markov a également des applications pratiques très sérieuses. L'un des outils de calcul les plus importants de la science et de l'ingénierie modernes est la méthode de Monte Carlo. Cette méthode, comme le célèbre casino dont il tire son nom, repose fondamentalement sur le hasard. En substance, il tente de résoudre approximativement des problèmes mathématiques difficiles en utilisant plusieurs suppositions aléatoires.

En pratique, Les chaînes de Markov sont souvent utilisées pour produire ces états aléatoires. Pour comprendre la précision de ces méthodes de Monte Carlo à chaîne de Markov, la tâche principale est d'estimer à quelle vitesse d(t) diminue à mesure que t augmente.

Le cube de poche

L'étude du problème de brouillage pour le Rubik's Cube 3x3x3 standard est actuellement un défi fascinant et non résolu. Cependant, cela devient tout à fait gérable si nous tournons notre attention vers une version 2x2x2 plus petite, appelé le cube de poche.

Dans ce cube, les pièces de bord et de centre sont absentes et seules les pièces d'angle restent. Le cube de poche n'en a que 3, 674, 160 états possibles, et son nombre de Dieu n'est que de 11.

Dans le graphique ci-dessous, nous traçons d(t) pour le cube de poche. Après 11 déplacements, d(t) est encore très grand, à 0,695. La première valeur de t qui donne un d(t) la valeur inférieure à 0,25 (souvent appelée "le temps de mélange" dans la théorie des chaînes de Markov) est de 19. Après 25 coups d(t) est de 0,092 ; après 50 coups, c'est 0,0012; et après 100 coups, c'est 0,00000017.

Alors, combien de mouvements devez-vous utiliser pour brouiller complètement un cube de poche ? La réponse dépend de la taille que vous souhaitez d(t) être. Cependant, il est certainement vrai que le nombre de mouvements de Dieu est insuffisant. Au strict minimum, il ne faut pas utiliser moins de 19 coups. Plus de détails, y compris le code pour calculer d(t) , sont disponibles ici.

Et bien sûr, une fois que vous avez brouillé votre cube, il ne reste plus qu'à le résoudre à nouveau.

Cet article est republié à partir de The Conversation sous une licence Creative Commons. Lire l'article original.