Générateurs et relations dans le groupe du rubik's cube

Générateurs et relations dans le groupe du rubik's cube: Générateurs et relations dans le groupe du Rubik's Cube

Il est possible de faire une représentation mathématique du Cube de Rubik, un casse-tête qui fut en son temps très populaire. Cet article fait partie d'une série sur la théorie mathématique du Rubik's Cube.

Sommaire

1 Introduction

1.1 Notations utilisées

2 Présentation du problème

2.1 Définition d’un mot

2.2 Intérêt dans le Cube de Rubik

2.3 Première application : nombre minimum de mouvements

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

4 Produit semi–direct

4.1 Définition

4.2 Recherche d’une présentation de

5 Application

6 Liens externes

Introduction

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

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

Présentation du problème

Définition d’un mot

Soit X un ensemble $X=\{x_1 , x_2 ,... , x_n \}\,$ et un autre ensemble disjoint noté $X^{-1}=\{x_1^{-1},...,x_{n}^{-1}\}$ tel que pour tout élément de ces ensembles, $x_k*x_k^{-1}=1$ (élément neutre), avec $x_k^0=1$ . Un mot est une séquence composée des éléments de $X \cup X^{-1} \,$ pondérés d’une puissance $e_i=\{-1,0,1\}\,$ . Un mot s’écrit $w=x_1^{e_1}...x_N^{e_N}$ et le mot inverse est définit ainsi : $x_N^{-e_N}...x_1^{-e_1}$ 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 $x*x^{-1} \,$ . Si $w = y_1^{e_1}...y_N^{e_N}$ est un mot réduit, on définit alors la longueur de $w$ par $l (w) = N$ .

Intérêt dans le Cube de Rubik

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 (la permutation appliquée au cube résolu). En partant de l’identité, on peut construire une suite ( $S n$ ) qui à chaque étape est égal au nombre de position possible du cube réalisable avec n mouvements de base. On a $S 0 = 1, S 1 = 18, S 2 = 18 * 18 + 27$ et ensuite pour tout n, on a $S n = 12 S n - 1 - 18 S n - 2$ . 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 $S n - 1$ mouvements possible plus les 18 que l’on peut effectuer sur $S n - 2$ 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 $(S n)$ 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 groupe

Le groupe libre sur les générateurs éléments de $X$ , noté $F X$ est le groupe des mots réduits de $X$ .
Dem : $(F_X, \circ )$ est un groupe :

la loi $\circ$ est interne au groupe (la loi $\circ$ é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 $y_1^{e_1}...y_N^{e_N}$ est inversible d’inverse $y_N^{-e_N}...y_1^{-e_1}$ .

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

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 $F n$ contenant Y. R constitue l’ensemble des relations de $F n$ .

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 $F n$ ) Soit G’ un autre groupe construit sur les mêmes générateurs X satisfaisant les relations de R. On considère $\begin{matrix} \phi : & F_X & & \rightarrow & \ G' \\ \ & w & & \mapsto \ & b_1^{e_1}b_2^{e_2}...b_l^{e_l}\end{matrix}$ (qui à un mot w lui associe sa décomposition selon les générateurs de G’). Cette application est un morphisme de groupe avec $R \subset ker(f)$ 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 à $F n / R$ . 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 $x n = 1$ donc on a $X = {x}$ et $R=\{(x^n)^k | k \in Z\} \subset F_1={x^k | k \in Z}$ . $C n$ admet donc comme présentation: $C n = x | x n = 1$ Le groupe diédral d’ordre n a pour présentation $D n = {a, b | a n = 1, b 2 = 1, a b a = b}$

Produit semi–direct

Définition

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 $(a, b) * (a', b') = (a * a', b * b')$ . 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 $(a, b) * (a', b') = (a * s (b)(a'), b * b')$ .

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 $(C_3^7 \rtimes_P \, \mathfrak{S}_8) \times (C_2^{11} \rtimes_P \, \mathfrak{S}_{12})$ avec comme morphisme $P$ présenté en introduction.

Recherche d’une présentation de $C_m^n \rtimes \, \mathfrak{S}_{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: $\mathfrak{S}_{n+1} = <a_1,...,a_n | (a_ia_j)^{m_{i,j}}=1 , 1\le i,j\le \, n>$ avec $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 : $\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 : $C_m^n = <h_1,...,h_n) | h_i^m = 1, h_i*h_j = h_j*h_i , 1\le i,j \le n>$

Pour le groupe symétrique, on peut associer à chaque transposition (de deux indices consécutifs) $a i$ une matrice de permutation de taille (n+1)*(n+1) $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 $s i = I - E i i - E i + 1, i + 1 + E i, i + 1 + E i + 1, i$

On peut aussi identifier $C_m^n$ avec le produit cartésien $\{(h_1(x_1),...,h_n(x_n)) | x_i \in C_m\}$ où $h i (t) = I - E i i - E i + 1, i + 1 + t E i i + t - 1 E i + 1, i + 1$

On a alors les relations suivantes entre les $s i et les h j (t)$ $\begin{matrix} s_ih_j(t)s_i^{-1} = h_j(t), |i-j|>1 \\ s_ih_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 : $(C_m^n \rtimes_P \, \mathfrak{S}_{n+1}) = \left\langle a_1,...,a_n,h_1...,h_n | \left\{\begin{matrix} {(a_ia_j)}^{m_{ij} } =1 \\ h_i^m = 1, h_ih_j = h_jh_i \\ a_ih_ja_i^{-1}=h_j, |i-j|>1 \\ a_ih_ia_i^{-1}=h_i^{-1} \\ a_{j \pm 1} h_ja_{j \pm 1} = h_ih_{j \pm 1} \end{matrix} \right. \right\rangle$

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

En considérant maintenant $H=\{h_1,...,h_n | h_i^m=1, h_ih_j=h_jh_i\} \subset P$ , $H \,$ est un sous groupe normal à $P \,$ . En effet, chaque $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 $\{a_ih_ja_i^{-1} | 1 \le i,j \le n\}=H$ . On a donc $H \cong C_m^n$ . Si $w = W (a 1,..., a n, h 1,..., h n) = 1$ est une relation de P, le mot $w \,$ écrit dans le groupe quotient $P / H$ devient un mot qui ne contiendra plus que des relations du type ${(a_ia_j)}^{m_{ij} }=1$ . On peut montrer ainsi que $P/H \cong S_{n+1}$ (cette partie de la démonstration sera précisée).

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

Application

Dans le cadre de Caml A) Recherche d’un groupe de générateurs du Cube autre que les 6 usuels

On peut montrer que en réalité, on n’a besoin que de 5 car le 6e peut s’exprimer en fonction des 5 autres. Peut-on trouver un ensemble encore plus petit ? Mouvements de Barns : montrer avec le programme de Guix que l'on peut retrouver les mouvements de bases RU etc.

Dénombrement du groupe à partir des relations du produit semi direct

Liens externes

[pdf] http://web.usna.navy.mil/~wdj/papers/rubik.pdf

Portail des mathématiques

Portail des jeux

Ce document provient de « G%C3%A9n%C3%A9rateurs et relations dans le groupe du Rubik%27s Cube ».

Catégories : Rubik's Cube | Théorie des groupes

Contenu soumis à la licence CC-BY-SA. Source : Article Générateurs et relations dans le groupe du rubik's cube de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Generateurs et relations dans le groupe du Rubik's Cube — Générateurs et relations dans le groupe du Rubik s Cube Il est possible de faire une représentation mathématique du Cube de Rubik, un casse tête qui fut en son temps très populaire. Cet article fait partie d une série sur la théorie mathématique… … Wikipédia en Français
Générateurs Et Relations Dans Le Groupe Du Rubik's Cube — Il est possible de faire une représentation mathématique du Cube de Rubik, un casse tête qui fut en son temps très populaire. Cet article fait partie d une série sur la théorie mathématique du Rubik s Cube. Sommaire 1 Introduction 1.1 Notations… … Wikipédia en Français
Générateurs et relations dans le groupe du Rubik's Cube — Il est possible de faire une représentation mathématique du Cube de Rubik, un casse tête qui fut en son temps très populaire. Cet article fait partie d une série sur la théorie mathématique du Rubik s Cube. Sommaire 1 Introduction 1.1 Notations… … Wikipédia en Français
Theorie mathematique sur le Rubik's Cube — Théorie mathématique sur le Rubik s Cube Cet article présente le modèle mathématique relatif au Cube de Rubik. Sommaire 1 Notations utilisées 2 Décomposition des mouvements du cube 2.1 Isomorphisme … Wikipédia en Français
Théorie mathématique sur le Rubik's Cube — Cet article présente le modèle mathématique relatif au Cube de Rubik. Sommaire 1 Notations utilisées 2 Décomposition des mouvements du cube 2.1 Isomorphisme 2.1.1 … Wikipédia en Français
Théorie mathématique sur le rubik's cube — Cet article présente le modèle mathématique relatif au Cube de Rubik. Sommaire 1 Notations utilisées 2 Décomposition des mouvements du cube 2.1 Isomorphisme … Wikipédia en Français
Groupe (mathématique) — Groupe (mathématiques) Pour les articles homonymes, voir Groupe. Cet article concerne une introduction au concept de groupe. Pour un approfondissement, voir théorie des groupes … Wikipédia en Français
Groupe (mathématiques) — Pour les articles homonymes, voir Groupe. Les manipulations possibles du cube de Rubik forment un groupe. En mathématiques, un groupe est un ensemble … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Générateurs et relations dans le groupe du rubik's cube

Générateurs et relations dans le groupe du Rubik's Cube

Sommaire

Introduction

Notations utilisées

Présentation du problème

Définition d’un mot

Intérêt dans le Cube de Rubik

Première application : nombre minimum de mouvements

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

Produit semi–direct

Définition

Recherche d’une présentation de $C_m^n \rtimes \, \mathfrak{S}_{n+1}$

Application

Liens externes

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Générateurs et relations dans le groupe du rubik's cube

Générateurs et relations dans le groupe du Rubik's Cube

Sommaire

Introduction

Notations utilisées

Présentation du problème

Définition d’un mot

Intérêt dans le Cube de Rubik

Première application : nombre minimum de mouvements

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

Produit semi–direct

Définition

Recherche d’une présentation de

Application

Liens externes

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link

Recherche d’une présentation de $C_m^n \rtimes \, \mathfrak{S}_{n+1}$