Théorie mathématique sur le Rubik's Cube - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Notations utilisées - Décomposition des mouvements du cube - Bibliographie

Introduction

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

Notations utilisées

$G \,$ le groupe des mouvements légaux (sans démonter le cube !)
$H \,$ le groupe élargi (ici on peut faire sauter le cube)
$C_n \, = \, \mathbb Z/n\mathbb Z$
$\mathfrak{S}_n \,$ le groupe symétrique d'ordre n
$\rtimes \,$ comme symbole pour le produit semi-direct
$\varepsilon \,$ pour la signature d'une permutation de $\mathfrak{S}_n \,$
$P: \begin{matrix}\mathfrak{S}_n \times C_k^n & \rightarrow & C_k^n \\(s,(x_1,x_2,...x_n)) & \mapsto & (x_{s(1)},x_{s(2)},...x_{s(n)})\end{matrix}$

(où $C_k^n$ désigne $C_k \times C_k \times ... \times C_k$ )

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).

$* \,$ 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

Isomorphisme $\mbox{entre} \, H \,\mbox{et} \, (C_3^8 \rtimes_P \, \mathfrak{S}_8) \times (C_2^{12} \rtimes_P \, \mathfrak{S}_{12})$

Permutation des arêtes et des sommets

On associe au Rubik's cube une numérotation des faces et une autre pour les sommets.
On définit $\rho : H \rightarrow \mathfrak{S}_8 \,$ la permutation concernant les sommets et $\sigma : H \rightarrow \mathfrak{S}_{12} \,$ celle des arêtes.
On a $\forall (g,h) \in H^2, \rho (g*h) = \rho(g) * \rho(h) \,$ et de même $\forall (g,h) \in H^2, \sigma (g*h) = \sigma(g) * \sigma(h) \,$ .
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

Pour chacun des sommets du cube, on place un marqueur noté $\star$ qui permet de déterminer son orientation .

Emplacement des marqueurs :

Pour les sommets :
Pour les arêtes :
L'orientation sera alors le nombre de rotations de 120° à effectuer sur le cube pour rétablir la place du marqueur $\star \,$ et on définit $\vec{v} \, : \, H \rightarrow C_3^8$ tel que $\vec{v}(g \,)$ soit la réorientation des coins associée au mouvement $g \in H \,$ .

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

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
,
l'application $ι$ 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

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

$\varepsilon(\rho(g))=\varepsilon(\sigma(g)) \,$

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)$

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

$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)$

Idem que précédemment en remplaçant $ρ$ par $σ$

Démonstration de la réciproque

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)$

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)$

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]]} \,$

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)$

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

(A approfondir)

v,r,w,s quelconques

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

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$ où $\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} \,$

Bibliographie

- Introduction - Notations utilisées - Décomposition des mouvements du cube - Bibliographie

Les océans de la Terre n'avaient autrefois pas du tout la même couleur 🌊

Une cartographie inédite révèle la consommation énergétique du cerveau 🧠

Des chercheurs ont intercepté et décodé "facilement" des messages sous-marins depuis les airs ✈️

Voici pourquoi les femmes ressentent plus de douleur chronique que les hommes 🧐

Un immense iceberg se détache et révèle ce surprenant écosystème caché depuis des siècles 🦑

Un colibri imite une chenille pour survivre: découvrez cette stratégie étonnante 🐦

Cette forme de vie géante ne ressemble à rien d'autre de connu 🌎

Recherche: cette nouvelle molécule se montre terriblement efficace contre la calvitie 🔬

Des tardigrades génétiquement modifiés pour survivre... sur le Soleil ☀️

Or, cuivre... pourquoi ces métaux précieux se trouvent dans les zones de subduction ? 🌋

Une avancée majeure dans la supraconductivité à haute température 🌡️

Les chimpanzés fabriquent leurs outils comme des ingénieurs 🛠️

Mach 16: des surprises physiques découvertes dans les vols hypersoniques 🚀

Des scientifiques ont réussi à filmer la séparation des brins de l'ADN 🧬

Comment 13 degrés peuvent transformer une foule en chaos ? 🚶‍♂️

Découverte: les phoques savent évaluer la quantité d'oxygène dans leur sang 🤿

Les trous noirs pourraient-ils protéger la vie dans l'Univers ? 🌱

Implants mammaires en silicone: une toxicité remise en question

Découverte d'un "broyeur d'étoiles" dans notre galaxie 🌀

Neandertal et Sapiens: une collaboration inattendue il y a 100 000 ans 🤝

Que sont ces sphères noires découvertes sur Mars ? 🔴

Découverte: les champignons contre... la grippe 🍄

Découverte inédite: voici comment notre cerveau attache les souvenirs entre eux 🖇️

Découverte: les requins émettent des sons ! 🦈

Des scientifiques inventent un ciment qui aspire le CO2 🌎

Comment le cerveau décode le temps: du récit aux réseaux neuronaux 🕰️

Horloge atomique dans son smartphone et GPS 1000 fois plus précis ⏱️

L'ocytocine: l'hormone de l'amour ou simple mythe ? 💕

Cette nouvelle méthode permettrait d'identifier une vie extraterrestre inattendue 👽

Une araignée géante filmée dans les abysses de l'Antarctique 🕷️

Trois familles d'objets planétaires identifiées dans le Système Solaire externe 🔭

Découverte d'une griffe géante à 2 doigts appartenant à une nouvelle espèce de dinosaure 🦖

Un nouvelle technologie de vaisseaux nucléaires pour explorer le Système solaire 🚀

Votre cerveau se consomme lui-même pour rechercher de l'énergie, pendant un exercice intense 🏃

Des vestiges organiques découverts sur Mars 🧐

Pourquoi les armes nucléaires sont-elles si difficiles et dangereuses à produire ? 💥

MRAM: la mémoire informatique du futur enfin là ? ⚡

Vidange d'un lac glaciaire: la catastrophe du Sikkim en 2023 expliquée 🌊

Qu'est-ce qui a bien pu creuser ces tunnels il y a plusieurs millions d'années ? ⛏️

Les secrets biologiques de Maria Branyas Morera, la supercentenaire 🕰️

Exploiter la rotation terrestre pour produire de l'électricité: l'énergie verte de demain ? ⚡

Que nous apprennent ces émissions radioactives de météorites lunaires et martiennes ? ☢️

La Chine dévoile un processeur quantique fiable à 99.9% 🚀

Voici les emblématiques espèces éteintes que la science pourrait bientôt ressusciter 🦣

Un poisson de 15 millions d'années incroyablement préservé 🐟

Existence démontrée d'un lien entre muscles, cerveau et fertilité 💪

Prévision météo: une petite IA surclasse les plus gros supercalculateurs 🌤️

Cette fosse commune révèle une histoire de violence extrême et de respect ⚔️

Cette nouvelle cellule solaire dure 10 fois plus longtemps 🌞

Des poulets aux plumes de dinosaures: une expérience génétique étonnante 🐔

Page générée en 0.168 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales
Version anglaise | Version allemande | Version espagnole | Version portugaise