Théorie mathématique sur le Rubik's Cube

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Cet article présente le modèle mathématique relatif au cube de Rubik.

Notations utilisées[modifier | modifier le code]

(où C_k^n désigne \underbrace{C_k \times C_k \times ... \times C_k}_{n \ fois} )

  • Les rotations d'un quart de tour dans le sens direct sont appelées R \,, U \,, L \,, F \,, B \,, D \, pour les faces droite (right), haut (up), gauche (left), avant (front), arrière (back) et bas (down).
  • 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.
  • * \, l'opérateur de composition (avec (f*g)(x) = g[f(x)] \,).
  •  (i,j) = f \in \mathfrak{S}_n : \forall k \in C_n , (k \ne i \ et \ k \ne j \Rightarrow f(k)=k) \ et \ f(i) = j \ et \ f(j)=i

Décomposition des mouvements du cube[modifier | modifier le code]

Isomorphisme \mbox{entre} \, H \,\mbox{et} \, (C_3^8 \rtimes_P \, \mathfrak{S}_8) \times (C_2^{12} \rtimes_P \, \mathfrak{S}_{12})[modifier | modifier le code]

Factorisation sommets-arêtes[modifier | modifier le code]

Un élément de H se décompose naturellement entre ce qu'il fait sur les coins et ce qu'il fait sur les sommets. On introduit les 2 sous-groupes Hco et Har constitués des mouvements laissant invariants respectivement les arêtes et les coins. H est isomorphe au produit de groupes H_\text{co}\times H_\text{ar}.

On va maintenant montrer que H_\text{co}\simeq (C_3^8 \rtimes_P \, \mathfrak{S}_8) et H_\text{ar}\simeq (C_2^{12} \rtimes_P \, \mathfrak{S}_{12}).

Permutation des arêtes et des sommets[modifier | modifier le code]

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 2 morphismes surjectifs de groupes \rho : H_\text{co} \rightarrow \mathfrak{S}_8 \, et \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.
En utilisant la notation des cycles, on a \rho(F) = (1,5,8,4) = (4,8)*(8,5)*(5,1) \, et \rho(U) = (4,3,2,1) = (1,2)*(2,3)*(3,4) \,, d'où \rho(F*U)=(1,5,8,3,2) \,. (attention : la notation des cycles est davantage adaptée à la loi \circ : si f = (1,2,3,4) \,, on a f = (1,2)\circ(2,3)\circ(3,4) = (4,3)*(3,2)*(2,1) \, et f(1)=2 ; f(2) = 3 ; f(3)=4 ; f(4)=1 \,)

Orientation des arêtes et des sommets[modifier | modifier le code]

\text{Rot}_\text{co} = \ker\, \rho et \text{Rot}_\text{ar} = \ker\, \sigma sont deux sous-groupes distingués de H : les rotations des coins et des arêtes (seule l'orientation des cubes change, pas leur position). Ils vont permettre de décomposer Hco et Har en produits semi-directs internes.

Changer un cube de position (par exemple mettre FUL en FUR) est une opération ambigue : 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 2 sous-groupes, Permco et Permar, complémentaires de Rotco et Rotar. Permco est le groupe des mouvements des coins à orientation constante, isomorphe à \mathfrak{S}_8. Ainsi H_\text{co} = \text{Rot}_\text{co} \rtimes \text{Perm}_\text{co} et on note \vec{v} \, : \, H_\text{co} \rightarrow \text{Rot}_\text{co} \simeq C_3^8 l'application coordonnée du produit semi-direct (ce n'est pas un morphisme de groupes).

On peut dessiner le choix de Permco et Permar en plaçant un marqueur \star sur chaque coin et face du Rubik's cube. Un mouvement d'orientation constante amènera la face marquée de la position de départ sur la face marquée de la position d'arrivée. Par exemple :
Pour les sommets : Rubik's cube marqueurs sommets.svg
Ce qui veut dire qu'un mouvement de Permco laisse les faces de l'axe blanc-jaune dans l'axe blanc-jaune.
Pour les arêtes :Rubik's cube marqueurs arêtes.svg
Rubik's cube orientation sommets.svg
On définit de même l'orientation des arêtes par le nombre de rotations de 180° permettant de rétablir l'orientation initiale : \vec{w} \, : \, H \rightarrow C_2^{12}. On a : \vec{v}(g*h)= \vec{v}(g) + P(\rho(g)^{-1},\vec{v}(h))
et \vec{w}(g*h)= \vec{w}(g) + P(\sigma(g)^{-1},\vec{w}(h))

Exemple : \vec{w}(F) = (1,0,0,0,0,0,0,0,1,0,0,0), \sigma (F) = (1,6,9,5) \,, \vec{w}(U)=(1,0,1,0,0,0,0,0,0,0,0,0) et \sigma (U)=(4,3,2,1) \,
 \Longrightarrow \vec{w}(F*U) = (1,0,1,0,1,0,0,0,1,0,0,0) et \sigma (F*U)=(1,6,9,5,4,3,2) \,

L'isomorphisme[modifier | modifier le code]

Soit H' \ = \ (C_3^8 \rtimes_P \, \mathfrak{S}_8) \times (C_2^{12} \rtimes_P \, \mathfrak{S}_{12}), on définit l'opération * \, par :
h*h' \ = \ (v,r,w,s)*(v',r',w',s') = (v+P(r^{-1},v'),rr',w+P(s^{-1},w'),ss') \,.
L'application \begin{matrix} \iota : & H &  & \rightarrow & \ H' \\ \ & g &  & \mapsto \ & (\vec{v}(g),\rho(g),\vec{w}(g),\sigma(g))\end{matrix} est un isomorphisme.
En effet, étant donné que
(\vec{v}(g),\rho(g),\vec{w}(g),\sigma(g))*(\vec{v}(h),\rho(h),\vec{w}(h),\sigma(h))=
(\vec{v}(g)+P(\rho(g)^{-1},\vec{v}(h)),\rho(g)\rho(h),\vec{w}(g)+P(\sigma(g)^{-1},\vec{w}(h)),\sigma(g)\sigma(h)),
l'application \iota est un morphisme.
De plus, elle est injective car \ker(\iota) = Id_{H} (en effet si aucun cube n'est déplacé ou réorienté, c'est que le cube est resté invariant !).
Elle est nécessairement surjective car en démontant le cube (on est ici dans le groupe élargi H \,), on peut parvenir à n'importe quelle configuration du Rubik's Cube.

Théorème fondamental : caractérisation des mouvements légaux[modifier | modifier le code]

Soit g \in H, \iota(g) = (v,r,w,s).
g \in G \Longleftrightarrow \left\{ \begin{matrix} a) & \varepsilon(r) & = & \varepsilon(s), \\ b) & \sum_{i=1}^{8} v_i & \equiv & 0 (mod \ 3), \\ c) & \sum_{i=1}^{12} w_i & \equiv & 0 (mod \ 2) \end{matrix} \right..

Démonstration de la partie directe[modifier | modifier le code]

\varepsilon(\rho(g))=\varepsilon(\sigma(g)) \,[modifier | modifier le code]

Soit g \in G.

On a r = \rho(g) \, et s = \sigma(g) \,. On écrit g = X_1X_2...X_k \,, où X_i \, est un mouvement parmi R \,, L \,, U \,, F \,, B \, et D \,.On démontre que pour chacun de ces mouvements, que \varepsilon(\rho(X))=\varepsilon(\sigma(X)) \,. Étant donné que \varepsilon \,, \rho \,, \sigma \, sont des morphismes, on a alors :
\varepsilon(r) = \varepsilon(\rho(g)) = \prod_{i=1}^k \varepsilon(\rho(X_i)) = \prod_{i=1}^k \varepsilon(\sigma(X_i)) = \varepsilon(\sigma(X)) = \varepsilon(s).

\sum_{i=1}^8 v_i \equiv 0 (mod \ 3)[modifier | modifier le code]

Vérifions que cette relation est valable pour les six rotations "de base" :

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

Il est immédiat que \sum_{i=1}^{8} v_i \equiv 0 (mod \ 3) \Longleftrightarrow \exists P \in S_8 : \sum_{i=1}^{8} v_{P(i)} \equiv 0 (mod \ 3) et que si deux familles (v_i) \, et (v_i') \, vérifient b), alors la famille (v_i + v_i') \, vérifie b) également.

On écrit le mouvement g de la même manière que précédemment (g = X_1X_2...X_k \,), on suppose de plus qu'il s'agit d'une expression minimale du mouvement (ie on ne peut l'écrire avec moins de mouvements). L'entier k est appelé longueur de g (il s'agit de la distance entre g et l'identité dans le graphe de Cayley de G.)

On peut donc prouver b) par induction sur la longueur du mouvement. La longueur k=1 a déjà été vérifiée (si k = 1, alors g \in \{R,L,U,F,B,D\}).

Supposons k>1. On a \vec{v}(X_1X_2...X_{k-1}X_k) = \vec{v}(X_1X_2...X_{k-1}) + P(\rho(X_1X_2...X_{k-1})^{-1},\vec{v}(X_k)). \rho(X_1X_2...X_{k-1}) \, étant une permutation de  \mathfrak{S}_n , P(\rho(X_1X_2...X_{k-1})^{-1},\vec{v}(X_k)) vérifie b), de plus d'après l'hypothèse d'induction, \vec{v}(X_1X_2...X_{k-1}) le vérifie également. Comme leur somme le vérifie, on obtient la relation.

\sum_{i=1}^{12} w_i \equiv 0 (mod \ 2)[modifier | modifier le code]

Idem que précédemment en remplaçant \rho par \sigma

Démonstration de la réciproque[modifier | modifier le code]

Soit g \in H vérifiant les trois points présentés précédemment.

On démontre d'abord la réciproque dans des cas particuliers, pour arriver ensuite au cas général.

v quelconque, r=id_{[[1,8]]} ; s=id_{[[1;12]]} ; (w_i)_{1\le i \le 12}=(0,0...,0)[modifier | modifier le code]

Il existe un mouvement qui tourne deux coins (sans les permuter) et qui préserve l'orientation et la position de chacun des autres cubes. En modifiant ce mouvement, on peut générer l'ensemble des 8-uplets vérifiant b) Certains de ces mouvements seront ajoutés par la suite

w quelconque, r=id_{[[1,8]]} ; s=id_{[[1;12]]} ; (v_i)_{1\le i \le 8}=(0,0...,0)[modifier | modifier le code]

Il est possible de retourner deux arêtes et de laisser le reste invariant. On génère alors l'ensemble des 12-uplets vérifiant c).

v et w quelconques, r=id_{[[1,8]]} ; s=id_{[[1;12]]} \,[modifier | modifier le code]

Soit g \, défini par (v,id_{[[1,8]]},w,id_{[[1,12]]}) \,, h \, et h' \, définis par (v,id_{[[1,8]]},0,id_{[[1,12]]}) \, et (0,id_{[[1,8]]},w,id_{[[1,12]]}) \,.
\iota(h*h')=(v+P(id^{-1},0),id,0+P(id^{-1},w),id)=\iota(g) \,, alors comme \iota \, est bijective, on en déduit g=h*h' \,: c'est la composée de deux mouvements "légaux", donc g \in G \,.

r et s quelconques, (v_i)_{1\le i \le 8}=(0,0...,0) ; (w_i)_{1\le i \le 12}=(0,0...,0)[modifier | modifier le code]

On montre en utilisant la relation a) que ce mouvement appartient à G \,

(À approfondir)

v,r,w,s quelconques[modifier | modifier le code]

Soit g \, vérifiant a) b) et c). Alors \iota(g)=(v,id,0,id)*(0,id,w,id)*(0,r,0,s) \, et chacun de ces trois mouvements est légal, donc g \in G \,.

Calcul du cardinal du groupe des mouvements du Rubik's Cube[modifier | modifier le code]

  • On élargit le groupe en supprimant la condition a) par

G_0=(\{(v,r,w,s) | r \in \mathfrak{S}_8, s \in \mathfrak{S}_{12}, \sum_{i=1}^{8} v_i \equiv 0 \,(mod \, 3), \sum_{i=1}^{12} w_i \equiv 0 \,(mod \, 2) \}.
On définit sur G_0 \, l'opération * \, par (v,r,w,s)*(v',r',w',s')=(v+P(r^{-1},v'),r*r',w+P(s^{-1},w'),s*s') \,.
(G_0,*) \, est un groupe :

    • * \, est interne
    • l'associativité de * \, :
      • est évidente pour r\, et s\,
      • découle (pour v \, et w \,) du fait que \left\{ \begin{matrix}P(r,a+b) & = & P(r,a)+P(r,b) \\ P(r*r',a) & = & P(r',P(r,a)) \end{matrix} \right. (attention à l'opération * \,)
    • (0,id,0,id) \, est élément neutre
    • (-P(r^{-1},v),r^{-1},-P(s^{-1},w),s^{-1}) \, est l'inverse de (v,r,w,s) \,
  • G_0 \, est isomorphe à ( \mathcal{C}_3^7 \rtimes \mathfrak{S}_8) \times ( \mathcal{C}_2^{11} \rtimes \mathfrak{S}_{12})

avec \mathcal{C}_n^k=\{(v_1,v_2,...,v_k,v_{k+1} | \forall i \in [[1,k+1]], v_i \in [[0,n-1]] \, \mbox{et} \, \sum_{i=1}^{k+1} v_i \equiv 0 \,(mod \, n) \},
ie \mathcal{C}_n^k=\{(v_1,v_2,...,v_k,\overline{ \left(-\sum_{i=1}^{k} v_i \right) } \, | \, \forall i \in [[1,k]], v_i \in [[0,n-1]] \}, où \bar x \, désigne la classe d'équivalence de x dans C_n \,.
On obtient ainsi \mathcal C_n^k \cong C_n^k \,,
et on en déduit card \, G_0 = (card \mathfrak S_8) \times (card \mathfrak S_{12}) \times 
(card C_3^7) \times (card C_2^{11}) = 8! \times 12! \times 3^7  \times 2^{11} \,

  • G \subset G_0 \, et  G = \{(v,r,w,s) \in G_0 \, | \, \varepsilon(r) = \varepsilon(s) \} \,

Soit \begin{matrix} f : & G_0 & \rightarrow & \{-1,1\} \\ & (v,r,w,s) & \mapsto & \varepsilon(r)\varepsilon(s) \end{matrix}, on a G=\, ker\, f\,.

  • Montrons que G \, est un sous-groupe normal de G_0 \, .
    • D'après la caractérisation des sous-groupes, G \, est un sous-groupe de G_0 \, .
    • \forall g \in G_0, \forall h \in G, g^{-1}*h*g \in G \, .
      • on a \rho( g^{-1} * h * g ) \in \mathfrak{S}_8, \sigma( g^{-1} * h * g) \in \mathfrak{S}_{12} \, .
      • comme g,h \in G_0 \, , alors les propriétés b) et c) sont vérifiées par g^{-1}*h*g \, (structure de groupe).
      • \begin{matrix} \varepsilon(\rho(g^{-1}*h*g))\varepsilon(\sigma(g^{-1}*h*g)) & = & \varepsilon(\rho(g^{-1}))\varepsilon(\rho(h))\varepsilon(\rho(g))\varepsilon(\sigma(g^{-1}))\varepsilon(\sigma(h))\varepsilon(\sigma(g)) & \mbox{car }\varepsilon,\rho\mbox{ et }\sigma\mbox{ sont des morphismes} \\ & = & \varepsilon(\rho(g^{-1}*g))\varepsilon(\sigma(g^{-1}*g))\varepsilon(\rho(h))\varepsilon(\sigma(h)) & \\ & = & \varepsilon(\rho(h))\varepsilon(\sigma(h)) & \mbox{ car }g^{-1}*g=id \\ & = & 1 & \mbox{ car }h \in G \end{matrix}\,

Donc G \rtimes G_0 \, , et le groupe quotient G_0 / G \, existe.

  • Calcul de l'indice de G \, dans G_0 \, :

Soit \mathcal R la relation définie par  \forall (g,g') \in G_0 , g=(v,r,w,s),g'=(v',r',w',s'),
g\mathcal Rg' \Leftrightarrow \varepsilon(r)\varepsilon(s)=\varepsilon(r')\varepsilon(s')
Soit g = (v,r,w,s)\in G_0 \, et g_1 = (v,\tau*r,w,s) \in G_0\tau \, est une transposition.
Soit h \in G_0, on a  h\mathcal R g \mbox{ ou }h \mathcal R g_1, d'où G_0/G=\{cl(g),cl(g_1)\} \,.
On en déduit que l'indice de G \, dans G_0 \, est [G_0:G] =|G_0/G|=2 \, .
D'après le théorème de Lagrange, |G|=|G_0| / [G_0:G] = \underline{8!12!2^{10}3^7} \,

Générateurs et relations[modifier | modifier le code]

Liens externes[modifier | modifier le code]