Groupe du Rubik's Cube

Cet article présente un modèle mathématique et une présentation du groupe du Rubik's Cube.

Notations utilisées

• ${\displaystyle G\,}$ est le groupe des mouvements légaux ou le groupe des états (sans démonter le cube !).
• ${\displaystyle H\,}$ est le groupe élargi ou le groupe des états étendus (ici on peut démonter le cube, mais les mouvements des sommets et des arêtes doivent rester chacun dans leur camp).
• ${\displaystyle C_{n}\,=\,\mathbb {Z} /n\mathbb {Z} }$ est l'ensemble des classes d'équivalence pour la congruence modulo n. Il est isomorphe au groupe des n-èmes de tour d'axe donné. On utilisera en particulier C₃ pour pivoter un coin du cube, et C₂ pour pivoter une arête. On note ${\displaystyle C_{k}^{n}=(C_{k})^{n}}$ à savoir ${\displaystyle \underbrace {C_{k}\times C_{k}\times ...\times C_{k}} _{n\ fois}}$.
• ${\displaystyle {\mathfrak {S}}_{n}}$ est le groupe symétrique d'ordre n. Ses éléments sont les permutations de n objets. Parmi ces permutations, celle de deux objets s'appelle transposition. On utilisera en particulier ${\displaystyle {\mathfrak {S}}_{8}}$ pour permuter les coins du cube, et ${\displaystyle {\mathfrak {S}}_{12}}$ pour permuter ses arêtes. La composition des permutations se lit de droite à gauche.
• ${\displaystyle \varepsilon \,}$ désigne la signature d'une permutation de ${\displaystyle {\mathfrak {S}}_{n}\,}$.
• Pour toute permutation s élément de ${\displaystyle {\mathfrak {S}}_{n}}$, on note P(s) l'automorphisme défini par : ${\displaystyle P(s):{\begin{matrix}C_{k}^{n}&\rightarrow &C_{k}^{n}\\(x_{1},x_{2},...x_{n})&\mapsto &(x_{s^{-1}(1)},x_{s^{-1}(2)},...x_{s^{-1}(n)})\end{matrix}}}$. P(s) permute les composantes ${\displaystyle (x_{1},x_{2},...x_{n})}$. s étant une bijection, on remarque que la somme des composantes est invariante : ${\displaystyle \sum _{i=1}^{n}x_{i}=\sum _{i=1}^{n}x_{s^{-1}(i)}}$. P est un morphisme du groupe ${\displaystyle {\mathfrak {S}}_{n}}$ dans le groupe des automorphismes de ${\displaystyle C_{k}^{n}}$.
• ${\displaystyle \rtimes }$ est le symbole d'un produit semi-direct interne, et ${\displaystyle \rtimes _{P}\,}$ celui d'un produit semi-direct externe induit par P.
• Les rotations d'un quart de tour, dans le sens des aiguilles d'une montre (sens direct par rapport à un axe entrant dans le cube), sont appelées ${\displaystyle R\,}$, ${\displaystyle U\,}$, ${\displaystyle L\,}$, ${\displaystyle F\,}$, ${\displaystyle B\,}$, ${\displaystyle D\,}$ pour les faces droite (right), haut (up), gauche (left), avant (front), arrière (back) et bas (down)^[1],[2].
• On identifie les sommets par 3 coordonnées et les arêtes par 2 ; par exemple FUL est le sommet de face en haut à gauche et BR est l'arête arrière droite^[1].

Décomposition des mouvements du cube

Isomorphisme entre H et ${\displaystyle (C_{3}^{8}\rtimes _{P}\,{\mathfrak {S}}_{8})\times (C_{2}^{12}\rtimes _{P}\,{\mathfrak {S}}_{12})}$

Factorisation sommets-arêtes

Un élément de H se décompose naturellement entre son action sur les coins et son action sur les arêtes, ces deux actions étant indépendantes. On introduit les deux sous-groupes H_co et H_ar constitués respectivement des mouvements agissant sur les coins et laissant invariante chaque arête, et des mouvements agissant sur les arêtes et laissant invariant chaque coin. H est isomorphe au produit direct des groupes ${\displaystyle H_{\text{co}}\times H_{\text{ar}}}$^[3].

On va maintenant montrer que ${\displaystyle H_{\text{co}}}$ est isomorphe au produit semi-direct ${\displaystyle C_{3}^{8}\rtimes _{P}{\mathfrak {S}}_{8}}$ et ${\displaystyle H_{\text{ar}}}$ au produit semi-direct ${\displaystyle C_{2}^{12}\rtimes _{P}{\mathfrak {S}}_{12}}$.

L'isomorphisme entre ${\displaystyle H_{\text{co}}}$ et ${\displaystyle C_{3}^{8}\rtimes _{P}{\mathfrak {S}}_{8}}$ exprime le fait qu'une action sur les coins se décompose en une permutation des 8 coins (élément de ${\displaystyle {\mathfrak {S}}_{8}}$), et pour chaque coin, d'une rotation possible de 0, 1 ou 2 tiers de tour (pour chaque coin, le groupe de ces rotations est isomorphe à C₃)^[4].

De même, l'isomorphisme entre ${\displaystyle H_{\text{ar}}}$ et ${\displaystyle C_{2}^{12}\rtimes _{P}\,{\mathfrak {S}}_{12}}$ exprime le fait qu'une action sur les arêtes se décompose en une permutation des 12 arêtes, et pour chaque arête, d'une rotation possible de 0 ou 1 demi-tour.

Permutation des arêtes et des sommets

On numérote les sommets du Rubik's cube de 1 à 8 dans cet ordre : FUR, BUR, BUL, FUL, FDR, BDR, BDL, FDL. Les arêtes vont de 1 à 12 : UL, BL, DL, FL, FU, BU, BD, FD, UR, BR, DR, FR.

On définit alors deux morphismes surjectifs de groupes ${\displaystyle \rho :H_{\text{co}}\rightarrow {\mathfrak {S}}_{8}}$ et ${\displaystyle \sigma :H_{\text{ar}}\rightarrow {\mathfrak {S}}_{12}}$ qui extraient d'un élément de H les permutations des sommets et des arêtes correspondantes, sans tenir compte de leur orientation^[3].

Par exemple, en utilisant la notation des cycles, on a ${\displaystyle \rho (F)=(1,5,8,4)}$ et ${\displaystyle \rho (U)=(4,3,2,1)}$, d'où ${\displaystyle \rho (U\circ F)=(1,5,8,3,2)}$.

Orientation des arêtes et des sommets

Posons ${\displaystyle {\text{Rot}}_{\text{co}}=\ker(\rho )}$ et ${\displaystyle {\text{Rot}}_{\text{ar}}=\ker(\sigma )}$. Ce sont deux sous-groupes distingués de H. Leurs éléments sont les rotations des coins (identité ou tiers de tour, dans un sens ou dans l'autre) et des arêtes (identité ou demi-tour). Seule l'orientation des cubes change, pas leur position. Ces deux groupes vont permettre de décomposer H_co et H_ar en les produits semi-directs annoncés.

Changer un cube de position (par exemple mettre FUL en FUR) est une opération ambiguë : dans la position d'arrivée, il y a 3 orientations possibles pour les coins, 2 pour les arêtes. Parmi tous ces mouvements possibles, on en choisit formant deux sous-groupes, Perm_co et Perm_ar, complémentaires de Rot_co et Rot_ar.

Perm_co est le groupe des mouvements des coins à orientation constante, isomorphe à ${\displaystyle {\mathfrak {S}}_{8}}$. En identifiant Perm_co à ${\displaystyle {\mathfrak {S}}_{8}}$, on peut voir ${\displaystyle \rho }$ comme un morphisme de H dans Perm_co. Pour tout g de ${\displaystyle H_{\text{co}}}$, ${\displaystyle g\rho (g)^{-1}}$ est alors un élément de H qui laisse en place chaque coin, mais en les pivotant sur place. C'est donc un élément ${\displaystyle v(g)}$ de ${\displaystyle {\text{Rot}}_{\text{co}}}$. On a donc la décomposition ${\displaystyle g=v(g)\rho (g)}$. Cette décomposition est unique du fait que ${\displaystyle {\text{Rot}}_{\text{co}}\cap {\text{Perm}}_{\text{co}}=\{{\text{Id}}\}}$. ${\displaystyle \rho (g)}$ indique où les coins sont déplacés, et ${\displaystyle v(g)}$ comment ils sont pivotés. La rotation de chaque sommet est donnée par un élément de ${\displaystyle C_{3}}$ indiquant de combien de tiers de tour le sommet est pivoté, de sorte que ${\displaystyle {\text{Rot}}_{\text{co}}}$ est isomorphe à ${\displaystyle C_{3}^{8}}$. On peut représenter ${\displaystyle v(g)}$ par un élément ${\displaystyle (v_{j})_{1\leq j\leq 8}}$ de ${\displaystyle C_{3}^{8}}$, la j-ème composante indiquant la rotation que subira le sommet qui arrivera en j par le déplacement dû à g.

On peut dessiner le choix de Perm_co en plaçant un marqueur ${\displaystyle \star }$ sur chaque coin du Rubik's cube. Un mouvement d'orientation constante est celui qui amène la face marquée de la position de départ sur la face marquée de la position d'arrivée^[4]. On peut prendre par exemple le marquage suivant :

pour lequel un mouvement élément de Perm_co laisse la réunion des faces blanc-jaune globalement invariante. On note ci-dessous par les valeurs 0, 1 ou 2 la valeur à attribuer à la rotation d'un coin en fonction de la place qu'occuperait sa face marquée par une étoile :

Si g et h sont éléments de ${\displaystyle H_{\text{co}}}$ avec :

${\displaystyle g=v(g)\circ \rho (g)}$

${\displaystyle h=v(h)\circ \rho (h)}$

alors, on a :

${\displaystyle hg=v(h)\rho (h)v(g)\rho (g)=v(h)\rho (h)v(g)\rho (h)^{-1}\rho (h)\rho (g)}$

${\displaystyle \rho (h)\rho (g)=\rho (hg)}$ est élément de ${\displaystyle {\text{Perm}}_{\text{co}}}$ et ${\displaystyle v(h)\rho (h)v(g)\rho (h)^{-1}=v(hg)}$ est élément de ${\displaystyle {\text{Rot}}_{\text{co}}}$. On n'a pas en géneral ${\displaystyle v(hg)=v(h)v(g)}$ ; v n'est donc pas un morphisme de groupe, ce qui empêche d'avoir un produit direct entre Rot_co et Perm_co. Mais la relation ${\displaystyle v(hg)=v(h)\rho (h)v(g)\rho (h)^{-1}}$ est caractéristique d'un produit semi-direct. Ainsi, ${\displaystyle H_{\text{co}}={\text{Rot}}_{\text{co}}\rtimes {\text{Perm}}_{\text{co}}}$.

Si ${\displaystyle v(g)}$ a pour composantes ${\displaystyle (v_{j})_{1\leq j\leq 8}}$, alors ${\displaystyle \rho (h)v(g)\rho (h)^{-1}}$ a pour composantes ${\displaystyle (v_{\rho (h)^{-1}(j)})_{1\leq j\leq 8}=P(\rho (h))((v_{j})_{1\leq j\leq 8})}$. Le remplacement de ${\displaystyle {\text{Rot}}_{\text{co}}}$ par son groupe isomorphe ${\displaystyle C_{3}^{8}}$ transfère le produit semi-direct interne ${\displaystyle {\text{Rot}}_{\text{co}}\rtimes {\text{Perm}}_{\text{co}}}$ en le produit semi-direct externe ${\displaystyle C_{3}^{8}\rtimes _{P}{\mathfrak {S}}_{8}}$.

On remarque par ailleurs que la somme des composantes de ${\displaystyle v(g)}$ est égale à celle de ${\displaystyle \rho (h)v(g)\rho (h)^{-1}}$. Il en résulte que la somme des composantes de ${\displaystyle v(hg)}$ est égale à la somme de celles de ${\displaystyle v(h)}$ et de celles de ${\displaystyle v(g)}$. Ainsi, v n'est pas un morphisme, mais la somme des composantes (appelée rotation totale des coins) en est un, à valeurs dans ${\displaystyle C_{3}}$^[4].

On opère de même sur les arêtes en choisissant un marquage privilégié de chacune d'elles, ce qui permet de définir leur orientation ${\displaystyle w\,:\,H\rightarrow C_{2}^{12}}$ par le nombre de rotations de 180° permettant de rétablir l'orientation initiale. On peut prendre par exemple :

Comme pour v, w n'est pas un morphisme de groupe, et on a seulement une structure de produit semi-direct ${\displaystyle H_{\text{ar}}={\text{Rot}}_{\text{ar}}\rtimes {\text{Perm}}_{\text{ar}}\simeq C_{2}^{12}\rtimes _{P}{\mathfrak {S}}_{12}}$, mais la somme de des composantes de w (appelée rotation totale des arêtes) est un morphisme, à valeurs dans ${\displaystyle C_{2}}$.

Théorème fondamental : caractérisation des mouvements légaux

On rappelle que H est le groupe des actions sur le cube de Rubik démontable, et G le groupe des actions sur le cube non démontable (en effectuant des mouvements des faces selon les règles). Pour tout g élément de H, soit vrws la décomposition de g en le produit d'un élément v de ${\displaystyle C_{3}^{8}}$ (pivotements des coins), r élément de ${\displaystyle {\mathfrak {S}}_{8}}$ (permutation des coins), w élément de ${\displaystyle C_{2}^{12}}$ (pivotements des arêtes), s élément de ${\displaystyle {\mathfrak {S}}_{12}}$ (permutation des arêtes). Alors^[5],[6] :

${\displaystyle g\in G\Longleftrightarrow \left\{{\begin{matrix}a)&\varepsilon (r)\varepsilon (s)&=&1\\b)&\sum _{i=1}^{8}v_{i}&\equiv &0\;{\rm {mod}}\;3\\c)&\sum _{i=1}^{12}w_{i}&\equiv &0\;{\rm {mod}}\;2\end{matrix}}\right.}$

Autrement dit, G est le noyau du morphisme ${\displaystyle \Phi }$ de H dans ${\displaystyle \{\pm 1\}\times C_{3}\times C_{2}}$, qui, à tout g de H associe le triplet ${\displaystyle \Phi (g)=(\varepsilon (r)\varepsilon (s),\sum _{i=1}^{8}v_{i},\sum _{i=1}^{12}w_{i})}$.

Le a) exprime par exemple que, selon les règles du jeu, il est impossible de transposer seulement deux sommets, ou bien seulement deux arêtes. Selon le b), il est impossible de pivoter un coin seul. Deux coins seuls peuvent être pivotés mais en sens inverse l'un de l'autre. Il dit aussi que l'orientation d'un coin est défini de manière unique par l'orientation des 7 autres coins. Le c) exprime qu'il est impossible de pivoter une arête seule. Le pivotement des arêtes s'opère nécessairement par paire. L'orientation d'une arête est définie de manière unique par l'orientation des 11 autres.

Le sens direct de la démonstration consiste à montrer que tout mouvement selon les règles vérifient ces conditions. Le sens réciproque consiste à prouver que, si on se donne une configuration du Rubik's cube vérifiant ces conditions, alors il existe une suite de mouvements selon les règles qui conduit à cette configuration (ou inversement, qui fait passer de cette configuration à la configuration initiale). C'est la description d'un algorithme de résolution du Rubik's cube^[7].

Démonstration de la partie directe

Il s'agit de montrer que G est inclus dans ${\displaystyle \ker(\Phi )}$. Pour cela, ${\displaystyle \Phi }$ étant un morphisme, il suffit de le prouver pour un système générateur de G, à savoir les six rotations de chacune des faces^[7].

En ce qui concerne ε(ρ(g))ε(σ(g)), une rotation d'une face est constitué d'un 4-cycle sur les coins et d'un 4-cycle sur les arêtes. Chaque cycle a pour signature -1 et leur produit fait bien 1.

En ce qui concerne ${\displaystyle \sum _{i=1}^{8}v_{i}\;{\rm {mod}}\;3}$, observons comment chaque rotation de face fait pivoter chacun des coins, (en utilisant le codage 0, 1 et 2 des trois faces de chaque coin donné dans le paragraphe précédent) :

${\displaystyle g\,}$	${\displaystyle v(g)}$
${\displaystyle F\,}$	(2,0,0,1,1,0,0,2)
${\displaystyle U\,}$	(0,0,0,0,0,0,0,0)
${\displaystyle D\,}$	(0,0,0,0,0,0,0,0)
${\displaystyle B\,}$	(0,1,2,0,0,2,1,0)
${\displaystyle R\,}$	(1,2,0,0,2,1,0,0)
${\displaystyle L\,}$	(0,0,1,2,0,0,2,1)

On constate bien que, pour chaque face, la somme des composantes de ${\displaystyle v(g)}$ est nulle modulo 3.

On peut opèrer une vérification analogue sur les arêtes pour montrer que ${\displaystyle \sum _{i=1}^{12}w_{i}}$ est nulle modulo 2. Mais il est plus rapide de remarquer que la rotation d'une face induit sur les 2 × 12 = 24 facettes carrées des 12 arêtes une permutation qui est le produit de deux 4-cycles (l'un des 4-cycles permute circulairement 4 facettes, l'autre 4-cycle permute circulairement 4 autres facettes, adjacentes aux 4 premières). Il en résulte que la signature de la permutation des 24 facettes vaut 1, et qu'il en est de même par composition pour un mouvement quelconque du Rubik's cube. Or cette signature n'est autre que ${\displaystyle (-1)^{\sum w_{i}}}$. Il en résulte que ${\displaystyle \sum _{i=1}^{12}w_{i}}$ est nulle modulo 2^[7].

Démonstration de la réciproque

Il s'agit de montrer que ${\displaystyle \ker(\Phi )}$ est inclus dans G. Pour cela, partant d'une configuration g appartenant à ${\displaystyle \ker(\Phi )}$, on lui applique une suite S de rotations des faces appartenant à G de façon que ${\displaystyle S\circ g={\rm {Id}}}$. Cela prouve que g est le symétrique de S, donc est élément de G^[7].

Les mouvements des faces à effectuer seront donnés ici par une suite de lettres : majuscules F, R, L, B, U, D pour une rotation dans le sens des aiguilles d'une montre, minuscules f, r, l, b, u, d pour le sens inverse. La composition des mouvements se fera dans ce paragraphe dans le sens de la lecture du mot ainsi formé, i.e. de gauche à droite. Ainsi, le mouvement "FUl" est constitué d'une rotation dans le sens des aiguilles d'une montre de la face F, suivie de la face U, et on termine par une rotation en sens inverse de la face L. La suite S est construite en mettant d'abord en place les arêtes, puis les coins, puis en pivotant convenablement les arêtes, puis les coins.

Mise en place des arêtes : pour tout couple d'arêtes, il existe un élément de G qui transpose ces deux arêtes, en laissant les autres arêtes en place (à pivotement près)^[8]. Par exemple "uFULulf" transpose deux arêtes de la face U^[9]. Comme les transpositions engendrent le groupe symétrique, cela prouve qu'il existe un élément de G qui dispose les arêtes à leur place.

Mise en place des coins : Compte tenu de la condition de parité a) sur la signature des permutations des arêtes et des coins, si les arêtes sont en place, cela signifie que les coins sont permutés par une permutation paire. Or ces permutations sont engendrées par les 3-cycles (permutation circulaire de trois coins). Pour mettre les coins en place par un mouvement élément de G, il suffit donc de montrer que, pour tout triplet de coins, il existe un élément de G qui permute ces trois coins tout en laissant les autres coins et les arêtes à leur place. C'est effectivement le cas. Par exemple, le mouvement "LurUluRU" permute trois coins de la face U tout en laissant tous les autres cubes à leur place, sans modifier aucun autre cube^[10].

Pivotement des arêtes : Compte tenu de la condition c) sur le pivotement des arêtes, on peut pivoter convenablement les arêtes en opérant successivement sur deux arêtes à la fois. Pour tout couple d'arêtes, il existe un élément de G qui se borne à pivoter deux arêtes^[8]. Par exemple, le mouvement "BddbbdBDBddflbLF" pivote deux arêtes adjacentes de la face D sans modifier aucun autre cube^[11].

Pivotement des coins : Compte tenu de la condition b) sur le pivotement des coins, on peut pivoter convenablement les coins en opérant successivement sur deux coins à la fois, les rotations étant de sens opposé sur ces deux coins. Pour tout couple de coins, il existe un élément de G satisfaisant ces conditions^[12]. Par exemple, le mouvement "uBULBlFLblubUf" pivote en sens inverse deux coins de la face U^[13].

Une fois ces opérations terminées, le cube est remis en place et on a prouvé que la configuration initiale g est bien élément de G.

Calcul du cardinal du groupe des mouvements du Rubik's Cube

On rappelle qu'on a introduit un morphisme ${\displaystyle \Phi }$ de H dans ${\displaystyle \{\pm 1\}\times C_{3}\times C_{2}}$, qui, à une configuration g du cube démontable associe le triplet constitué du produit des signatures des permutations sur les coins et les arêtes, la rotation totale des coins et la rotation totale des arêtes. Le noyau de ${\displaystyle \Phi }$ est le groupe G des mouvements du Rubik's cube.

Ce morphisme est surjectif car, pour tout élément de ${\displaystyle \{\pm 1\}\times C_{3}\times C_{2}}$, on peut trouver une configuration g de H antécédent par ${\displaystyle \Phi }$ de cet élément. Il suffit pour cela de pivoter un coin et une arête de façon adéquate et éventuellement de permuter deux coins (on rappelle que, dans H, tous les mouvements sont possibles). Comme ${\displaystyle \{\pm 1\}\times C_{3}\times C_{2}}$ est de cardinal 12, il en résulte que G est un sous-groupe de H d'indice 12, les classes de G étant les gG avec g parcourant dans H un sous-ensemble de 12 représentants d'antécédents par ${\displaystyle \Phi }$ des 12 éléments de ${\displaystyle \{\pm 1\}\times C_{3}\times C_{2}}$.

Par conséquent, le cardinal de G est le douzième de celui de H^[3]. (C'est une variante du théorème de Lagrange ou de la formule des indices). Or le cardinal de H est ${\displaystyle |H|=8!\times 3^{8}\times 12!\times 2^{12}}$ (produit du nombre de permutations des coins par le nombre de pivotement des coins par le nombre des permutations des arêtes par le nombre de pivotement des arêtes), donc celui de G est :

${\displaystyle |G|={\frac {|H|}{12}}=2^{27}\times 3^{14}\times 5^{3}\times 7^{2}\times 11=43\ 252\ 003\ 274\ 489\ 856\ 000\approx 43\times 10^{18}}$

soit environ 43 milliards de milliards de combinaisons.

On peut aussi dire qu'il y a ${\displaystyle 2^{11}}$ pivotements d'arêtes possibles (l'orientation de la dernière arête étant alors imposée par la condition c)), ${\displaystyle 3^{7}}$ pivotements de coins possibles (l'orientation du dernier coin étant imposé par la condition b)), ${\displaystyle 8!}$ placements possibles des huit sommets, mais seulement ${\displaystyle {\frac {12!}{2}}}$ placements possibles des douze arêtes en raison de la condition de parité donnée par la condition a). Le total ${\displaystyle 2^{11}\times 3^{7}\times 8!\times {\frac {12!}{2}}}$ redonne le résultat précédent^[14],[15].

Générateurs et relations

Propriétés particulières

Comme précédemment, on donne les mouvements des faces à effectuer par une suite de lettres, la composition s'effectuant ici de gauche à droite : majuscules F, R, L, B, U, D pour une rotation dans le sens des aiguilles d'une montre, prime F', R', L', B', U', D' pour le sens inverse.

• On peut engendrer le groupe G en autorisant seulement les rotations de cinq faces données. En effet, le mouvement "R'LF'2B'2R'LD'R'LF'2B'2R'L", dû à Dave Benson, permet de tourner la face supérieure en utilisant uniquement les autres faces^[16].
• L'ordre maximal d'un élément de G est 1260. Il est obtenu par exemple par le mouvement "R'B'2DU'D"^[17].
• Le groupe G peut être engendré par deux mouvements seulement, par exemple "L'2B'R'DL" et "U'F'R'U'RUF"^[18].

Présentation du problème

D’après les notations utilisées pour étudier le Cube, le problème peut se présenter sous deux formes. On peut le traiter en utilisant des notations totalement mathématiques ou alors le traiter sous forme de mots puisque chacune des lettres R,U etc. correspond à une permutation (voir numérotation du Cube). Il existe donc une fonction surjective de l’ensemble des mots sur X = {R,L,U,D,F,B} vers l’ensemble des permutations du Cube. Pour une permutation, la longueur est définie comme étant, en partant du Cube résolu, le nombre minimum de mouvement (= générateurs considérés) à effectuer pour obtenir la permutation.

Première application : nombre minimum de mouvements

À partir de ces mouvements, on peut construire un arbre où chaque nœud représente une position du cube (chaque position correspond à une permutation appliquée au cube résolu). En partant du cube résolu, on peut construire une suite (${\displaystyle S_{n}}$) qui, à chaque étape, compte le nombre de branches finales de l'arbre. Ce nombre est un majorant de la quantité de positions d'un cube réalisable avec n mouvements de base. Plusieurs branches peuvent éventuellement aboutir à la même position, on va chercher à compter les branches en minimisant les positions identiques. On a ${\displaystyle S_{0}=1,S_{1}=18}$ (6 faces ayant 3 mouvements possibles, la double rotation d'une face compte comme un seul mouvement de la face), ${\displaystyle S_{2}=15*18}$ (le deuxième mouvement ne peut pas se faire sur la face précédemment tournée). Et ensuite pour tout n, on a ${\displaystyle S_{n}=12S_{n-1}+18S_{n-2}}$. Explication : remarquons qu'il n'y a que deux possibilités: soit on enchaine des mouvements de faces adjacentes en nombre quelconque, soit on enchaine au maximum deux mouvements de faces opposées (avant de refaire une face adjacente). Concernant les faces adjacentes successives : pour chacune des ${\displaystyle S_{n-1}}$ positions de l'étape n-1, on peut faire un des 3 mouvements de chacune des 4 faces adjacentes (à la dernière face tournée à l'étape n-1), soit 4*3=12 mouvements possibles. Concernant les faces opposées : pour cela, on revient à l'une des ${\displaystyle S_{n-2}}$ positions de l'étape d'avant (n-2) et on enchaine deux mouvements de faces opposés, ce qui conduit à l'étape n. Ces deux mouvements donnent lieu à 3*3=9 'résultats' possibles (on ne compte pas les possibilité de mouvements, mais seulement les différents résultats, et l'ordre d'exécution n'a pas d'importance). Et comme il y a deux couples de faces opposées adjacentes (à la face tournée à l'étape n-2), on obtient un total de 18 possibilités qui s'ajoutent pour arriver à l'étape n. 

On peut ensuite calculer les valeurs de la suite ${\displaystyle (S_{n})}$. Comme ${\displaystyle S_{17}\simeq 2.034\times 10^{19}}$ (qui est un majorant du nombre maximal de positions atteignables en 17 mouvements) est inférieur à ${\displaystyle |G|\simeq 4.3\times 10^{19}}$ (qui est le nombre positions du cube), on en déduit que 17 mouvements ne suffisent pas à produire toutes les positions du cube. Cela prouve que certaines positions du cube ne peuvent pas être atteintes en moins de 18 mouvements (remarque : ${\displaystyle S_{18}\simeq 2.716\times 10^{20}>|G|}$, donc on peut pas dire mieux avec ce raisonnement).

Il a été prouvé par des arguments plus techniques que certaines positions nécessitent 20 mouvements. (Voir Optimal solutions for Rubik's Cube)

Générateurs et relations : présentation d’un groupe

Soit X un ensemble fini avec n = card X. Le groupe libre sur les générateurs éléments de ${\displaystyle X}$ , noté ${\displaystyle F_{n}}$ est le groupe des mots réduits de ${\displaystyle X}$.

Soit Y un groupe de mots réduits sur X. Soit R le plus petit sous groupe normal de ${\displaystyle F_{n}}$ contenant Y. R constitue l’ensemble des relations de ${\displaystyle F_{n}}$. Le quotient F_n/R est un groupe ; c’est le plus grand groupe qui satisfait ces relations. On dit qu'il a pour générateurs l’ensemble X et pour relations l'ensemble Y. Un ensemble de générateurs et de relations est appelé une présentation.

En termes de notation, un élément r de R est noté sous forme d’une équation de la forme r = 1.

Exemple : le groupe cyclique d’ordre n possède un générateur x et une relation ${\displaystyle x^{n}=1}$ donc on a ${\displaystyle X=\{x\}}$ et ${\displaystyle R=\{(x^{n})^{k}|k\in Z\}\subset F_{1}={x^{k}|k\in Z}}$. ${\displaystyle C_{n}}$ admet donc comme présentation : ${\displaystyle C_{n}=\{x|x^{n}=1\}}$ Le groupe diédral d’ordre n a pour présentation ${\displaystyle D_{n}=\{a,b|a^{n}=1,b^{2}=1,aba=b\}}$

Produit semi-direct

Recherche d’une présentation de Cn
m ⋊ 𝕾n+1

Il faut d’abord chercher les représentations des groupes symétriques et des groupes cycliques. Pour le groupe symétrique d’ordre n+1, on a: ${\displaystyle {\mathfrak {S}}_{n+1}=<a_{1},...,a_{n}|(a_{i}a_{j})^{m_{i,j}}=1,1\leq i,j\leq \,n>}$avec ${\displaystyle m_{i,j}=\left\{{\begin{matrix}3&{\mbox{si }}j=i\pm \,1\\2&{\mbox{si }}|i-j|>1\\1&{\mbox{si }}i=j\end{matrix}}\right.}$ Dans le cas où n=4, la matrice est : ${\displaystyle {\begin{pmatrix}1&3&2&2\\3&1&3&2\\2&3&1&3\\2&2&3&1\end{pmatrix}}}$

Pour le produit cartésien du groupe cyclique d'ordre m, on a : ${\displaystyle C_{m}^{n}=<h_{1},...,h_{n})|h_{i}^{m}=1,h_{i}*h_{j}=h_{j}*h_{i},1\leq i,j\leq n>}$

Pour le groupe symétrique, on peut associer à chaque transposition (de deux indices consécutifs) ${\displaystyle a_{i}}$ une matrice de permutation de taille (n+1)*(n+1) ${\displaystyle s_{i}={\begin{pmatrix}1&0&\cdots &\cdots &\cdots &\cdots &\cdots &0\\\vdots &\ddots &&&&&&\vdots \\\vdots &&1&&&&&\vdots \\\vdots &&&0&1&&&\vdots \\\vdots &&&1&0&&&\vdots \\\vdots &&&&&1&&\vdots \\\vdots &&&&&&\ddots &\vdots \\0&\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &1\end{pmatrix}}}$ autrement dit ${\displaystyle s_{i}=I-E_{ii}-E_{i+1,i+1}+E_{i,i+1}+E_{i+1,i}}$

On peut aussi identifier ${\displaystyle C_{m}^{n}}$ avec le produit cartésien ${\displaystyle \{(h_{1}(x_{1}),...,h_{n}(x_{n}))|x_{i}\in C_{m}\}}$ où ${\displaystyle h_{i}(t)=I-E_{ii}-E_{i+1,i+1}+tE{ii}+t^{-1}E_{i+1,i+1}}$

On a alors les relations suivantes entre les ${\displaystyle s_{i}{\mbox{et les }}h_{j}(t)}$ ${\displaystyle {\begin{matrix}s_{i}h_{j}(t)s_{i}^{-1}=h_{j}(t),|i-j|>1\\s_{i}h_{i}(t)s_{i}^{-1}=h_{i}(t)^{-1},i=j\\s_{j\pm 1}h_{j}(t)s_{j\pm 1}^{-1}=h_{i}(t)h_{j\pm 1},i=j\pm 1\end{matrix}}}$

On peut alors démontrer la propriété suivante : ${\displaystyle (C_{m}^{n}\rtimes _{P}\,{\mathfrak {S}}_{n+1})=\left\langle a_{1},...,a_{n},h_{1}...,h_{n}|\left\{{\begin{matrix}{(a_{i}a_{j})}^{m_{ij}}=1\\h_{i}^{m}=1,h_{i}h_{j}=h_{j}h_{i}\\a_{i}h_{j}a_{i}^{-1}=h_{j},|i-j|>1\\a_{i}h_{i}a_{i}^{-1}=h_{i}^{-1}\\a_{j\pm 1}h_{j}a_{j\pm 1}=h_{i}h_{j\pm 1}\end{matrix}}\right.\right\rangle }$

Démonstration : si on appelle ${\displaystyle P}$ la représentation présentée ci-dessus. Le but de la démonstration est bien sûr de montrer ${\displaystyle (C_{m}^{n}\rtimes _{P}\,{\mathfrak {S}}_{n+1})\cong P}$. Pour cela on considère le morphisme ${\displaystyle F:P\mapsto (C_{m}^{n}\rtimes _{P}\,{\mathfrak {S}}_{n+1})}$ qui associe les générateurs de ${\displaystyle P\,}$ avec les générateurs de ${\displaystyle (C_{m}^{n}\rtimes _{P}\,{\mathfrak {S}}_{n+1})}$. Par définition de l'application, ${\displaystyle F\,}$ est surjective. Pour prouver l'injectivité, on note ${\displaystyle K=ker(F)}$. En notant ${\displaystyle card(G)=|G|}$, on a d'après le théorème de Lagrange : ${\displaystyle |P|=|P/K||K|\geq |P/K|=|(C_{m}^{n}\rtimes _{P}\,{\mathfrak {S}}_{n+1})|=m^{n}(n+1)!}$.

En considérant maintenant ${\displaystyle H=\{h_{1},...,h_{n}|h_{i}^{m}=1,h_{i}h_{j}=h_{j}h_{i}\}\subset P}$, ${\displaystyle H\,}$ est un sous groupe normal à ${\displaystyle P\,}$. En effet, chaque ${\displaystyle a_{i}}$ renvoie un générateur de H sur un produit de générateurs de H ou sur son inverse. Comme H est un groupe, on obtient que ${\displaystyle \{a_{i}h_{j}a_{i}^{-1}|1\leq i,j\leq n\}=H}$. On a donc ${\displaystyle H\cong C_{m}^{n}}$. Si ${\displaystyle w=W(a_{1},...,a_{n},h_{1},...,h_{n})=1}$ est une relation de P, le mot ${\displaystyle w\,}$ écrit dans le groupe quotient ${\displaystyle P/H}$ devient un mot qui ne contiendra plus que des relations du type ${\displaystyle {(a_{i}a_{j})}^{m_{ij}}=1}$. On peut montrer ainsi que ${\displaystyle P/H\cong S_{n+1}}$ (cette partie de la démonstration sera précisée).

Ainsi, on a ${\displaystyle |P/H||H|=|C_{m}^{n}||S_{n+1}|}$ ce qui montre ${\displaystyle |P|=m^{n}(n+1)!\,}$ et ainsi ${\displaystyle |K|=1\,}$ d'où ${\displaystyle K={1}\,}$. ${\displaystyle F\,}$ est donc injectif donc bijectif.

Liens externes

• Pierre Colmez, « Le Rubik's Cube, groupe de poche »
• W. D. Joyner, « Mathematics of the Rubik's cube », 1996
• Matthieu Barreau, « Une analyse du Cube Hongrois », 2011

Bibliographie

• David Singmaster, Notes on Rubik's cube, Enslow Publishers, 1981
• Edward C. Turner et Karen F. Gold, « Rubik's Groups », The American Mathematical Monthly, vol. 92, n^o 9,‎ 1985, p. 617-629 (DOI 10.1080/00029890.1985.11971700, lire en ligne)
• André Warusfel, Réussir le Rubik's cube, Denoël, 1981

Notes et références

1. (Singmaster, p. 4)
2. (Warusfel, p. 33)
3. (Colmez, p. 2)
4. (Colmez, p. 3)
5. (Colmez, p. 4)
6. (Warusfel, p. 152-160)
7. (Colmez, p. 5)
8. (Colmez, p. 6)
9. (Warusfel, p. 186)
10. (Warusfel, p. 182)
11. (Warusfel, p. 146). Ce mouvement a été découvert par Morwen Thistlethwaite (en)
12. (Colmez, p. 7)
13. (Warusfel, p. 184)
14. http://ronan.terpereau.perso.math.cnrs.fr/Projet-L3/analyse_cube_hongrois.pdf, Proposition 3
15. (Warusfel, p. 161)
16. (Warusfel, p. 142)
17. (Warusfel, p. 145)
18. (Warusfel, p. 144)

• Portail des mathématiques
• Portail des jeux