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 vraiment intéressant
mais aussi parce qu'il materise 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 mélange (=mouvement, =formule, =manoeuvre), et la notion d'état (=configuration, =motif) . Comme en géométrie avec la notion de 'point', on comprend bien ce qu'est un 'point', mais l'expliquer n'est pas évident !
Même chose ici, on voit ce qu'est un mélange , un motif, mais l'expliquer c'est autre chose.
Les Mélanges
Mélanges standards
Prenez un Rubik's Cube à l'état résolu, orientez le c'est-à-dire , dire qui est le Haut, qui est l'Avant .... (par ex Haut=blanc, Avant=vert, ... ). Une fois le Cube est fixé
mélangez-le avec les rotations de base {H,B,A,P,G,D}, on obtient ainsi un mélange ce que nous appelons un mélange standard ou un mélange tout court.
Voici un exemple d'un mélange (standard)
 |
 |
Un mélange par rotation A |
Résultat du mélange (état) |
A = (HA)->(AD)->(BA)->(AG).(HDA)->(BAD)->(BGA)->(HAG)
= (HA,AD,BA,AG).(HDA,BAD,BGA,HAG)
Le résultat d'un mélange est un état. On peut remarquer tout de suite que 2 mélanges peuvent donner un même état par ex
A
4 et D
4 ou encore (H²D²)
3(B²D²)
3 et (H²G²)
3(B²G²)
3
dans ce cas nous dirons que ces mélanges sont équivalants ou identiques et que nous écrivons
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')
L'Ensemble des mélanges à partir des rotations de base {H,B,A,P,G,D} sera noté
M = < H, B, A, P, G, D > , M est donc engendré par les rotations de base,
IMPORTANT !! On considère que deux mélanges donnant le même état seront identiques.
Mélanges étendus
Démontons le Cube, mélangeons un peu les pièces puis ré-assemblons le, ce que nous appelons un mélange étendu.
Voici quelques exemples de ces mélanges étendus
Pivoter une arête : rotation Γ .
1. On enlève l'arête (HA)
2. La pivote (180° ou -180°)
3. Puis on la remet
 |
 |
Rotation étendue Γ |
Résultat de la rotation étendue Γ=(HA)+=(HA)-=(HA)° (état étendu r7) |
Par définition ce mélange se nomme rotation étendue Γ qui a comme résultat , l'arête (HA) est pivotée (180° ou -180°)
(HA)° = (HA)
+ = (HA)
- = Γ
Pivoter un sommet : rotation Ψ .
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 Ψ |
Résultat de la rotation étendue Ψ = (HDA)+ (état étendu r3) |
Ce mélange , 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)
+ = Ψ
Pivoter un sommet: Ψ²
1. On enlève le sommet (HDA)
2. Le pivote 2/3 tour dans le sens horaire(240° ou -120°)
3. Puis on le remet
 |
 |
Rotation étendue ΨΨ=Ψ² |
Résultat de la rotation étendue Ψ² = (HDA)++ = (HDA)- (état étendu r5) |
Permuter deux arêtes : rotation Ω
1. On enlève les arêtes (HA), (HD)
2. Permute (HA)<->(HD) = (HA,HD)
3. Puis on les remet
 |
 |
rotation étendue Ω |
Résultat de la rotation étendue Ω = (HA)<->(HD) = (HA,HD) (état étendu r2) |
Ce mélange , par définition , se nomme rotation étendue Ω qui a comme résultat, les arêtes (HA) , (HD) sont permutées
(HA)<->(HD) = (HA,HD) = Ω
Dans le même ordre d' idée , voici un mélange étendu ΩΓ:
1. On enlève les arêtes (HA), (HD)
2. Permute (HA)<->(HD)
3. Pivote (HA)
4. Puis on les remet
 |
 |
mélange étendu ΩΓ |
Résultat du mélange étendu ΩΓ = (HA)°<->(HD) = (HA°,HD) (état étendu r8) |
(HA°,HD) = ΩΓ
Ce sont des mélanges impossible à réaliser sans démonter le Cube.
Les "rotations" Γ, Ψ, Ω , par définition appellées rotations étendues.
On note M
+ l'ensemble des mélanges étendus
M
+ = < H, B, A, P, G, D ,Γ, Ψ, Ω > , M
+ est donc engendré par les 6 rotations de base et les 3 rotations étendues.
Rappel : deux mélanges donnant le même état seront considèrés comme identiques.
M ⊂ M
+
Le groupe (M+, .)
L'ensemble des mélanges M
+ étendus muni le produit (la concaténation) de deux mélanges forme un groupe (M
+, .) , en effet on a:
- Le produit ST (on fait S puis T) d'un mélange S par un mélange T, est encore un mélange (loi interne).
- Il existe un mélange qui consiste à rien faire, on l'appelle mélange neutre et on le note I (élément neutre).
- Chaque mélange S a un inverse S' (noté aussi parfois S-1): SS'=S'S=I (symétrique)
- Faire (ST) puis K c'est la même chose que faire S puis (TK):
(ST)K=S(TK) (associative)
M = < H,B,A,P,G,D > (engendré par {H, B, A, P, G, D}) est un sous groupe de M+ . Mais ce n'est ni M ni M+ ce sera ce qu'on appelle le groupe du Rubik's Cube !, contrairement à beaucoup de gens y croient
(M+ , . ) se nomme le groupe des formules étendues du Rubik's Cube , et (M , . ) le groupe des formules du Rubik's Cube.
RAPPEL : On considère que deux formules donnant un même état sont identiques
Finalement : il y a 2 concepts importants il faut bien comprendre et maitriser et ne pas confondre.
concept: mélange = mouvement = manoeuvre = formule
concept: état = motif = configuration
Remarque important
Une remarque importante sur M (ou M
+) , on a considéré que deux formules donnant un même état, elles sont identiques, pourquoi ne seront pas elles différentes ?
Si deux formules différentes donnent le même état, c'est qu'elle donnent un même état c'est tout en quoi celà nous gène ?
Voyons de plus prés
I. Tout le monde s'accorde sur les égalités suivantes:
A
4 = I et
D' = D
3
mais
(H²D²)
3(B²D²)
3 ≠ (H²G²)
3(B²G²)
3
On dit A
4 = I , parce qu'elles donnent le même état (état initial) de même D' = D
3 parce qu'elles donnent aussi le même état mais
(H²D²)
3(B²D²)
3 ≠ (H²G²)
3(B²G²)
3 et pourtant elle donnent le même état, ce n'est pas très logique !!
II. On peut écrire
I, AAAA, AAAAAAAA, .... M aura donc une infinité d'éléments, or on sait que le groupe du Rubik's Cube est fini, on aimerais 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 Z={a,b,c,d,...}, Z'={a',b',c',d',...} disjoints en bijection et un élémént 1 non dans Z et Z'. On forme les mots de Z c'est-à-dire les suites finies d'éléments de Z et Z'
avec la règle: aa', a'a, bb', b'b, cc', c'c, ... interdits
du genre
S = abd'bbc ; OK
T = c'dab'bd² ; interdit
Soit F
Z l'ensemble des mots de Z , et on prend par définition :
1. a' ==> symétrique de a
2. 1=mot-vide=élément neutre, aa'=a'a=1
3. S=ab'dc ==> S'=c'd'ba' symétrique de S
4. F
Z muni la loi concaténation :
ST = N (on supprime bien sûr les a'a, aa', b'b, bb', .... dans N)
F
Z forme ainsi un groupe nommé
groupe libre engendré par Z
Soit maintenant L un groupe fini, et f un morphisme surjectif de F
Z -> L :
f: F
Z -> L
S -> f(S)
et
S,T ∈F
Z , S~T ssi f(S) = f(T)
alors on a:
G=F
Z/~ = F
Z/Ker(f) = L (th: si f morphisme surjectif alors F
Z/Ker(f) = L)
Pour nous
Z = {H,B,A,P,G,D} , F
Z = M
L = Λ = < p
H, p
B, p
A, p
P, p
G, p
D > permutations des étiquettes X ; Λ ⊂ S
x
f: M -> Λ
f(H) = p
H, f(B) = p
B, f(A) = p
A, ... permutations des stickers ∈ S
x
S,T ∈M , S~T ssi S,T ∈Ker(f))
et
M/~ = M/Ker(f) = L fini
il est plus facile, et plus compréhensible de manipuler
M = < H, B, A, P, G, D > ; avec la convention S=T si S,T donnent le même état (=la même permutation étiquettes)
que de manipuler des classes d'équivalences.
M/~
Remarque
ΓA signifie on fait la rotation Γ puis la rotation A et ΓA≠AΓ, le résultat, on se trouve sur la couche G
7 .::LES COUCHES ICI::.
 |
 |
ΓA (on est sur la couche G7) |
AΓ (on est sur la couche G7) |
L'ensemble X des étiquettes
Soit X = {1,2,3, ..., 48} l'ensemble des étiquettes numérotées comme indique la fig ci-dessous
Notre but c'est de numéroter les autocollants de tel sort 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 étiquettes X |
|
Action du groupe M+ sur X
D'un côté on a un Rubik's Cube monochrome, de l'autre côté les étiquettes 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 étiquettes ....
 |
 |
Rotation A |
étiquettes déplacées |
On appelle ceci "action" de A sur X, Ce n'est pas A qui déplace les étiquettes 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 étiquettes.
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-étiquettes {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/index.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
ou bien
gap>
Ici on colle le text 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);
rubikplus := Group( pH, pB, pA, pP, pG, pD, pGamma, pPsi, pOmega );
rubik := Group( pH, pB, pA, pP, pG, pD );
# Srubikplus := Size( rubikplus );
# Srubik := Size( rubik );
# indice := Srubikplus / Srubik ;
Print( "RubikPlus = ",Size( rubikplus ), "\n" );
Print( "Rubik = ", Size( rubik ) , "\n" );
Print( "Indice = ", Size( rubikplus )/Size( rubik ) , "\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 étiquettes,
l'étiquette '1' par exemple, elle ne peut pas se placer en '34' par ex , ou encore à chaque fois que '1' bouge , l'étiquette '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'). les p
H, p
B, ... sont alors décomposées en 4 morceaux que l'on nomme 'état' s:
s = (u,x,v,y) avec u∈S
12, x∈Z
212, v∈S
8, y∈Z
38
G
+ = (S
12 x Z
212) x (S
8 x Z
38)
G
+ est le résultat de l'action de M
+ (sur X), et G résultat de l'action de M (sur X).
Comme on considère que deux formules donnant un même état sont identiques , on dira alors qu'elle possède des différentes écritures comme
par ex: I=A
4=[HD]
6 (comme pour les nombres: 1/2 = 3/6 = 0,5)
Remarque
On peut retrouver rapidement G
+ en raisonnant ainsi: (sans entrer dans le détail de la construction par l'action de M
+ sur X)
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, donc on a affaire à S
12 (le groupe des permutations à 12 objets) et chaqu' arête possède 2 orientations.
Par exemple, l'arête vert-orange peut se placer en (HA) avec (H=orange, A=vert) ou (H=vert, A=orange), donc l'orientation des arêtes est codée par un vecteur à 12 composantes à valeur dans {0,1},
c'est donc 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, donc on a affaire à S
8 et chaque sommets possède 3 orientations.
Par exemple, le sommet blanc-vert-rouge peut se placer en (HDA) avec (H=vert, Droite=blanc, A=rouge) ou (H=rouge, Droite=vert, A=blanc), donc l'orientation des sommets elle aussi est codée par un vecteur à 8 composantes à valeur dans {0,1,3},
c'est donc on a affaire à Z
38, pour les sommets on a S
8 x Z
38
Finalement l'ensemble de tous les états (produits par M
+) est:
G
+ = (S
12 x Z
212) x (S
8 x Z
38)
Ce sont tous les états du Cube (produit par tous les mélanges du Cube y compris le démontage/montage du Cube)
Quand on mélange le Cube normalement avec les rotations {H,B,A,P,G,D}, on obtient un état , mais ce mélange a des contraintes ! Et ces contraintes sont bien visibles.
En effet, prenons un exemple: mélangeons le Cube avec la rotation A. On voit qu'on permute les arêtes mais on permute aussi les sommets !!
A chaque fois qu'on bouge les arêtes
on est obligé de bouger aussi les sommets. G est donc l'ensemble des états provenant des mélanges avec contraintes.
Sur G
+ on définit une certaine loi (assez étrange d'ailleurs) qui fait que G
+ est un groupe et G est un sous groupe de G
+
La loi interne '.' dans G+: (G+, .)
On va définir une loi interne dans G
+ , voici l'opération 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')) (
.::voir pourquoi ici::. ) avec u(x) = (x
u(1), x
u(2), x
u(3),..., x
u(12)) (°)
Le couple (u,x) ou (v,y) = (permutation,vecteur) que j'appelerai un "état" l'état de la pièce, le produit de 2 états est donc
(u,x)(u',x') = ( uu', x + u(x') ) (
.::voir pourquoi ici::. ) rappelle: uu' , on fait u en 1er puis u' (uu' = u' o u)
C'est G qu'on appelle le groupe du Rubik's Cube, il décrit les états du Cube produits par des mouvements standards.
Et finalement, G se trouve dans un objet composé de 4 "morceaux"
G ⊂ S
12 x Z
212 x S
8 x Z
38
°NOTE :
- ex: 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=identité
0=(0,0,0,0,0,0,0,0,0,0,0,0) vecteur nul
id=permutation identité
1=(1,1,1,1,1,1,1,1) vecteur ayant des 1
En résumé :
Chaque
mouvement gènère une
permutations des étiquettes qui produit ensuite un
état du Cube.
par exemple
rotation A∈M => permutation p
A∈S
X => état s=(u,x,v,y)∈G (configuration, motif)
 |
 |
Rotation A |
état |
Il est donc important de faire la distinction entre: mouvement, permutation, état.
G
+ c'est l'ensemble des états du Cube produits par tous les mouvements (mélanges) y compris le démontage/remontage du Cube, cet ensemble forme un groupe pour une loi assez étrange que nous venons de voir.
G c'est l'ensemble des états produits par les rotations de base {H,B,A,P,G,D}, c'est un sous-groupe de G
+
G = 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 étiquettes (Λ ⊂ S
48)
G = le groupe du Rubik's Cube (G ⊂ G
+)
Tous les 3 sont équipotentes, chaqu'un joue un rôle différent .
-M agit sur G
-M agit sur X
Beaucoup d'auteurs prennent Λ 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 états qui vérifient certaines conditions
 |
 |
A : rotation |
pA : permutations des étiquettes |
 |
|
s : l'état |
|
On a:
M
+ ⇒ Λ
+ ⇒ G
+
M ⇒ Λ ⇒ G
Résumé
- Quelque soit la démarche on doit arriver à:
G+ = S12 x Z212 x S8 x Z38
- Il faut définir une loi interne '.' sur G+ qui correspond à avec ce qui se passe sur le Rubik's Cube (mouvement, orientation ... quand on tourne une face)
- Le groupe du Rubik's Cube G est le sous-groupe de G+ qui vérifie les 3 lois
- Trouver une conexion entre M et G sinon ça sert à rien de fabriquer G !!!
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: 23/05/2023