Quel fantôme est-ce ? Quel monstre inouï ! Quelle matière hétéroclite ! Quelle force extraordinaire est la sienne ! Elle qui est haïe des sots, méprisée par les gueux, blâmée par les grossiers, vitupérée par les coquins, persécutée par les esprits bestiaux. Elle qui est aimée des sages, admirée par les savants, glorifiée par les grands, estimée par les puissants et favorisée des dieux. Citoyenne familière du monde, fille du père savoir et de la mère intuition, elle qui a mis la nature à nu, qui a franchi les airs, traversé le ciel, parcouru les étoiles…
Ci-dessous figurent quelques résultats qui, je l’espère, seraient dignes de votre curiosité ; néanmoins, je dois vous mettre en garde. Contrairement aux articles précédents, celui-ci n’est pas destiné aux néophytes, il y figure des résultats non triviaux et sûrement insuffisamment, voire nullement, justifiés.
Les mathématiques du Rubik’s Cube
La théorie des groupes, célèbre branche des mathématiques, est souvent décriée pour son manque d’applications ou bien d’utilité dans le monde réel, mais si l’on arrive à s’accrocher au-delà des notations et des subtilités, on y trouve une manière étonnamment simple et rigoureuse pour décrire des objets complexes.
Dans ce chapitre, nous allons exprimer les rotations possibles d’un Rubik’s Cube dans le langage de la théorie des groupes. Pour ce faire, nous devons introduire une notation bien spécifique avec plusieurs éléments :
- Le groupe des classes d’équivalence d’entiers pour la relation de congruence modulo n, généralement noté Z/Zn, sera noté Zn
- Le groupe symétrique, correspondant à toute application bijective possible sur un ensemble fini de n éléments vers lui-même, typiquement noté Sn
- On note les 6 rotations possible d’un Rubik’s cube comme le nom de la face par laquelle on le tourne, toujours dans le sens des aiguilles d’une montre. Soit : U, D, R, L, F et B pour respectivement “Up, Down, Right, Left, Front, Back”.
- L’application “signature” caractérisant le nombre d’inversions dans une application est notée sgn(•).
- Et finalement, on notera les mouvements possibles d’un Rubik’s cube comme les éléments de G et les mouvements “étendu” où l’on peut s’autoriser à déformer le cube comme bon nous sembles H.
Pour commencer, il faut considérer le Rubik’s Cube tel on le ferait pour un cube, c’est à dire qu’on y trouve 8 sommets, 12 arêtes et 6 faces. La particularité étant qu’à chaque coin sont assignés trois facettes distinctes et de même, à chaque arête, sont associée deux facettes distinctes.
De par ce constat, on peut affirmer que chaque position d’un Rubik’s Cube peut être distinguée en deux parties, l’une décrivant l’état de chaque sommet et de leurs facettes respectives, l’autre décrivant l’état de chaque arête et de leurs facettes respectives. Ainsi, on peut écrire :
Ici, on note la partie gauche par Hco et la partie droite par Har
La justification se fait étape par étape, premièrement au sujet des sommets :
Il faut distinguer les positions des sommets avec les positions de leurs facettes associées ; cette distinction permet de mieux comprendre la structure se cachant derrière. Pour exprimer cette distinction on considère le morphisme suivant :
Et donc le noyau de ce morphisme est un sous-groupe normal de Hco qui décrit les changements des facettes des sommets du Rubik’s Cube. D’ailleurs, pour un état des coins g, en posant v(g) comme l’états des facettes des coins de g, on peut observer :
Ce qui nous donne une forme de décomposition des éléments de Hco qui est unique, d’une part les changements des facettes (le produit entre ces deux éléments est bien la loi “composition” de S8 qui s’écrit par un petit cercle ou par rien du tout), et de l’autre les permutations des sommets, et maintenant on observe par cette même décomposition, pour deux éléments g et h de Hco :
Ce qui décrit une structure de produit semi-direct par l’action de normalisation de l’élément de permutation des sommets sur le groupe de changements des facettes (que l’on note N en indice sur l’opérateur de produit semi direct). Ici, il faut juste faire attention à la manière dont ces éléments agissent entre eux, v(g) représentant un élément de (Z3)8 il est possible d’y appliquer un élément de S8 par simple composition.
Un raisonnement assez similaire peut être déroulé. Pour les arêtes, on définit un autre morphisme décrivant uniquement les permutations possibles des arêtes, en ignorant donc les changements des facettes :
Et de la même manière, cela induit une décomposition, en les permutations des arêtes et les permutations des facettes des arêtes, pour un élément k de Har en posant w(k) comme les changements des facettes (soit ici un élément de (Z2)12 on obtient le même résultat et la même structure de produit semi direct avec surprise, la même action de groupe qui plus est :
Et donc pour deux éléments k et l de Har on a :
Maintenant que l’on a caractérisé le groupe Rubik’s cube “détendu”, on peut aussi caractériser les mouvements légaux que l’on peut faire sur de tels éléments, soit le groupe G. Et de cette manière, l’on nécessite trois conditions sur la décomposition vrwa (v, rho, w, alpha) d’un élément de G :
Cela revient par ailleurs au noyau d’un morphisme de groupe que l’on notera Ω, et donc c’est un sous-groupe normal de H. La première condition se constate par le fait que les seuls mouvements légaux transposent chacun deux fois quatre éléments par des 4-cycles (une fois quatre coins, et une fois quatre arêtes), la signature de la décomposition de chaque mouvement est donc nécessairement -1 ce qui donne que leurs produits sont 1.
Les deux autres conditions se vérifient à partir des 6 rotations générant tout état « légal » du Rubik’s Cube. Puisqu’elles vérifient ces conditions, et que tout état légal est généré par ces mouvements, cela permet de conclure. L’autre sens consistant à vérifier que ces mouvements sont bien légaux est assez implicite et revient à trouver une suite de mouvements permettant d’inverser un état « légal » du Rubik’s Cube ; plus de détails peuvent se trouver sur le Wikipédia mis en source.
À partir de tous ces résultats, on peut trouver le nombre de positions légales (soit le cardinal de G) d’un Rubik’s Cube à partir du premier théorème d’isomorphisme en théorie des groupes :
Adrien Mocaer
Sources :
Articles similaires :
Toujours des mathématiques
The Sports Gambling Epidemic
