La face cachée du Rubik's Cube
11
Mar
2013
Structure mathématique du Rubik's Cube
Le Rubik's Cube est célèbre non seulement c'est un casse-tête redoutable
mais aussi parce qu'il matérialise physiquement une théorie mathématique abstrait: Les Groupes
NOTE : Vous trouverez la version pdf ici :
Le groupe du Rubik's Cube (Tome I)
Le groupe du Rubik's Cube (Tome II)
En Rubik's Cube il y a deux notions très importantes à comprendre: la notion de configuration et la notion de formule .
Comme en géométrie avec la notion de 'point', on voit bien ce qu'est un 'point', mais l'expliquer n'est pas évident !
Même chose ici, on voit ce qu'est une configuration et une formule mais les expliquer c'est autre chose.
Les configurations G+
Prenez un Rubik's Cube standard, orientez le, c'est-à-dire dire qui est le Haut, qui est l'Avant .... pour nous ça sera:
H(aut)=b(lanc), B(as)=j(aune), A(vant)=v(ert), P(ostérieur)=k(lein), G(auche)=o(range), D(roite)=r(ouge)
1. Les arêtes et les sommets forment deux clans bien distigues , ils ne se mélangent jamais, une arête ne se met pas à la place d'un sommet et inversement (c'est normal, car physiquement ces pièces sont différentes).
2. On peut permuter ces 12 arêtes entre elles comme on veut, on a donc affaire à S
12 (le groupe des permutations à 12 objets) et chaqu' arête possède 2 orientations.
donc l'orientation des arêtes est codée par un vecteur à 12 composantes à valeur dans {0,1},
on a affaire à Z
212 (Z
2 = un groupe à 2 éléments), finalement pour les arêtes on a S
12 x Z
212
3. Même chose pour les sommets
On peut permuter les 8 sommets entre eux comme on veut, on a donc affaire à S
8 et chaque sommets possède 3 orientations.
donc l'orientation des sommets elle aussi est codée par un vecteur à 8 composantes à valeur dans {0,1,-1},
on a affaire à Z
38, pour les sommets on a S
8 x Z
38
Finalement on pose :
G
+ = (S
12 x Z
212) x (S
8 x Z
38)
C'est l'ensemble des configurations
voici visuellement quelques configurations
|
|
Une configuration |
Une autre configuration |
|
|
Une configuration |
Une autre configuration |
|
|
Une configuration |
configuration résolue (une couleur par face) |
Une configuration est une sorte de motif des autocollants
On remarque que les centres ne sont pas bougés : Haut=blanc, Bas=jaune, Avant=vert, ...
La loi interne '.' dans G+:
On va définir une loi '.' dans G
+ :
s=(u,x,v,y) et s'=(u',x',v',y')
ss' = (u,x,v,y)(u',x',v',y') = (uu', x+u(x'), vv', y+v(y'))
où p(x) = (x
p(1), x
p(2),..., x
p(n)) ; p=permutation, x=vecteur
uu' = u'o u
(G
+, .) est un groupe
une "configuration" est mathématiquement représentée par (u,x,v,y) un 4-uplet
Un exemple :
pour les arêtes
u = (1,3,5,2)(9,11) et x = (x
1, x
2, x
3, x
4, x
5, x
6, x
7, x
8, x
9, x
10, x
11, x
12)
u(x) = (x
3, x
1, x
5, x
4, x
2, x
6, x
7, x
8, x
11, x
10, x
9, x
12)
on permute les x
i par u.
-On a: u(x+x') = u(x) + u(x')
-Parfois on note: 0 = (0,0,...,0) , 1 = (1,1,...,1)
ex (id,0,id,1) ==>
id=permutation identique
0=(0,0,0,0,0,0,0,0,0,0,0,0) vecteur nul
id=identité
1=(1,1,1,1,1,1,1,1) vecteur ayant des 1
Les formules M
On prend un Rubik's Cube monochrome et on le pose sur une table avec une face devant nous, on a donc 6 faces
ainsi nommées:
H(aut), B(as), A(vant), P(ostérieur), G(auche), D(roite)
|
|
Rubik's Cube monochrome |
les rotations de base |
Et les 6 rotations de base: {H, B,A,P,G,D}
A = on tourne la face A 90° dans le sens horaire
A' = on tourne la face A -90° (dans le sens antihoraire)
A² = on tourne la face A 180°
On pose :
M = < H,B,A,P,G,D > , M est engendré par les 6 rotations de base {H,B,A,P,G,D}
M c'est l'ensemble des formules
Une formule est donc une suite finie de rotations de base avec la règle :
HH', H'H, BB',B'B, etc ....est interdit dans une formule
ex:
HDB²PA'GH'D' ==> OK
GHDD'GB'P² ==> interdit à cause DD'
Remarque : M est infini car on peut écrire : AAA, AAAAAA, AAAAAAAAA, ....
Une loi '.' dans M
On définit une loi '.' dans M: '.' = la concaténation : V, T ==> VT
On pose : HH' = H'H = BB' = B'B = etc ....= I
(M, .) forme un groupe en effet
(i) V,T ∈M ==> VT∈M ; loi interne
(ii) IV = VI = V ; I élément neutre
(iii) V = HBA'DGP²D' ==> V' = DP'²G'D'AB'H' ; inverse
(iv) (VT)S = V(TS) ; associative
Action '•' de M sur G+
On définit une action '•' de M dans G
+ ainsi
G
+ x M --> G
+
(s,V) --> s•V = t
Vérifiant les 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é
Remarque : (i) l'Axiome3 montre que deux formules donnant une même configuration seront considérés comme identiques
en effet :
a donné, fixé
a•V = a•T
(a•V)•T' = (a•T)•T'
a•(VT') = a•(T•T')
a•(VT') = a•I = a
a•(VT') = a
VT' = I ==> V = T ; (A3)
Exemples:
A' = A
3
A
4 = I
A'B²AH²A'B²AH² = H²DBD'H²DB'D'
A
4 = D
4
(H²D²)
3(B²D²)
3 = (H²G²)
3(B²G²)
3
B = (DG'A²P²DG') H (DG'A²P²DG')
(ii) L'axiome3 rend M fini .
On a vu qu'on peut écrire :
A', AAA, AAAAAA, .... M aura donc une infinité d'éléments, or on sait que le groupe du Rubik's Cube est fini, on aimerait donc que M lui aussi soit fini, et avoir le même
nombre d'éléments que le goupe du Rubik's Cube. Pour arriver on doit passer par ce qu'on appelle le groupe libre ....
Groupe libre
On se donne 2 ensembles finis X={a,b,c,d,...}, X'={a',b',c',d',...}
disjoints et en bijection a -> a' , b -> b'... et un élémént 1 non dans X et X'. On forme les mots de X c'est-à-dire les suites finies d'éléments de X et X'
avec la règle: aa', a'a, bb', b'b, cc', c'c, ... interdits
du genre
V = abd'b²c ; OK
T = c'dab'bd² ; interdit à cause b'b
Soit F
X l'ensemble des mots de X ,
On pose :
aa' = a'a = bb' = b'b = cc' = c'c ... = 1
et on prend par définition :
1. 1 = élément neutre,
2. a' ==> symétrique de a
3. V=ab'dc ==> V'=c'd'ba' symétrique de V
4. F
X muni la loi concaténation :
V,T ∈F
X ==> VT = N (on supprime bien sûr les a'a, aa', b'b, bb', .... dans N)
V = acb'd , T = d'cb²a ==> VT = acb'dd'cb²a = acb'cb²a
F
X forme ainsi un groupe nommé
groupe libre engendré par X
Soit maintenant L un groupe fini, et f un morphisme injective de F
X -> L :
f: F
X -> L ; f injectif
V -> f(V)
et une relation d'équivalznce
V,T ∈F
X , V~T ssi V,T ∈Ker(f)
alors on a:
F
X/~ = F
X/Ker(f) = F
X ≅ Im(f) (th: F
X/Ker(f) ≅ Im(f))
Pour nous
X = {H,B,A,P,G,D} , F
X = M
L = G
+
f: M -> G
+
f(V) = e•V ; e=état résolu
V,T ∈M , V~T ssi V,T ∈Ker(f))
et
M/~ = M/Ker(f) = M ≅ Im(f) ⊂ G
+ fini
il est plus facile, et plus compréhensible de manipuler
M = < H, B, A, P, G, D > ; avec la convention V=T si V,T donnent la même configuration
que de manipuler des classes d'équivalences.
M/~
Remarque
ΓA signifie on fait la rotation Γ puis la rotation A et ΓA ≠ AΓ
|
|
ΓA |
AΓ |
Le groupe du Rubik's Cube (G, .)
Par définition le groupe du Rubik's Cube est :
G = {s∈G
+ / s=e•V , V∈M} , e=état résolu
Ce sont des configurations provenant de M (à partir de e), les éléments de G se nomment les états,
G est un sous groupe de G
+
Théorème fondamental de la Cubologie
On se pose la question suivante : Quelles sont les conditions nécessaires et suffisantes pour qu'une configuration soit un état ?
On pose :
s=(u,x,v,y) ∈G
+ avec:
(F) x=0 (mod 2)
(T) y=0 (mod 3)
(P) sig(u) = sig(v)
On démontre alors le théorème suivant:
G = {s∈G
+ / s vérifie (F), (T), (P)}
Ce sont des configurations vérifiant (F), (T), (P),
Les rotations étendues
Rotation Γ : pivoter une arête .
1. On enlève l'arête (HA)
2. La pivote (180° ou -180°)
3. Puis on la remet
|
|
Rotation étendue Γ |
|
Par définition ce manoeuvre se nomme rotation étendue Γ qui a comme résultat , l'arête (HA) est pivotée (180° ou -180°)
(HA)° = (HA)
+ = (HA)
- = Γ
Rotation Ψ : pivoter un sommet .
1. On enlève le sommet (HDA)
2. Le pivote 1/3 tour dans le sens horaire (120°)
3. Puis on le remet
|
|
Rotation étendue Ψ |
|
Ce manoeuvre , par définition , se nomme rotation étendue Ψ qui a comme résultat, le sommet (HDA) pivoté 1/3 de tour dans le sens horaire (120°)
(HDA)
+ = Ψ
Rotation Ω : permuter deux arêtes .
1. On enlève les arêtes (HA), (HD)
2. Permute (HA)<->(HD) = (HA,HD)
3. Puis on les remet
|
|
rotation étendue Ω |
|
Ce manoeuvre , par définition , se nomme rotation étendue Ω qui a comme résultat, les arêtes (HA) , (HD) sont permutées
(HA)<->(HD) = (HA,HD) = Ω
Ce sont des manoeuvres impossible à réaliser sans enlever les pièces.
Les "rotations" Γ, Ψ, Ω , par définition appellées rotations étendues (les rotations étendues sont des rotations qui violent les lois de Rubik's Cube).
On note M
+ l'ensemble des formules étendues
M
+ = < H, B, A, P, G, D ,Γ, Ψ, Ω > , M
+ est donc engendré par les 6 rotations de base et les 3 rotations étendues.
Rappel : deux formules donnant la même configuration seront considèrées comme identiques.
M ⊂ M
+
Le groupe (M+, .)
L'ensemble des formules étendues M
+ muni la concaténation '.' de deux formules forme un groupe (M
+, .) , en effet on a:
M = < H,B,A,P,G,D > (engendré par {H, B, A, P, G, D}) est un sous groupe de M
+ .
Finalement : il y a 2 concepts importants il faut bien comprendre et maitriser et ne pas confondre.
concept: configuration (==> état)
concept: formule
L'ensemble X des autocollants
Soit X = {1,2,3, ..., 48} l'ensemble des autocollants numérotées comme indique la fig ci-dessous
Notre but c'est de numéroter les autocollants de telle sorte qu'on puisse les regrouper facilement pour former les arêtes et les sommet
*Pour les arêtes: les autocollants pairs .
On commence par les facettes dominantes : 2,4,6,8, ...
Puis les autres facettes
*Pour les sommets: les autocollants impairs .
On commence par les facettes dominantes : 1,3,5,7, ...
Puis les autres facettes dans le sens horaire.
x
i = (2i, 2i+24) , y
i = (2i-1, 4i+13, 4i+15)
|
|
L'ensemble des autocollants X |
L'ensemble des autocollants X |
Action du groupe M sur X
D'un côté on a un Rubik's Cube monochrome, de l'autre côté les autocollants numérotés éparpillées sur la table,
physiquement rien ne lie entre ces deux objets. Imaginez
lorsqu'on fait une rotation A par ex, une force mystérieuse déplace les autocollants ....
|
|
Rotation A |
autocollants déplacées |
On appelle ceci "action" de A sur X, Ce n'est pas A qui déplace les autocollants mais une permutation p
A
de X, un élément de S
x , p
A∈S
x , la rotation A ordonne à p
A
de déplacer les autocollants.
au lieu de prendre la rotation A, on peut prendre n'importe quel élément de M, on dit que M agit sur X
A chaque rotation de base {H,B,A,P,G,D} on associe une permutation {p
H, p
B, p
A, p
P, p
G, p
D} de S
x et soit Λ les permutations engendrées par {p
H, p
B, p
A, p
P, p
G, p
D}
Λ = < p
H, p
B, p
A, p
P, p
G, p
D > et
Λ
+ = < p
H, p
B, p
A, p
P, p
G, p
D, p
Γ, p
Ψ, p
Ω >
Permutations standards (arête,sommet)
p
H = (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
p
B = (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);
p
A = (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);
p
P = (6,38,22,40)(30,14,46,16) (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
p
G = (4,12,20,14)(28,36,44,38) (3,39,13,27)(21,11,41,5)(23,37,43,25);
p
D = (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);
Permutations étendues
p
Γ = (2,26);
p
Ψ = (1,17,19);
p
Ω = (2,8)(26,32);
Permutations tranches
p
h = (10,36,14,40)(34,12,38,16);
p
d = (2,30,22,42)(26,6,46,18);
p
a = (4,32,24,44)(28,8,48,20);
Le GAP
Télécharger le GAP .::ICI::.
https://www.gap-system.org/Releases/4.4.12.html
Dans la fenêtre de cmd on se place dans le dossier de GAP
C:\Users\nom> cd\gap4r4\bin
C:\gap4r4\bin>gap < gap_rubikcube.txt
fichier gap_rubikcube.txt
gap_rubikcube.txt
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);
pGamma := (2,26);
pPsi := (1,17,19);
pOmega := (2,8)(26,32);
ph := (10,36,14,40)(34,12,38,16);
pd := (2,30,22,42)(26,6,46,18);
pa := (4,32,24,44)(28,8,48,20);
Lambdaplus := Group( pH, pB, pA, pP, pG, pD, pGamma, pPsi, pOmega );
Lambda1 := Group( pH, pB, pA, pP, pG, pD );
Print( "\n" );
Print( "|Lambda+| = ",Size( Lambdaplus ), "\n" );
Print( "|Lambda| = ", Size( Lambda1 ) , "\n" );
Print( "N = ", 2 * 3 * 2 , "\n" );
Print( "|G+| = ", Factorial(12) * 2^12 * Factorial(8) * 3^8 , "\n" );
Print( "|G| = |G+|/N = ", Factorial(12) * 2^12 * Factorial(8) * 3^8 / ( 2 * 3 * 2 ), "\n" );
Les permutations de Λ : p
H, p
B, ... ∈S
x ne sont pas quelconque de X mais elles sont très particulières pour voir celà il suffit de suivre le mouvement des autocollants,
l'autocollant '1' par exemple, elle ne peut pas se placer en '34' par ex , ou encore à chaque fois que '1' bouge , l'autocollant '17' bouge aussi... le '1' a un mouvement de S
8 et de rotation autour d'un triangle équilatérale (le '1' peut se placer en '17' ou '19').
Ainsi On peut regrouper les autocollants en arêtes et en sommets et leurs orientations pour former une configuration s:
s = (u,x,v,y) avec u∈S
12, x∈Z
212, v∈S
8, y∈Z
38
On retrouve ainsi :
G
+ = (S
12 x Z
212) x (S
8 x Z
38)
|
|
Rotation A |
état |
Il est donc important de faire la distinction entre: configuration, formule, permutation, .
G
+ c'est l'ensemble des configurations, cet ensemble forme un groupe .
G c'est l'ensemble des configurations produites par les rotations de base {H,B,A,P,G,D}, c'est un sous-groupe de G
+
G = {s∈G
+ / s=e•V , V∈M} , e=état résolule , le groupe du Rubik's Cube
G
+ = le groupe étendu de G
3 antagonismes M, Λ, G
L'étude mathématique du Rubik's Cube fait intervenir 3 antagonismes M, Λ, G , on va voir le rôle de chaqu'un
M = <H, B, A, P, G, D> , le groupe des formules (M ⊂ M
+)
Λ = <p
H, p
B, p
A, p
P, p
G, p
D> , le groupe des permutations des 48 autocollants (Λ ⊂ S
48)
G = le groupe du Rubik's Cube (G ⊂ G
+) , G = {s∈G
+ / s=e•V , V∈M} , e=état résolu
Tous les 3 sont isomorphes, mais on ne peut pas les identifiés car chaqu'un joue un rôle différent .
-M agit sur G
-M agit sur X
Beaucoup d'auteurs définissent Λ comme le groupe du Rubik's Cube mais ce n'est pas la discription la plus visuelle
Pour nous le groupe du Rubik's Cube c'est G l'ensemble des configurations provenant de M.
|
|
V : formule |
pV : permutations |
|
|
s=e•V : état |
|
On a:
Λ
+ <== M
+ ==> G
+
Λ <== M ==> G
Voici la démarche :
- G+ = S12 x Z212 x S8 x Z38 les configurations
- Loi interne '.' sur G+ : (u,x,v,y)(u',x',v',y') = (uu', x+u(x'), vv', y+v(y'))
- M = < H,B,A,P,G,D > les formules
- (M, .) : '.' concaténation
- Action '•' de M sur G+
- Définition de G: G = {s∈G+ / s=e•V , V∈M} , e=état résolu
- Théorème fondamental : G = {s∈G+ / s vérifie les 3 lois}
Remarque
M = < H,B,A,P,G,D >
On peut avoir 5 générateurs
M = < H,A,P,G,D > où B = (DG'A²P²DG')H(DG'A²P²DG') (Roger Penrose)
On peut avoir 2 générateurs
M = < Q,K > où Q = HPGHG'H'P' et K = D²AGB'D' (Frank Barnes)
[1] 2 3 4 5 6 7 8 9
Accueil
DMJ: 01/05/2024