La face cachée du Rubik's Cube

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⁴ et D⁴ ou encore (H²D²)³(B²D²)³ et (H²G²)³(B²G²)³ dans ce cas nous dirons que ces mélanges sont équivalants ou identiques et que nous écrivons
A⁴ = D⁴
(H²D²)³(B²D²)³ = (H²G²)³(B²G²)³
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:

1. 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).
2. Il existe un mélange qui consiste à rien faire, on l'appelle mélange neutre et on le note I (élément neutre).
3. Chaque mélange S a un inverse S' (noté aussi parfois S^-1): SS'=S'S=I (symétrique)
4. 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⁴ = I et
D' = D³
mais
(H²D²)³(B²D²)³ ≠ (H²G²)³(B²G²)³

On dit A⁴ = I , parce qu'elles donnent le même état (état initial) de même D' = D³ parce qu'elles donnent aussi le même état mais (H²D²)³(B²D²)³ ≠ (H²G²)³(B²G²)³ 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₇ .::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₈ 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₁₂, x∈Z₂¹², v∈S₈, y∈Z₃⁸
G⁺ = (S₁₂ x Z₂¹²) x (S₈ x Z₃⁸)

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⁴=[HD]⁶ (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₁₂ (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₂¹² (Z₂ = un groupe à 2 éléments), finalement pour les arêtes on a S₁₂ x Z₂¹²

3. Même chose pour les sommets
On peut permuter les 8 sommets entre eux comme on veut, donc on a affaire à S₈ 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₃⁸, pour les sommets on a S₈ x Z₃⁸

Finalement l'ensemble de tous les états (produits par M⁺) est:

G⁺ = (S₁₂ x Z₂¹²) x (S₈ x Z₃⁸)

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₁₂ x Z₂¹² x S₈ x Z₃⁸

°NOTE :
- ex: u = (1,3,5,2)(9,11) et x = (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁, x₁₂)
u(x) = (x₃, x₁, x₅, x₄, x₂, x₆, x₇, x₈, x₁₁, x₁₀, x₉, x₁₂)
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₄₈)
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é

1. Quelque soit la démarche on doit arriver à:
   G⁺ = S₁₂ x Z₂¹² x S₈ x Z₃⁸
2. 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)
3. Le groupe du Rubik's Cube G est le sous-groupe de G⁺ qui vérifie les 3 lois
4. 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