Le groupe G(M) du Megaminx

31 Mar 2016

Structure mathématique du Megaminx Le Megaminx a pratiquement la même structure que le Rubik's Cube

1- Notation

Prenez votre Mégaminx et posez le sur la table, comme ceci:.


Les noms des faces... :
H(aut) , B(as), h(aut-opposé) | A(vant) , P(ostérieur) | G(auche) , D(roite), d(roite-opposé)...

Les rotations
A = tourner une fois la face Avant dans le sens positif (sens des aiguilles d'une montre).
A' = tourner une fois dans le sens négatif
A² = tourner deux fois dans le sens positif

On écit (HA) pour désigner le arête Haut-Avant ou (HAD) le sommet Haut-Avant-Droite
(HA)° = pivoter le arête (HA)
(HAD)° = pivoter le sommet (HAD)
Le point '.' ou les parenthèses '(', ')' qui se trouvent dans les formules sont là pour faciliter la lecture c'est tout!!!


2- Rappel

Soient M = < H, B, A, P, G, D, h, b, a, p, g, d > le groupe de mouvements engendré par les 12 rotations de base, et X = {1,2, ...,120} l'ensemble des stickers (sauf les centres) numérotés, M agit sur X, gènère des permutations p dans S120 et on peut couper ces permutations en deux parties ... -Il suffit de suivre les mouvements des stickers-

Construction le groupe G = G(M) du Megaminx

On ne rentre pas dans le détaille dans la contruction (action de M sur les stickers X,...) on passe directement à la phase d'analyse.

- On a 30 arêtes qui baladent partout, donc on a affaire avec S30, mais les arêtes peuvent aussi se pivoter en 2 positions c'est un truc Z230, pour les arêtes tout se passe dans:
S30 x Z230
- De même on a 20 sommets qui baladent partout, donc on a affaire avec S20, mais les sommets peuvent aussi se pivoter en 3 positions c'est un truc Z320, pour les sommets tout se passe dans:
S20 x Z320
Finalement tout se passe dans
G+ = S30 x Z230 x S20 x Z320 c'est l'ensemble de tous les états du cube.
G+ muni la loi suivante, qui lui confère un groupe, le groupe étendu du puzzle
(u,x,v,y)(p,z,q,t) = ( up, x+u(z), vq, y+v(t) )

et un élément de G c'est par définition:
e=(u,x,v,y)∈G+
u ∈S30, x ∈Z230, v ∈S20, y ∈Z320
qui vérifie:
1. ∑ yi = 0 (mod 3) en abrégeant y=0 (mod 3) avec y = (y1,y2,...,y20)
2. ∑ xi = 0 (mod 2) en abrégeant x=0 (mod 2) avec x = (x1,x2,...,x30)
3. sig(u)=sig(v)=1

Il nous reste maintenant à montrer la "connexion" entre M et G, tout celà se fait en plusieurs étapes

Connexion entre M et G

Le but est de montrer la propriété suivante:
Chaque formule gènère un état, chaqu'état provient d'une formule

Chaqu'état provient d'une formule

La démontration est constructive, on construit la formule
On prend donc un élément de G , et il faut trouver une formule dont il provient
e=(u,x,v,y)∈G+ vérifiant les trois conditions (1), (2) et (3)
On va faire ça en plusieurs étapes.
On coupe (u,x,v,y) en plusieurs morceaux

Cas les arêtes: (u,x)=(u,x,id,0)
Soient les 2 formules suivantes:
F1 = G[HA]G' => pivote 2 arêtes
F2 = DHD'. H . DH3D' => glisse 3 arêtes sans perturber l'orientation des arêtes, un 3-cycle
On coupe l'état-arête (u,x) = (1,x)(u,0)

-On utilise F1 (et la conjugaison) , pour pivoter les arêtes une par une , la dernière sera automatiquement et correctement pivotée à cause de x=0 (mod 2)

-On utilise F2 (et la conjugaison), pour glisser toutes les arêtes à leur place c'est possible car F2 est un 3-cycle , et que les 3-cycle engendre A30 (on est dans A30 car sig(u)=1)

Cas les sommets: (v,y)=(1,0,v,y)
Soient les 2 formules suivantes:
F3 = [HA] .P'[AH]P => placer 3 sommets, un 3-cycle
F4 = [HA]² .P'[AH]²P => pivoter 2 sommets
On va couper l'état-sommet (v,y) en plusieurs morceaux, c'est un peu plus compliqué que pour les arêtes.
Voyons:
D'après les formule F3 et F4 ceci nous suggère de couper (v,y) ainsi:
(v,0)(1,y) ce qui donne:
(v,v(y))
mais comme on sait pivoter les sommets , il suffit de corriger le résultat v(y)
On veut
(v,y) = (v,v(y)) (1,z) il faut trouver z
y = v(y) + v(z)
v(z) = y - v(y)
z = v-1(y - v(y))

Finalement on coupe
(v,y) = (v,0)(1,y)(1, v-1(y - v(y)) !!
Vérifions le calcule
(v,0)(1,y) = (v,v(y))
(v,v(y))(1, v-1(y - v(y))
(v,v(y) + vv-1(y - v(y)) )
(v,v(y) + y - v(y) ) = (v,y) huuup!!!

Bref : On place des sommets, si l'orientation change on pivote avec F4

-On utilise F3 (et la conjugaison), pour placer toutes les sommets c'est possible car F3 est un 3-cycle , et que les 3-cycle engendre A20 (on est dans A20 car sig(v)=1)

-On utilise F4 (et la conjugaison) , pour pivoter les sommets, le dernier sera automatiquement bien pivoté à cause de y=0 (mod 3)

Finalement pour trouver une formule pour l'état (u,x,v,y) on fait simplement
- Utiliser les formules F1,F2 pour ranger les arêtes ==> (u,x, . , . )
- Utiliser la formule F3,F4 pour ranger les sommets ==> (.,.,v,y)
Donc l'état (u,x,v,y) correspond bien à une formule

Chaque formule gènère un état

On prend donc une formule L -un élément de M- , la formule gènère un état (u,x,v,y)∈G+, il faut montrer que
1. y=0 (mod 3)
2. x=0 (mod 2)
3. sig(u)=sig(v)=1

(3) ==> Pour une rotation de base, on a sig(u)=sig(v)=1 donc pour une formule on a:
sig(u) x sig(u') x sig(u")... = 1x1x1 ... = 1 et
sig(v) x sig(v') x sig(v")... = 1x1x1 ... = 1

(1)+(2) ==> Parmi les écritures de la formule L qui donne (u,x,v,y) on prend la plus courte (c'est exactement comme 2/4, 4/8, 8/16 ... on prend le plus simple 1/2)
longeur(L)=n, on va raisonner par récurrence sur n
Pour n=1 , on a x=0 (mod 2) et y=0 (mod 3) pour toute rotation de base
Supposons que la propriété soit vraie pour n, montrons qu'elle reste encore vraie pour n+1
Soit Q une formule de longeur n+1, mais on passe de n à n+1 par une rotation de base
Q = LZ avec Z=rotation de base ==> (u',x',v',y') = (u,x,v,y)(p,a,q,b)
x' = x + u(a)
y' = y + v(b)
comme
x=0 (mod 2) l'hypothèse de récurrence
u(a)=0 (mod 2) une permutation ne change pas le modulo de a
d'où
x'=0 (mod 2)
de même
y=0 (mod 3) l'hypothèse de récurrence
v(b)=0 (mod 3)
d'où
y'=0 (mod 3)

Résumer: Toute formule produit un élément de G, tout élément de G provient de M
Remarque :
1. Bien qu'il y ait une bijection entre M et G mais on ne peut pas identifier G=M, en effet, M agit sur G et non le contraire !!!
2. Le Megaminx est un twist LOCALEMENT PAIR (sig(u)=sig(v)=1).

1 [2]

Accueil

DMJ: 31/03/2016









Facile

Moyen

Difficile

Les Crazy

Les Stars

Divers

Théorie des Twists

Quiz (Master Cube)