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

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

Notations utiliséesModifier

  •   le groupe des mouvements légaux (sans démonter le cube !)
  •   le groupe élargi (ici on peut faire sauter le cube)
  •   l'ensemble des classes d'équivalence pour la congruence modulo n
  •   le groupe symétrique d'ordre n
  •   comme symbole pour le produit semi-direct
  •   pour la signature d'une permutation de  
  •  

(avec   à savoir  )

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

Décomposition des mouvements du cubeModifier

Isomorphisme entre H et  Modifier

Factorisation sommets-arêtesModifier

Un élément de H se décompose naturellement entre ce qu'il fait sur les coins et ce qu'il fait sur les arêtes. On introduit les 2 sous-groupes Hco et Har constitués des mouvements laissant globalement invariants, respectivement, l'ensemble des arêtes et l'ensemble des coins. H est isomorphe au produit de groupes  .

On va maintenant montrer que   et  .

Permutation des arêtes et des sommetsModifier

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   et   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   et  , d'où  . (attention : la notation des cycles est davantage adaptée à la loi   : si  , on a   et  )

Orientation des arêtes et des sommetsModifier

  et   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 ambigüe : 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 à  . Ainsi   et on note   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   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 :  

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 : 

 

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  

L'isomorphismeModifier

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.

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

Soit  

 

Démonstration de la partie directeModifier

ε(ρ(g) = ε(σ(g)Modifier

Soit  .

On a   et  . On écrit  , où   est un mouvement parmi  ,  ,  ,  ,   et  .On démontre que pour chacun de ces mouvements, que  . Étant 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  

Démonstration de la réciproqueModifier

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.

v quelconque,  Modifier

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,  Modifier

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,  Modifier

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  

r et s quelconques,  Modifier

On montre en utilisant la relation a) que ce mouvement appartient à  .

(À approfondir)

v, r, w, s quelconquesModifier

Soit   vérifiant a) b) et c). Alors   et chacun de ces trois mouvements est légal, donc  

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

  • 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  
i.e.  , 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    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,  

soit 43 milliards de milliards de combinaisons.

Générateurs et relationsModifier

Présentation du problèmeModifier

Définition d’un motModifier

Soit X un ensemble   et un autre ensemble disjoint noté   tel que pour tout élément de ces ensembles,   (élément neutre), avec  . Un mot est une séquence composée des éléments de   pondérés d’une puissance  . Un mot s’écrit   et le mot inverse est défini ainsi :   Un mot réduit est soit un mot vide (constitué que de 1) soit un mot pour lequel il n’y a pas deux symboles consécutifs de la forme  . Si   est un mot réduit, on définit alors la longueur de   par   .

Intérêt dans le Cube de RubikModifier

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 mouvementsModifier

À partir de ces mouvements, on peut construire un arbre où chaque nœud représente une position du cube (la permutation appliquée au cube résolu). En partant de l’identité, on peut construire une suite ( ) qui à chaque étape est égal au nombre de position possible du cube réalisable avec n mouvements de base. On a   et ensuite pour tout n, on a  . En effet, pour plus de précision dans le calcul, il ne faut pas compter toutes les permutations qui permettraient de revenir à une position déjà atteinte. Pour cela, il faut donc fixer des conditions (on compte ici les mouvements de la tranche du milieu) : on ne compte pas les positions obtenues par deux mouvements consécutifs sur une même face ni trois mouvements autour du même axe. Dans une situation donnée, il ne reste plus que 12 dans une position de   mouvements possible plus les 18 que l’on peut effectuer sur   qui correspond aux positions où l’on n’a pas répété les mouvements (ou encore les positions où l’on a répété les mouvements pour revenir à une identité). On peut ensuite calculer le terme général de la suite   puis l’égaler à N, le nombre de positions totales possibles du cube afin de déterminer n. On trouve alors n = 17.3 ce qui montre qu’il existe une position du cube qui ne peut pas être atteinte en moins de 18 mouvements. Il a même été prouvé qu'une position (le centre du cube) nécessite 20 mouvements.(Voir Optimal solutions for Rubik's Cube)

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

Le groupe libre sur les générateurs éléments de   , noté   est le groupe des mots réduits de  .
Dem :   est un groupe :

  • la loi   est interne au groupe (la loi   étant définie comme la loi de composition avec en plus une réduction du mot obtenu)
  • admet un élément neutre 1
  • associatif (loi de composition sur les permutations)
  • un mot   est inversible d’inverse  .

Définition : on appelle H sous-groupe normal à G si pour tout g de G, on a  .

Soit X un ensemble fini avec n = card X. Soit Y un groupe de mots réduits sur X. Soit R le plus petit sous groupe normal de   contenant Y. R constitue l’ensemble des relations de  .

Dem : Fn/R est un groupe, c’est le plus grand groupe qui satisfait ces relations. Avec les notations précédentes, (G, o ) est par définition un groupe satisfaisant les relations de R (groupe quotient sur  ). Soit G’ un autre groupe construit sur les mêmes générateurs X satisfaisant les relations de R. On considère  (qui à un mot w lui associe sa décomposition selon les générateurs de G’). Cette application est un morphisme de groupes avec   puisque G’ satisfait les relations de R donc f(R) = 1. D’après les théorèmes sur les morphismes, G est une extension de G’ donc G est le plus grand groupe généré par X satisfaisant les relations de R. Soit G un groupe. On dit que G a pour générateurs l’ensemble X et pour relations Y si G est isomorphe à  . 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.

Ex. : le groupe cyclique d’ordre n possède un générateur x et une relation   donc on a   et  .   admet donc comme présentation :   Le groupe diédral d’ordre n a pour présentation  

Produit semi-directModifier

DéfinitionModifier

Produit direct de deux groupes : en considérant deux groupes G et H, le produit direct de G et de H est l’ensemble des couples (a,b) muni d’une loi produit telle que  . Si « G agit sur H », c'est-à-dire s'il existe un morphisme s de G dans A et H, on peut considérer la loi  .

Cas du groupe G : l’intérêt d’une présentation pour ce groupe est que l’on peut établir un isomorphisme entre G et   avec comme morphisme   présenté en introduction.

Recherche d’une présentation de  Modifier

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:  avec   Dans le cas où n=4, la matrice est :  

Pour le produit cartésien du groupe cyclique d'ordre m, on a :  

Pour le groupe symétrique, on peut associer à chaque transposition (de deux indices consécutifs)   une matrice de permutation de taille (n+1)*(n+1)   autrement dit  

On peut aussi identifier   avec le produit cartésien   

On a alors les relations suivantes entre les    

On peut alors démontrer la propriété suivante :  

Démonstration : si on appelle   la représentation présentée ci-dessus. Le but de la démonstration est bien sûr de montrer  . Pour cela on considère le morphisme   qui associe les générateurs de   avec les générateurs de  . Par définition de l'application,   est surjective. Pour prouver l'injectivité, on note  . En notant  , on a d'après le théorème de Lagrange :  .

En considérant maintenant  ,   est un sous groupe normal à  . En effet, chaque   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  . On a donc  . Si   est une relation de P, le mot   écrit dans le groupe quotient   devient un mot qui ne contiendra plus que des relations du type  . On peut montrer ainsi que   (cette partie de la démonstration sera précisée).

Ainsi, on a   ce qui montre   et ainsi   d'où  .   est donc injectif donc bijectif.

Liens externesModifier