Est-ce difficile de brouiller le Rubik’s Cube?

Le Rubik’s Cube est l’un des puzzles préférés du 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 ces exploits d’une dextérité étonnante, il existe de nombreuses questions mathématiques fascinantes liées au Rubik’s Cube. Un mouvement du cube consiste à faire tourner l’une des six faces de 90, 180 ou 270 degrés. Un étourdissement de 43 252 003 274 489 856 000 états possibles peut être obtenu en appliquant des séquences de mouvements à l’état résolu.

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

Le Cube de Rubik à l’état résolu. Mike Gonzalez (TheCoffee)

Mais qu’en est-il de la question opposée: combien de mouvements sont nécessaires pour brouiller un cube résolu? À 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 cube 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, chaque ordre possible ayant la même probabilité d’apparaître. Bayer et Diaconis ont montré que sept brassages de riffles sont nécessaires et suffisants pour mélanger approximativement un jeu de cartes standard.

L’année dernière, des mathématiciens ont publié une étude similaire du puzzle 15, qui consiste en un carré 4×4 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 cube de Rubik effectuerait à plusieurs reprises des mouvements aléatoires dessus. La séquence aléatoire d’états résultante est un cas particulier de ce que les mathématiciens appellent une chaîne de Markov. La propriété clé est que, compte tenu de l’état actuel, la probabilité de ce que sera l’état suivant ne dépend d’aucun des états précédents.

En appliquant la théorie des chaînes de Markov au brouillage des cubes, il s’ensuit que, à mesure que le nombre de mouvements aléatoires augmente, la probabilité d’être dans l’un 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.

Laissez d(t) décrire dans quelle mesure la distribution de probabilité après t mouvements aléatoires diffère de la distribution de probabilité uniforme. À mesure que le nombre de mouvements aléatoires (t) augmente, la valeur de d(t) diminue. Le cube brouillé correspond à d(t) étant petit.

Monte-Carlo à chaîne de Markov

Dans la théorie des chaînes de Markov, cette diminution de d(t) est appelée « mélange”. Outre le brassage de cartes et le brouillage de casse-tête, la théorie du mélange de chaînes de Markov a également des applications pratiques très sérieuses. L’un des outils informatiques 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 d’après lequel elle porte 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 clé consiste à estimer la vitesse à laquelle d (t) diminue à mesure que t augmente.

Le cube de poche

Cube de poche dans un état brouillé. Mike Gonzalez (TheCoffee)

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

Dans ce cube, les arêtes et les pièces centrales sont absentes et il ne reste que les pièces d’angle. Le cube de poche n’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 mouvements, d(t) est toujours très grand, à 0,695. La première valeur de t qui donne une valeur d(t) inférieure à 0,25 (souvent appelée « temps de mélange” dans la théorie de la chaîne de Markov) est 19. Après 25 mouvements, d(t) vaut 0,092; après 50 mouvements, il vaut 0,0012; et après 100 mouvements, c’est 0,00000017.

Distance de la distribution du cube de poche de l’uniforme après t se déplace. Eric Zhou

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 que d (t) soit. 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.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *