Utilisateur:Edocoh/Brouillon
Construction le groupe du Rubik's Cube G
modifierOn oriente le Cube ainsi:
Haut=blanc, Bas=jaune, Avant=vert, Postérieur=klein, Gauche=orange, Droite=rouge.
I) Les configurations
modifierOn pose:
G+ = S12 x Z212 x S8 x Z38
où
Sn = les permutations à n objets
Zk = le groupe modulo k (Z/kZ,+)
s=(u,x,v,y) €G+, u€S12, x€Z212 ,v€S8, y€Z38
x = (x1, x2, ... , x12)
xi = 0,1 si la couleur dominante est sur 0,1
y = (y1, y2, ... , y8)
yi = 0,1,-1 si la couleur dominante est sur 0,1,-1
s.s' = ss' = (u,x,v,y)(u',x'v',y') = (uu',x+u(x'),vv',y+v(y'))
où
uu' = u'ou
u(x) = (xu(1), xu(2), ..., xu(12)) ; permutatuion des xi par u
vv' = v'ov
v(y) = (yv(1), yv(2), ..., yv(8)) ; permutatuion des yi par v
Les éléments de G+ se nomment configuration
(G+,.) le groupe des configurations du Rubik's Cube
II) Le formules
modifierM = <H,B,A,P,G,D>
où H,B,A,P,G,D les rotations de base
Les éléments de M se nomment formule
Une formule V est donc une suite finie de rotations de base respectant la règle :
HH', H'H, BB', B'B, AA',A'A, PP', P'P, GG', G'G, DD', D'D sont interdits dans une formule
On pose : HH' = H'H = BB' = B'B = AA' = A'A = PP' = P'P = GG' = G'G = DD' = D'D = I
exemple:
HDH'D'APG² ; OK
DHH'PAG ; interdit car HH'
Dans M on munit la loi concaténation '.'
1) V,T ==> VT∈M ;loi interne
2) IV = VI = V ; I=élément neutre
3) V = HDH'D'APG² ==> V' = G'²P'A'DHD'H' ;inverse de V
VV' = V'V = I
4) V,T,S , (VT)S = V(TS) ; associativité
(M,.) un groupe
(M,.) le groupe des formules du Rubik's Cube
III) L'action libre
modifierOn définit une action libre '•' de M dans G+ ainsi
G+ x M --> G+
(s,V) --> s•V = t
Vérifiant les 4 axiomes suivants:
A1: s•I = s ; élément neutre
A2: (s•V)•T = s•(VT) ; associativité
A3: a donné, fixé
a•V=a ==> V=I ; librement
A4: s•(VT) = (s•V)(s•T) ; compatibilité
IV) Le groupe du Rubik's Cube
modifierPar définition : le groupe du Rubik's Cube G est :
G = {s∈ G+ | s=e•V , V∈ M} ; e=configuration résolu
Les éléments de G se nomment état
G = ce sont des configurations provenant de M (à partir de e) .
V) Théorème fondamental
modifiers=(u,x,v,y) ∈G+, On pose :
(F) x=0 (mod 3) ; la loi des flips
(T) y=0 (mod 3) ; la loi des twists
(P) sig(u) = sig(v)
Les lois (F),(T),(P) nous montrent le nombre de contraintes est N=2.3.2
Théorème fondamental de la Cubologie :
G = {s∈ G+| s vérifie (F),(T),(P)}
G = ce sont des configurations vérifiant les lois (F), (T), (P).
On a:
G = G+ / N
G = S12 x Z210S8 x Z37
|G| = |G+| / N = 43 252 003 274 489 856 000
VI) Les permutations (des autocollants)
modifierSoient X = {1,2, ..., 48} les autocollants (stickers) numérotés et SX = S48 les permutations de X .
On définit un morphisme de M sur S48 ainsi :
M --> S48
V --> pV
vérifiant :
B1) pI = id
B2) pVT = pV pT
B3) pv = pT ==> V=T
donc à chaque rotation de base {H,B,A,P,G,D} on associe les permutations :
H --> pH , B --> pB, ...
pH = (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
pB = (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);
pA = (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);
pP = (6,38,22,40)(30,14,46,16) (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
pG = (4,12,20,14)(28,36,44,38) (3,39,13,27)(21,11,41,5)(23,37,43,25);
pD = (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);
Et on pose :
Λ = < pH, pB, pA, pP, pG ,pD > ⊂ S48
On a: |G| = |Λ| = |M|
VII) Les J-conjugaison-classes
modifierSoit J le groupe des isométries du cube (ce groupe a 48 éléments)
On définit une action libre '•' de J dans G ainsi
G x J --> G
(s,f) --> e•(fVf-1) , où s=e•V , V∈M
Vérifiant les 4 axiomes suivants:
A1: s•id = s ; élément neutre
A2: (s•f)•g = s•(fg) ; associativité
A3: a donné, fixé
a•f=a ==> f=id ; librement
A4: s•(fg) = (s•f)(s•g) ; compatibilité
On associe à '•' la relation d'équivalence ~ ainsi définie:
s = e•V ,V∈M
s ~ t ssi ∃ f ∈J tel que e•(fVf-1) = t
les classes de cette relation se nomme les J-conjugaison-classes.
La formule de Burnside nous donne le nombre d'orbites ou de J-conjugaison-classes, w:
Ff = { s∈G | e•(fVf-1) = s }
L'ensemble des points fixes de de f
Ff = { s∈G | e•(fVf-1) = e•V }
Ff = { s∈G | fVf-1 = V }
Ff = { V€M | fV = Vf }
On montre alors il y a w = 901 083 404 981 813 616 nombre de J-conjugaison-classes
Voici un script en GAP qui permet de calculer les J-conjugaison-classes :
#gap_J-rubik-burnside.txt
# 5 6 7
# 4 H 8
# 3 2 1
#25 28 23|21 26 19|17 32 31|29 30 27
#38 G 36|12 A 10|34 D 40|16 P 14
#43 44 37|39 42 33|35 48 45|47 46 41
# 11 18 9
# 20 B 24
# 13 22 15
#H=49,B=50,A=51,P=52,G=53,D=54
# Iso=le groupe isometrie du cube
j1 := (6,46,18,26)(8,14,24,12)(38,48,36,32)(2,30,22,42)(16,20,10,4)(28,40,44,34)
(5,45,11,17)(7,13,9,3)(21,31,41,35)(43,33,23,29)(1,25,15,37)(47,39,19,27) ;
j2 := (6,16,22,14)(8,24,20,4)(38,30,40,46)(2,10,18,12)(28,32,48,44)(34,42,36,26)
(5,31,15,43)(7,45,13,25)(21,19,33,39)(1,35,11,23)(47,41,27,29)(3,17,9,37);
Iso := Group(j1,j2) ;
# Dep=le groupe isometrie+ du cube (24) Dep = ssg de Iso
d1 := (1,11)(2,18)(3,9)(4,24)(5,15)(6,22)(7,13)(8,20)(10,12)
(14,16)(17,37)(19,39)(21,33)(23,35)(25,45)(26,42)(27,47)(28,48)(29,41)
(30,46)(31,43)(32,44)(34,36)(38,40);
d2 := (1,15)(2,22)(3,13)(4,20)(5,11)(6,18)(7,9)(8,24)(10,16)(12,14)
(17,45)(19,47)(21,41)(23,43)(25,37)(26,46)(27,39)(28,44)(29,33)(30,42)
(31,35)(32,48)(34,40)(36,38) ;
d3 := (1,17,19)(2,32,10)(3,31,33)(4,40,42)
(5,45,39)(6,48,12)(7,35,21)(8,34,26)(9,23,29)(11,25,47)(13,43,41)
(14,22,44)(15,37,27)(16,18,28)(20,38,46)(24,36,30);
d4 := (1,35,11,23)(2,10,18,12)(3,17,9,37)(4,8,24,20)(5,31,15,43)
(6,16,22,14)(7,45,13,25)(19,33,39,21)(26,34,42,36)(27,29,47,41)
(28,32,48,44)(30,40,46,38) ;
Dep := Group(d1,d2,d3,d4) ;
# Rubik=le groupe du Rubik's Cube
pH := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
pB := (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);
pA := (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);
pP := (6,38,22,40)(30,14,46,16) (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
pG := (4,12,20,14)(28,36,44,38) (3,39,13,27)(21,11,41,5)(23,37,43,25);
pD := (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);
Rubik := Group(pH,pB,pA,pP,pG,pD);
# Pocket=le groupe Pocket (= Rubik sans arêtes)
#pH := (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
#pB := (9,15,13,11)(33,45,41,37)(35,47,43,39);
#pA := (1,35,11,23)(17,9,37,3)(19,33,39,21);
#pP := (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
#pG := (3,39,13,27)(21,11,41,5)(23,37,43,25);
#pD := (1,29,15,33)(17,31,45,35)(19,7,47,9);
#Pocket := Group(pH,pB,pA,pP,pG,pD);
G := Rubik ;;
GG := "Rubik" ;;
J := Iso ;;
JJ := "J" ;;
Jcjg := Sum(J,f -> Size(Centralizer(G,f))) / Size(J);;
Print("\n\n ",GG," = ", Size(G), "\n" );
Print("\n ",JJ,"-cjg = ", Jcjg, "\n" );
Programme 2
#gap_J-rubik.txt
# 5 6 7
# 4 H 8
# 3 2 1
#25 28 23|21 26 19|17 32 31|29 30 27
#38 G 36|12 A 10|34 D 40|16 P 14
#43 44 37|39 42 33|35 48 45|47 46 41
# 11 18 9
# 20 B 24
# 13 22 15
#H=49,B=50,A=51,P=52,G=53,D=54
# Iso=le groupe isometrie du cube (48)
j1 := (6,46,18,26)(8,14,24,12)(38,48,36,32)(2,30,22,42)(16,20,10,4)(28,40,44,34)
(5,45,11,17)(7,13,9,3)(21,31,41,35)(43,33,23,29)(1,25,15,37)(47,39,19,27) ;
j2 := (6,16,22,14)(8,24,20,4)(38,30,40,46)(2,10,18,12)(28,32,48,44)(34,42,36,26)
(5,31,15,43)(7,45,13,25)(21,19,33,39)(1,35,11,23)(47,41,27,29)(3,17,9,37);
Iso := Group(j1,j2) ;
# Dep=le groupe isometrie+ du cube (24) Dep = ssg de Iso
d1 := (1,11)(2,18)(3,9)(4,24)(5,15)(6,22)(7,13)(8,20)(10,12)
(14,16)(17,37)(19,39)(21,33)(23,35)(25,45)(26,42)(27,47)(28,48)(29,41)
(30,46)(31,43)(32,44)(34,36)(38,40);
d2 := (1,15)(2,22)(3,13)(4,20)(5,11)(6,18)(7,9)(8,24)(10,16)(12,14)
(17,45)(19,47)(21,41)(23,43)(25,37)(26,46)(27,39)(28,44)(29,33)(30,42)
(31,35)(32,48)(34,40)(36,38) ;
d3 := (1,17,19)(2,32,10)(3,31,33)(4,40,42)
(5,45,39)(6,48,12)(7,35,21)(8,34,26)(9,23,29)(11,25,47)(13,43,41)
(14,22,44)(15,37,27)(16,18,28)(20,38,46)(24,36,30);
d4 := (1,35,11,23)(2,10,18,12)(3,17,9,37)(4,8,24,20)(5,31,15,43)
(6,16,22,14)(7,45,13,25)(19,33,39,21)(26,34,42,36)(27,29,47,41)
(28,32,48,44)(30,40,46,38) ;
Dep := Group(d1,d2,d3,d4) ;
# Rubik=le groupe du Rubik's Cube
pH := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
pB := (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);
pA := (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);
pP := (6,38,22,40)(30,14,46,16) (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
pG := (4,12,20,14)(28,36,44,38) (3,39,13,27)(21,11,41,5)(23,37,43,25);
pD := (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);
Rubik := Group(pH,pB,pA,pP,pG,pD);
# Pocket=le groupe Pocket (= Rubik sans arêtes)
#pH := (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
#pB := (9,15,13,11)(33,45,41,37)(35,47,43,39);
#pA := (1,35,11,23)(17,9,37,3)(19,33,39,21);
#pP := (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
#pG := (3,39,13,27)(21,11,41,5)(23,37,43,25);
#pD := (1,29,15,33)(17,31,45,35)(19,7,47,9);
#Pocket := Group(pH,pB,pA,pP,pG,pD);
G := Rubik ;;
GG := "Rubik" ;;
J := Iso ;;
JJ := "J" ;;
etat := 0 ;;
Jcjg := 0 ;;
# Les classes des sous groupes conjugaisons de J
Cl := ConjugacyClassesSubgroups( J );;
ptfixe := [];
Print("\n\n No \tetat \tclasses-conjugaisons\n" );
Print("================================================== \n" );
# pour toute classe Cl[i], on cherche les pt fixes générés par Cl[i]
for i in [Length(Cl),Length(Cl)-1..1] do
# prendre un représentant
H := Representative( Cl[i] );
# les pt fixes engendrés par H
aux := Size( Centralizer( G, H ) );
# si Q inclus dans H,on supprime dans H les pt fixes générés par Q
for k in [Length(Cl),Length(Cl)-1..i+1] do
for Q in Elements( Cl[k] ) do
if IsSubgroup( Q, H ) then
aux := aux - ptfixe[k];
fi;
od;
od;
# sauver les pt fixes génégrés par H
ptfixe[i] := aux;
# print N° classe
Print("\n ", i, ":\t" );
# le nbr de pt fixes (= nbr états) générés par Cl[i]
Print( Size(Cl[i]) * ptfixe[i], "\t" );
etat := etat + ( Size(Cl[i]) * ptfixe[i] );
# le nbr de J-cjg classes générés par Cl[i]
Print( (Size(Cl[i]) * ptfixe[i]) / Index(J,H), " " );
Jcjg := Jcjg + ( (Size(Cl[i]) * ptfixe[i] )/ Index(J,H) );
od;
Print("\n\n ",GG," = ", etat, "\n" );
Print("\n ",JJ,"-cjg = ", Jcjg , "\n" );