Rubik’s Cube : comment ses rotations engendrent-elles un groupe ?

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente. Vous pourriez mélanger à Rubik’s Cube une fois par seconde depuis la création de l'univers et vous n'auriez toujours pas vu toutes les combinaisons possibles. C'est

Intervenant 20:11

quand même dingue.

Intervenant 10:13

Ah oui. Et pourtant, peu importe le chaos apparent de ces couleurs, il n'est jamais à plus de 20 mouvements d'être parfaitement résolu.

Intervenant 20:20

Jamais plus de vingt, oui.

Intervenant 10:21

C'est fou. Donc aujourd'hui, on fait une petite exploration au cœur d'un super article.

Intervenant 20:26

Ouais, l'article qui s'appelle le groupe de Rubik.

Intervenant 10:29

Exactement. Et le but aujourd'hui, c'est vraiment de décortiquer tout ça et de comprendre comment les mathématiques arrivent à dompter cet objet qui a frustré tant de monde.

Intervenant 20:39

Moi, la première.

Intervenant 10:40

On y a tous passé des heures, mais c'est vraiment le grand paradoxe du Rubik’s Cube. Ça donne cette illusion d'un infini vertigineux, alors qu'en fait, c'est un problème mathématique très, très encadré.

Intervenant 20:51

Voilà, c'est plutôt comme une serrure à combinaison mécanique. Sauf que, au lieu de faire tourner des molettes chacune de leur côté, chaque rotation que tu fais modifie instantanément l'état des autres faces.

Intervenant 11:02

Et c'est cette interconnection qui rend le truc si complexe. L'article est super précis là-dessus d'ailleurs. Il nous donne les chiffres exacts. Si on prend les huit coins et les douze arêtes du cube...

Intervenant 21:11

Oui, on rentre dans les calculs de factoriel là.

Intervenant 11:14

C'est ça. Sans donner la formule complète, on arrive à un chiffre brut qui est juste gigantesque. 43 milliards, 2 milliards de combinaisons. C'est énorme. Mais l'auteur précise qu'on doit diviser ce résultat par 4 pour des raisons mécaniques.

Intervenant 21:27

Reverser l'orientation d'une seule arête, par exemple.

Intervenant 11:30

Ah, à moins de forcer et de casser la pièce, quoi.

Intervenant 21:32

Exactement. Tu ne peux pas non plus échanger juste deux coins. Chaque mouvement qu'on va appeler légal préserve une certaine parité mathématique. Donc cet axe central impose des limites strictes. Le chaos est encadré en fait.

Intervenant 11:45

D'accord, je vois. Et c'est là qu'on en arrive au concept clé de notre source, ce fameux groupe de Rubik.

Intervenant 21:51

C'est ça.

Intervenant 11:52

C'est un terme un peu austère, mais en gros, l'idée, c'est que les six rotations de base, donc les faces avant, arrière, haut, bas, droite et gauche, elles génèrent une structure. C'est un peu comme une immense carte GPS, non ?

Intervenant 22:03

C'est une super bonne métaphore. Imagine que chaque position du cube, c'est une adresse unique dans une ville géante de 43 milliards de milliards d'habitants.

Intervenant 12:12

Ça fait une sacrée métropole.

Intervenant 22:14

Un peu trop, oui. Et les rotations, ce sont les seules rues à sens unique qui connectent ces adresses entre elles.

Intervenant 12:20

Le groupe de Rubik, c'est ce qui prouve que cette ville est un espace clos.

Intervenant 22:23

Ok, donc on n'est jamais vraiment perdu. Il y a toujours un itinéraire précis pour rentrer à la maison, donc pour revenir au cube résolu.

Intervenant 12:31

Exactement.

Intervenant 22:32

Et c'est là que ça devient vraiment intéressant. Parce que si cet univers est structuré, à quelle vitesse est-ce qu'on peut le traverser ?

Intervenant 12:39

À la fameuse course contre la montre. Ben oui, l'article cite des recours fous. L'Australien Felix Zemdegs était à 4,59 secondes. Mais en novembre 2018, le Chinois Yu Shengdu a descendu ça à 3,47 secondes. 3 secondes

Intervenant 22:52

et demie, c'est incroyable !

Intervenant 12:54

Mais je me demande, est-ce que c'est la limite physique de ce qui est humainement possible ? Parce que quand on voit ce que fait la machine…

Intervenant 22:59

Ah oui, là la machine joue carrément dans une autre ligue. En 2018 toujours, un robot du MIT a résolu le cube en 0,38

Intervenant 13:07

secondes. 0,38 ? C'est absurde, on a à peine le temps de cligner des yeux !

Intervenant 23:12

C'est ça. Mais le truc, c'est qu'il utilisait le logiciel d'un informaticien allemand, Herbert Kosiemba. Et ce logiciel, il ne cherche pas au hasard, il a la carte entière du groupe de Rubik. Il trouve le raccourci parfait tout de suite.

Intervenant 13:25

D'ailleurs, l'article rappelle qu'un robot de passionné manipulait déjà le cube au Salon de la Culture et des Jeux Mathématiques à Paris en 2016. Donc, l'alliance entre algorithme et mécanique, ça fascine depuis un moment.

Intervenant 23:38

Oui, c'est clair. Et l'algorithme de Koscienba, il est vraiment central pour la suite.

Intervenant 13:43

Oui, ce qui nous amène à la question ultime du papier. Au-delà de la vitesse physique, quelle est l'efficacité mathématique absolue ? Le truc qu'on appelle le nombre de dieux.

Intervenant 23:53

Le nombre de dieux, oui. C'est un concept fascinant. C'est le nombre maximal de mouvements nécessaires pour résoudre n'importe quelle position du cube.

Intervenant 14:02

Juste pour être sûr, qu'est-ce qu'on compte exactement comme un mouvement ?

Intervenant 24:05

Bonne question. Dans la définition du base, un mouvement, c'est un quart de tour ou un demi-tour d'une face. Et c'est en 2010 que Thomas Rokiki, aidé par Kossiamba justement, et par les cerdoirs de Google, a prouvé que ce nombre est exactement de 20.

Intervenant 14:21

20. Alors que la moyenne de résolution est de 17,7 mouvements, si je me souviens bien de l'article.

Intervenant 24:26

Voilà. Et si on applique une règle plus stricte, de 2014, qui dit qu'un demi-tour compte pour deux mouvements de quart de tour, bah ce nombre monte à 26.

Intervenant 14:36

Mais attends, quand tu dis qu'ils ont utilisé des serveurs de Google, ils n'ont pas bêtement fait tester aux ordinateurs les 43 milliards de milliards de trajets pour trouver le plus long ?

Intervenant 24:46

Ah non, pas du tout. Même avec Google, la force brute aurait pris des années. Le vrai coup de génie, ça a été d'utiliser la symétrie.

Intervenant 14:53

C'est-à-dire ?

Intervenant 24:54

Bah si tu prends un cube mélangé et que tu le tournes dans tes mains pour regarder une autre face, le casse-tête reste exactement le même, c'est juste l'orientation qui change.

Intervenant 15:02

Ah oui, ok.

Intervenant 25:03

Donc en exploitant toutes ces symétries, ils ont pu regrouper des millions de combinaisons en un seul calcul.

Intervenant 15:09

Donc la solution c'était de réduire intelligemment la taille de la carte GPS.

Intervenant 25:15

C'est tout à fait ça.

Intervenant 15:16

C'est brillant. Les mathématiques arrivaient à rendre lisible le truc qui a l'air totalement chaotique.

Intervenant 25:20

C'est la beauté de la chose. Quel que soit l'état de ton vieux cube sur l'étagère, il n'est jamais à plus de 20 mouvements de l'ordre parfait.

Intervenant 15:26

Et ça, ça m'amène à une dernière pensée, assez vertigineuse d'ailleurs.

Intervenant 25:29

Ah, dis-moi !

Intervenant 15:30

Si les ordinateurs de Google, avec toutes ces astuces de symétrie, ont mis des semaines en 2010 pour trouver ce nombre de dieux sur un simple cube de 3x3, imagine un peu les limites informatiques et conceptuelles qu'il faudrait repousser pour trouver le nombre de dieux d'un cube 4x4 ou même d'un 5x5.

Intervenant 25:47

Ouf, ça donne le vertige rien que d'y penser.

Intervenant 15:50

Une petite réflexion à garder en tête la prochaine fois que vous croiserez un de ces casse-têtes. Merci de nous avoir rejoints pour cette analyse et à très bientôt.