Utilisation  en classe- Cet article illustre de façon originale la notion d’action de groupe opérant sur un ensemble. Le lecteur qui n’aurait pas manipulé cette notion depuis un certain temps  pourra trouver  les prérequis nécessaires sur CultureMATH dans l'article Intoduction à la théorie des groupes de Farouk Boucekkine et Thomas Chomette.
Ce texte n’est pas utilisable dans l’enseignement  secondaire  ;en revanche, les enseignants du supérieur trouveront dans cet article une façon originale pour aider leurs étudiants à maîtriser le vocabulaire d'action de groupes.

 

Pierre Colmez, École Polytechnique - CNRS - e-mail

---

---

Le Rubik’s cube se compose de 27 = 3³ 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 E_X des états des coins par celui E_Y 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 |E_X| = 8! · 3⁸. 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 |E_Y| = 12! · 2¹², et |E| = 12! · 8! · 3⁸ · 2¹² = 2²⁹ · 3¹⁵ · 5³ · 7² · 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! · 2¹² · 3⁸ = 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 G_X × G_Y du groupe G_X des mélanges des coins et du groupe G_Y 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) ∈ G_X et π_Y(g) ∈ G_Y ; de plus π_X : G → G_X et π_Y : G → G_Y sont des morphismes de groupes. Les groupes G_X et G_Y 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 G_X dans le groupe des permutations Perm_X 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 Rot_X des rotations des coins, qui est isomorphe [4] à (Z/3Z)^X. On peut aussi voir Perm_X comme un sous-groupe de G_X en privilégiant une des faces visibles de x, pour tout x ∈ X : si σ ∈ Perm_X, 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 G_X, de manière unique, sous la forme g = ρσ, où ρ ∈ Rot_X et σ ∈ Perm_X, 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  Rot_X et Perm_X ne commutent pas : si ρ = (n_x) _{x ∈ X} et si σ ∈ PermX, alors σρσ⁻¹ est la rotation (n'_x)_{x ∈ X} , avec n' = n_σ(x). Le groupe G_X n’est donc pas le produit direct [5] des groupes Rot_X et Perm_X.
Si g = ρσ , où ρ = (n_x)_{x ∈ X} ∈ Rot_X et σ ∈ Perm_X, on définit la rotation totale rt_X(g) de g par la formule  rt_X(g) =∑ _{x ∈ X}  n_x ; c’est un élément de Z/3Z.



Lemme 3. — rt_X : G_X → 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 G_Y dans le groupe des permutations Perm_Y de l’ensemble Y des bords. Ce morphisme est surjectif et son noyau est le groupe Rot_Y des retournements des bords, qui est isomorphe à (Z/2Z)^Y. On peut encore voir Perm_Y comme un sous-groupe de G_Y en privilégiant une des faces visibles de m, pour tout y ∈ Y, ce qui permet d’écrire tout élément g de G_Y, de manière unique, sous la forme g = ρσ où ρ ∈ Rot_Y et σ ∈ Perm_Y. On définit la rotation totale rt_Y(g) de g ∈ G_Y par rt_Y(g) = ∑ _{y ∈ Y}  n_y  , si g = ρσ  avec ρ = (n_y)_{y ∈ Y} ∈ Rot_Y et σ ∈ Perm_Y . On obtient, comme ci-dessus, un morphisme de groupes rt_Y : G_Y → Z/2Z.

En fait, on peut montrer que le morphisme rt_Y  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 G_Y permute les éléments de F, d’où un morphisme de groupe σ_F : G_Y → Perm_F.


Proposition 4. — Si g ∈ G_Y, alors (−1)^rt_Y(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 Perm_X et Perm_Y, 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) = (rt_X o π_X(g), rt_Y 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 rt_X o π_X, rt_Y 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 rt_Y est aussi l’ensemble des éléments de G_Y 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 rt_Y 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 rt_X 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⁻¹ 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 y_rs (ou y_sr), et si r, s, t sont trois faces ayant un coin en commun, on note ce coin x_rst (ou x_str ...).

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 y_ab sur y_ac, et donc y_ac sur y_ae, y_ae sur y_ad et y_ad sur y_ab. Les 8 coins sont alors x_abc, x_ace, x_aed, x_adb, x_fcb, x_fec, x_fde et x_fbd.

 

Notations des 6 faces, 8 coins et 12 bords

• Mise en place des bords.— La mise en place des bords utilise l’élément (a²b)⁵ de Rub et ses conjugués. Cet élément a pour vertu d’échanger y_ac et y_ad  en échangeant les faces a, et de laisser fixes les autres bords [8]. En particulier, son image dans Perm_Y par σ_Y o π_Y est la transposition des bords y_ac et y_ad. (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 y_ac sur y et y_ad sur y'. L’image de g(a²b)⁵g⁻¹ 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  Perm_Y, cela démontre le résultat suivant. 


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


• Orientation des bords.— La manipulation d²fbd ⁻¹ retourne y_ad et laisse fixe y_ac (cf. Simulateur - Orientations des bords); donc

                       h = (a²b)⁵(d²fbd ⁻¹)⁻¹(a²b)⁵(d²fbd ⁻¹)

retourne y_ac et  y_ad sans toucher aux autres bords. Si y et y' sont deux éléments distincts de Y, et si g ∈ Rub envoie y_ac sur y et  y_ad  sur y', alors ghg⁻¹ 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 Rot⁰_Y de Rot_Y des éléments de rotation totale nulle (un élément de Rot⁰_Y 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 Rot⁰_Y.


• Mise en place des coins.— La mise en place des coins utilise l’élément (b⁻¹a⁻¹ba)³ de Rub. Cet élément a pour vertu de fixer les bords, et donc d’appartenir à Rub ∩ G_X, et d’échanger les coins x_abc et x_fcb (en échangeant les faces a et f) ainsi que les coins x_adb et  x_dae (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 Perm_X est un produit de deux transpositions de supports disjoints.


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


• Orientation des coins.— On note Rot⁰_X le sous-groupe de Rot_X des éléments de rotation totale nulle (i.e. le noyau de  rt_X). On a aussi Rot⁰_X = H ∩  Rot_X, puisqu’un élément de Rot_X est déjà dans les noyaux de  rt_Y o π_Y et de ε.


Lemme 10. — On a Rot⁰_Y ⊂ 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 Perm_Y, il existe g₁ ∈ Rub tel que σ_Y o π_Y(g₁) = σ_Y o π_Y(h), et alors h₁ = g₁⁻¹ h est un élément de H appartenant au noyau de σ_Y o π_Y.

• D’après le lemme 8, il existe g₂ ∈ Rub tel que π_Y(g₂) = π_Y(h₁)), et alors h₂ = g₂⁻¹ h₁ est un élément de H appartenant à G_X.

• On a ε(h₂) = 1, et comme h₂ induit l’identité sur Y, la permutation σ_X(h₂) appartient à Alt_X. D’après le lemme 9, ceci implique qu’il existe g₃ ∈ Rub ∩ G_X tel que σ_X(g₃) = σ_X(h₂), et alors g₄ = g₃⁻¹ h₂ est un élément de H ∩ Rot_X. Or H ∩ Rot_X = Rot⁰_X est inclus dans Rub d’après le lemme 10 ; on a donc g₄ ∈ Rub.

• Comme h = g₁g₂g₃g₄, 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 GL_n(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 (n_x)_{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 Rot_X et Perm_X (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 a²b 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.