Théorie mathématique sur le Rubik's Cube
Un article de Wikipédia, l'encyclopédie libre.
Cet article présente le modèle mathématique relatif au Cube de Rubik.
Sommaire |
[modifier] Notations utilisées
- le groupe des mouvements légaux (sans démonter le cube !)
- le groupe élargi (ici on peut faire sauter le cube)
- le groupe symétrique d'ordre n
- comme symbole pour le produit semi-direct
- pour la signature d'une permutation de
(où désigne )
- Les rotations d'un quart de tour dans le sens direct sont appelées , , , , , pour les faces
droite (right), haut (up), gauche (left), avant (front), arrière (back) et bas (down).
- l'opérateur de composition (avec ).
[modifier] Décomposition des mouvements du cube
[modifier] Isomorphisme
[modifier] Permutation des arêtes et des sommets
On associe au Rubik's cube une numérotation des faces et une autre pour les sommets.(Je vais scanner une image pour indiquer les conventions choisies.)
On définit la permutation concernant les sommets et celle des arêtes.
On a et de même .
En utilisant la notation des cycles, on a et , d'où . (attention : la notation des cycles est davantage adaptée à la loi : si , on a et )
[modifier] Orientation des arêtes et des sommets
Pour chacun des sommets du cube, on place un marqueur noté 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 et on définit tel que soit la réorientation des coins associée au mouvement .
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 : . On a :
et
Exemple : , , et
et
[modifier] L'isomorphisme
Soit , on définit l'opération par :
.
L'application est un isomorphisme.
En effet, étant donné que
,
l'application ι est un morphisme.
De plus, elle est injective car (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 ), on peut parvenir à n'importe quelle configuration du Rubik's Cube.
[modifier] Théorème fondamental : Caractérisation des mouvements légaux
Soit .
.
[modifier] Démonstration de la partie directe
[modifier]
Soit .
On a et . On écrit , où est un mouvement parmi ,,,, et .On démontre que pour chacun de ces mouvements, que . Etant donné que , , sont des morphismes, on a alors :
.
[modifier]
Vérifions que cette relation est valable pour les six rotations "de base" :
(2,0,0,1,1,0,0,2) | |
(0,0,0,0,0,0,0,0) | |
(0,0,0,0,0,0,0,0) | |
(0,1,2,0,0,2,1,0) | |
(1,2,0,0,2,1,0,0) | |
(0,0,1,2,0,0,2,1) |
Il est immédiat que et que si deux familles et vérifient b), alors la famille vérifie b) également.
On écrit le mouvement g de la même manière que précédemment (), 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 ).
Supposons k>1. On a . étant une permutation de , vérifie b), de plus d'après l'hypothèse d'induction , le vérifie également. Comme leur somme le vérifie, on obtient la relation.
[modifier]
Idem que précédemment en remplaçant ρ par σ
[modifier] Démonstration de la réciproque
Soit 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.
[modifier] v quelconque,
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
[modifier] w quelconque,
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).
[modifier] v et w quelconques,
Soit défini par , et définis par et .
, alors comme est bijective, on en déduit : c'est la composée de deux mouvements "légaux", donc .
[modifier] r et s quelconques,
On montre en utilisant la relation a) que ce mouvement appartient à
(A approfondir)
[modifier] v,r,w,s quelconques
Soit vérifiant a) b) et c). Alors et chacun de ces trois mouvements est légal, donc .
[modifier] Calcul du cardinal du groupe des mouvements du Rubik's Cube
- On élargit le groupe en supprimant la condition a) par
.
On définit sur l'opération par .
est un groupe :
-
- est interne
- l'associativité de :
- est évidente pour et
- découle (pour et ) du fait que (attention à l'opération )
- est élément neutre
- est l'inverse de
- est isomorphe à
avec ,
ie , où désigne la classe d'équivalence de x dans .
On obtient ainsi ,
et on en déduit
- et
Soit , on a .
- Montrons que est un sous-groupe normal de .
- D'après la caractérisation des sous-groupes, est un sous-groupe de .
- .
- on a .
- comme , alors les propriétés b) et c) sont vérifiées par (structure de groupe).
Donc , et le groupe quotient existe.
- Calcul de l'indice de dans :
Soit la relation définie par
Soit et où est une transposition.
Soit , on a , d'où .
On en déduit que l'indice de dans est .
D'après le théorème de Lagrange,
[modifier] Générateurs et relations
[modifier] Bibliographie
- [pdf] Mathematics of the Rubik's Cube, W.D. Joyner