CultureMATH - accueil - contact


Le Rubik's cube, Groupe de poche


         Pierre Colmez

       École Polytechnique - CNRS - e-mail
Article déposé le 17 mai 2010. Toute reproduction pour publication ou à des fins commerciales, de la totalité ou d'une partie de l'article, devra impérativement faire l'objet d'un accord préalable avec l'éditeur (ENS Ulm). Toute reproduction à des fins privées, ou strictement pédagogiques dans le cadre limité d'une formation, de la totalité ou d'une partie de l'article, est autorisée sous réserve de la mention explicite des références éditoriales de l'article. 

Version [pdf ]  (9 pages, 125 ko) 

  


SOMMAIRE




Le Rubik’s cube se compose de 27 = 33 petits cubes dont 7 sont fixes (le cube central et ceux se trouvant au centre des faces) et 20 sont mobiles (les 8 coins et les 12 bords ; on note X et Y respectivement les ensembles des coins et des bords). Un ingénieux système permet à chacune des tranches extérieures de tourner, et donc de mélanger les cubes mobiles, ce qui se voit physiquement puisque les faces extérieures des cubes mobiles sont colorées (une face extérieure reste à l’extérieur au cours de ces mouvements). Résoudre le Rubik’s cube signifie le ramener dans l’état, dit initial, où chacune des faces est monocolore. Nous allons expliquer pourquoi, si on démonte un Rubik’s cube et qu’on le remonte au hasard, on a une chance sur 12 de pouvoir le résoudre. Ceci va demander de transformer le Rubik’s cube en un groupe [1].


1. Le groupe de Rubik


On note E l’ensemble des états possibles du cube. Cet ensemble est le produit de l’ensemble EX des états des coins par celui EY des états des bords. Comme il y a 8 coins que l’on peut permuter comme on veut, et que chaque coin peut être mis, une fois sa place choisie, dans 3 positions différentes (il faut que les faces extérieures soient apparentes), on a |EX| = 8! · 38. De même, les 12 bords peuvent être permutés comme on veut et chacun peut être retourné, une fois son emplacement choisi ; on a donc |EY| = 12! · 212, et |E| = 12! · 8! · 38 · 212 = 229 · 315 · 53 · 72 · 11.
Maintenant, il y a un groupe G qui agit naturellement sur E; c’est le groupe des mélanges du Rubik’s cube, décrit plus explicitement ci-dessous (on se permet de démonter le Rubik’s cube et de le reconstruire, faces colorées à l’extérieur). Il y a une bijection naturelle de G sur E, qui consiste à faire agir g ∈ G sur l’état initial du Rubik’s cube [2], mais il est important de faire la distinction [3] entre G et E pour comprendre en quel sens le Rubik’s cube est un groupe.
     On note Rub le groupe de Rubik qui est le sous-groupe de G engendré par les 6 rotations des tranches (c’est donc le sous-groupe des mélanges du cube que l’on peut obtenir sans casser le cube). L’énoncé que l’on cherche à démontrer se traduit alors par l’énoncé suivant, qui est un pur énoncé de théorie des groupes.


Théorème 1. — Le sous-groupe Rub est d’indice 12 dans G.


Ce résultat est une conséquence d’une description (cf. théorème 5) plus précise de Rub comme sous-groupe de G. Comme on connaît le cardinal de G, on peut en déduire celui de Rub qui n’est autre
que le nombre d’états du cube que l’on peut atteindre par une suite de rotations des tranches (vu la taille de ce nombre, il est difficile d’espérer pouvoir résoudre le Rubik’s cube en s’en remettant au pur hasard).

Corollaire 2. — |Rub| = (1/12) · 12! · 8! · 212 · 38 = 43 252 003 274 489 856 000.
 

2. Dévissage du groupe des mélanges


• Séparation des bords et des coins.— Comme on ne peut pas échanger un coin et un bord, et qu’on peut mélanger les coins et les bords totalement indépendamment, le groupe G est le produit direct GX × GY du groupe GX des mélanges des coins et du groupe GY des mélanges des bords. On peut donc écrire tout élément g de G sous la forme g = (πX(g), πY(g)), où πX(g) ∈ GX et πY(g) ∈ GY ; de plus πX : G → GX et πY : G → GY sont des morphismes de groupes. Les groupes GX et GY sont les sous-groupes de G laissant fixes Y et X respectivement ; ce sont aussi les noyaux respectifs de πY et πX .

• Le groupe des mélanges de coins.— Ne regarder que les emplacements des coins sans tenir compte de leurs orientations fournit un morphisme naturel de groupes g → σX(g) de GX dans le groupe des permutations PermX de l’ensemble X des coins. Ce morphisme est surjectif car tous les coins sont physiquement identiques ; le noyau de ce morphisme est le groupe RotX des rotations des coins, qui est isomorphe [4] à (Z/3Z)X. On peut aussi voir PermX comme un sous-groupe de GX en privilégiant une des faces visibles de x, pour tout x ∈ X : si σ ∈ PermX, alors σ envoie le cube se trouvant dans le coin x sur le cube x' = σ(x), la face privilégiée de x étant apposée sur la face privilégiée de x'. On peut alors écrire tout élément g de GX, de manière unique, sous la forme g = ρσ, où ρ ∈ RotX et σ ∈ PermX, ce qui traduit le fait qu’un mélange des coins peut se décomposer en une permutation des coins (envoyant les faces privilégiées sur les faces privilégiées), suivi d’une rotation des coins.

 On fera attention que les groupes  RotX et PermX ne commutent pas : si ρ = (nx) x ∈ X et si σ ∈ PermX, alors σρσ−1 est la rotation (n'x)x ∈ X , avec n' = nσ(x). Le groupe GX n’est donc pas le produit direct [5] des groupes RotX et PermX.
Si g = ρσ , où ρ = (nx)x ∈ X ∈ RotX et σ ∈ PermX, on définit la rotation totale rtX(g) de g par la formule  rtX(g) =∑ x ∈ X  nx ; c’est un élément de Z/3Z.



Lemme 3. — rtX : GX → Z/3Z est un morphisme de groupes.  (Voir Encart 1)


Le groupe des mélanges des bords.— On peut faire la même discussion avec les bords : on dispose d’un morphisme naturel de groupes g  → σX(g) de GY dans le groupe des permutations PermY de l’ensemble Y des bords. Ce morphisme est surjectif et son noyau est le groupe RotY des retournements des bords, qui est isomorphe à (Z/2Z)Y. On peut encore voir PermY comme un sous-groupe de GY en privilégiant une des faces visibles de m, pour tout y ∈ Y, ce qui permet d’écrire tout élément g de GY, de manière unique, sous la forme g = ρσ où ρ ∈ RotY et σ ∈ PermY. On définit la rotation totale rtY(g) de g ∈ GY par rtY(g) = ∑ y ∈ Y  ny  , si g = ρσ  avec ρ = (ny)y ∈ Y ∈ RotY et σ ∈ PermY . On obtient, comme ci-dessus, un morphisme de groupes rtY : GY → Z/2Z.

En fait, on peut montrer que le morphisme rtY  s'écrit de manière plus directe : on note F l’ensemble des faces visibles des bords (comme chaque bord a deux faces visibles, on a |F| = 2|Y| = 24). Le groupe GY permute les éléments de F, d’où un morphisme de groupe σF : GY → PermF.


Proposition 4. — Si g ∈ GY, alors (−1)rtY(g) est la signature de la permutation σF(g). (Voir Encart 2)



• Un invariant global.— On note ε le morphisme de G dans {±1} envoyant g ∈ G sur la signature de la permutation σX∪Y(g) induite sur les emplacements X∪Y du Rubik’s cube, en oubliant les orientations. Le groupe des permutations de X∪Y contient le produit de PermX et PermY, et σX∪Y(g) correspond à l’élément (σX o πX (g), σY o πY (g)) de ce produit ; on a donc aussi ε(g) = sign(σX o πX (g))sign(σX o πX (g)).




3. Le groupe de Rubik comme sous-groupe du groupe des mélanges


En combinant les trois morphismes de groupes définis ci-dessus, on obtient un morphisme de groupes rt : G → (Z/3Z) × (Z/2Z) × {±1}, avec rt(g) = (rtX o πX(g), rtY o πY(g), ε(g)).

Ce morphisme est surjectif de manière évidente ; son noyau H est donc d’indice 12 dans G, et le théorème 1 est donc une conséquence du résultat suivant.



Théorème 5. — On a Rub = H. Autrement dit, un élément g de G appartient à Rub si et seulement si πX(g) et πY(g) sont de rotation totale nulle, et si g induit une permutation paire sur les emplacements du cube.

Démonstration. — La démonstration de ce résultat comporte deux parties : la première (Proposition 6), assez plaisante, consiste à vérifier que tout élément de Rub vérifie les conditions ci-dessus, et la seconde (proposition 12), un peu plus pénible, demande de montrer que tout élément de G vérifiant les conditions du théorème peut s’écrire comme un produit de rotations de tranches du cube ; cela revient à décrire un algorithme de résolution [6] du Rubik’s cube.


Proposition 6. — Le groupe Rub est un sous-groupe de H.

Démonstration. — Comme H est l’intersection des noyaux de rtX o πX, rtY o πY et ε, et comme Rub est engendré par les rotations de tranche, il suffit, pour démontrer que Rub ⊂ H, de prouver que ces rotations de tranche appartiennent à ces noyaux. Soit donc g une rotation de tranche.

• D’après la Proposition. 4, le noyau de rtY est aussi l’ensemble des éléments de GY induisant une permutation de signature 1 sur l’ensemble F des faces des bords. Or g induit un produit de deux 4-cycles sur ces 24 faces, et donc est de signature 1. On en déduit l’appartenance de g au noyau rtY o πY.

• On peut décider que les faces privilégiées sont celles du dessus et du dessous du cube ; alors les rotations d’une tranche horizontale sont nulles en chaque coin, et donc la rotation totale est nulle. Si on fait tourner une tranche verticale, les quatre coins qui ne sont pas sur cette tranche ont une rotation nulle, et les quatre autres ont pour rotations 1, 2, 1 et 2, dont la somme est effectivement nulle dans Z/3Z. On en déduit, dans tous les cas, l’appartenance de g au noyau de rtX o πX.

• g induit un 4-cycle sur les coins et un 4-cycle sur les bords ; on a donc ε(g) = 1, ce qui prouve que g est dans le noyau de ε.

Ceci termine la démonstration de l’inclusion Rub ⊂ H.



4. Résolution du Rubik’s cube


L’algorithme décrit ci-dessous [7] consiste à :

• mettre les bords à leur place,
• les retourner 2 par 2 pour les orienter correctement,
• mettre les coins à leur place sans toucher aux bords,
• les retourner 2 par 2 pour les orienter correctement.

En réfléchissant un peu, on peut combiner les deux premières étapes et les deux dernières.

• Notations.— On note a, b, c, d, e et f  les faces du Rubik’s cube. Si r est une face, on note encore r la rotation d’un quart de tour de la tranche du cube correspondant à la face r (dans le sens des aiguilles d’une montre, l’axe étant orienté du centre du Rubik’s cube vers le centre de la face r). Par définition, Rub est le sous-groupe de G engendré par a, b, c, d, e, f, et si r est une face, alors r−1 est la rotation d’un quart de tour dans le sens trigonométrique de la tranche du cube correspondant à la face r.

Si r et s sont deux faces ayant un bord commun, on note ce bord yrs (ou ysr), et si r, s, t sont trois faces ayant un coin en commun, on note ce coin xrst (ou xstr ...).

On indexe les faces de telle sorte que (a, f), (b, e) et (c, d) forment des couples de faces opposées et que a envoye yab sur yac, et donc yac sur yae, yae sur yad et yad sur yab. Les 8 coins sont alors xabc, xace, xaed, xadb, xfcb, xfec, xfde et xfbd.


Notations des 6 faces, 8 coins et 12 bords





• Mise en place des bords.— La mise en place des bords utilise l’élément (a2b)5 de Rub et ses conjugués. Cet élément a pour vertu d’échanger yac et yad  en échangeant les faces a, et de laisser fixes les autres bords [8]. En particulier, son image dans PermY par σY o πY est la transposition des bords yac et yad. (Cf. Simulateur -  Mise en place des bords)

Par ailleurs, on vérifie facilement que si y et y' sont deux éléments distincts de Y, alors il existe g ∈ Rub envoyant yac sur y et yad sur y'. L’image de g(a2b)5g−1 par σY o πY est alors la transposition échangeant y et  y'. Il en résulte que σY o πY(Rub) contient toutes les transpositions, et comme celles-ci engendrent  PermY, cela démontre le résultat suivant. 


Lemme 7. — La composée σY o πY induit une surjection de Rub sur PermY.


• Orientation des bords.— La manipulation d2fbd −1 retourne yad et laisse fixe yac (cf. Simulateur - Orientations des bords); donc

                       h = (a2b)5(d2fbd −1)−1(a2b)5(d2fbd −1)

retourne yac et  yad sans toucher aux autres bords. Si y et y' sont deux éléments distincts de Y, et si g ∈ Rub envoie yac sur y et  yad  sur y', alors ghg−1 retourne y et y' sans toucher aux autres bords. Il s’ensuit que πY(Rub ∩ ker(σY o πY)) contient les retournements de deux bords quelconques, et comme ces éléments engendrent le sous-groupe Rot0Y de RotY des éléments de rotation totale nulle (un élément de Rot0Y est composé d’un nombre pair de retournements de bords), cela démontre le résultat suivant.


Lemme 8. — πY induit une surjection de Rub ∩ ker(σY o πY) sur Rot0Y.


• Mise en place des coins.— La mise en place des coins utilise l’élément (b−1a−1ba)3 de Rub. Cet élément a pour vertu de fixer les bords, et donc d’appartenir à Rub ∩ GX, et d’échanger les coins xabc et xfcb (en échangeant les faces a et f) ainsi que les coins xadb et  xdae (en échangeant les faces b et e), tout en laissant fixes les autres (cf. Simulateur - Mise en place des coins). En particulier, son image dans PermX est un produit de deux transpositions de supports disjoints.


Lemme 9. — L’image de Rub ∩ GX dans PermX est le sous-groupe AltX des permutations de signature 1.  (Voir Encart 3)


• Orientation des coins.— On note Rot0X le sous-groupe de RotX des éléments de rotation totale nulle (i.e. le noyau de  rtX). On a aussi Rot0X = H ∩  RotX, puisqu’un élément de RotX est déjà dans les noyaux de  rtY o πY et de ε.


Lemme 10. — On a Rot0Y ⊂ Rub.  (Voir Encart 4)


• L’inclusion  H ⊂ Rub.— Nous pouvons maintenant prouver le résultat suivant, ce qui termine la démonstration du théorème 5.


Proposition 12. — On a H ⊂ Rub.

Démonstration. — Commençons par remarquer que, Rub étant inclus dans H, le produit d’un élément de Rub et d’un élément de H donne un élément de H. Soit h ∈ H.

• Comme σY o πY induit (cf. lemme 7) une surjection de Rub sur PermY, il existe g1 ∈ Rub tel que σY o πY(g1) = σY o πY(h), et alors h1 = g1−1 h est un élément de H appartenant au noyau de σY o πY.

• D’après le lemme 8, il existe g2 ∈ Rub tel que πY(g2) = πY(h1)), et alors h2 = g2−1 h1 est un élément de H appartenant à GX.

• On a ε(h2) = 1, et comme h2 induit l’identité sur Y, la permutation σX(h2) appartient à AltX. D’après le lemme 9, ceci implique qu’il existe g3 ∈ Rub ∩ GX tel que σX(g3) = σX(h2), et alors g4 = g3−1 h2 est un élément de H ∩ RotX. Or H ∩ RotX = Rot0X est inclus dans Rub d’après le lemme 10 ; on a donc g4 ∈ Rub.

• Comme h = g1g2g3g4, on a h ∈ Rub, ce qui permet de conclure.




Bibliographie

Colmez, Pierre, Eléments d'analyse et d'algèbre (et de théorie des nombres), éditions de l'Ecole Polytechnique, 2009

Comment se jouer de la géométrie, coédition APMEP et éditions Vuibert, 2009

Dupas, Jean-Jacques, "Büvös Kocka ou la magie du cube hongrois", Tangente n° 129, Janvier - février 2009






Notes



[1] C’est un des rares groupes avec lequel on peut se promener dans la rue ; on peut en faire de même avec le groupe des tresses d’Artin, mais il a tendance à s’emmêler facilement.

[2] En fait, on aurait pu partir de n’importe quel état e, et obtenir une bijection g → g · e de G sur E; en résumé, on peut passer de n’importe quel état du cube à n’importe quel autre en faisant agir G, et ceci par l’action d’un unique élément de G; on dit que E est un espace principal homogène sous l’action de G. Une situation analogue est celle où E est un espace affine et G est l’espace vectoriel associé : le choix d’une origine O dans E définit une bijection v → O + v de G sur E, et on peut passer de n’importe quel point de E à n’importe quel autre point en translatant par un vecteur de G, et ceci de manière unique. De même, l’ensemble des bases d’un espace vectoriel de dimension n sur un corps K est un espace principal homogène sous l’action du groupe GLn(K).

[3] Ceci revient à faire la distinction entre les morceaux qui composent le cube et leurs positions : le groupe des mélanges agit sur les positions et g ∈ G envoie le morceau x se trouvant dans la position p sur la position g(p), indépendamment de la position de x dans l’état initial du cube.

[4] Si (nx)x ∈ X  est un élément de (Z/3Z)X, la rotation qui lui correspond fait tourner le coin x de nx tiers de tour (dans le sens des aiguilles d’une montre) autour de l’axe partant du centre du Rubik’s cube et passant par le coin du Rubik’s cube correspondant à x.

[5] C’est le produit semi-direct de RotX et PermX (cette situation est assez rare : en général, si φ: G → H est un morphisme surjectif de groupes, il est impossible de trouver un sous-groupe de G, isomorphe à H, s’envoyant bijectivement sur H par φ).

[6] L’algorithme qui en résulte n’est pas très efficace : on a vérifié, avec l’aide d’un ordinateur, qu’il est toujours possible de résoudre le Rubik’s cube en moins de 25 rotations de tranche. Son intérêt est plus théorique ; il permet d’illustrer l’effet de la conjugaison sur l’action d’un groupe sur un ensemble.

[7] Il est plus facile à suivre avec un Rubik’s cube en main, mais avec un peu de courage, un papier et crayon peuvent suffire (c’est quand même dommage de se priver de l’existence d’une version physique du groupe de Rubik). On pourra également utiliser le logiciel Arcus (simulateur du Rubik's cube).

[8] Le mouvement a2b bouge 7 bords, avec un cycle de longueur 5 et un de longueur 2 ; sa puissance 5-ième élimine donc le cycle de longueur 5, mais il est un peu miraculeux qu’elle ne retourne aucun élément de ce cycle.