La face cachée du Rubik's Cube

27 Feb 2017

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

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 A4 et D4 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
A4 = D4
(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, et 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 du mélange étendu Γ=(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 du mélange étendu Ψ = (HDA)+ (état étendu r5)

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 du mélange étendu Ψ² = (HDA)++ = (HDA)- (état étendu r3)


Permuter deux arêtes : rotation Ω
1. On enlève les arêtes (HA), (HG)
2. Permute (HA)<->(HG) = (HA,HG)
3. Puis on les remet

mélange étendu Ω Résultat du mélange étendu Ω = (HA)<->(HG) = (HA,HG) (état étendu r2)

Ce mélange , par définition , se nomme rotation étendue Ω qui a comme résultat, les arêtes (HA) , (HG) sont permutées
(HA)<->(HG) = (HA,HG) = Ω


Dans le même ordre d' idée , voici un mélange étendu ΩΓ:
1. On enlève les arêtes (HA), (HG)
2. Permute (HA)<->(HG)
3. Pivote (HA)
4. Puis on les remet

mélange étendu ΩΓ Résultat du mélange étendu ΩΓ = (HA)°<->(HG) = (HA°,HG) (état étendu r8)

(HA°,HG) = ΩΓ

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:
A4 = I et
D' = D3
mais
(H²D²)3(B²D²)3 ≠ (H²G²)3(B²G²)3

On dit A4 = I , parce qu'elles donnent le même état (état initial) de même D' = D3 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

u = abd'bbc ; OK
v = c'dab'bd² ;interdit

Soit FZ l'ensemble des mots de Z , et on prend par définition
1. a' ==> symétrie de a
2. 1=mot-vide=élément neutre, aa'=a'a=1
3. u=ab'dc ==> u'=c'd'ba' symétrie de u
4. FZ muni la loi concaténation forme un groupe nommé groupe libre engendré par Z

Soit maintenant K un sous-groupe (d'un groupe L) engendré par les p,q,r,s, ... c'est-à-dire K = < p,q,r,s, ... > ⊂ L
f: FZ -> K
f(a)=p , f(b)=q, f(c)=r, f(d)=s, .... et
x,y ∈FZ , x~y ssi x,y ∈Ker(f)
alors on a:
G=FZ/~ = FZ/Ker(f) = K

Pour nous
Z = {H,B,A,P,G,D}
K = Λ = < pH, pB, pA, pP, pG, pD > permutations des étiquettes X ; ⊂ Sx
f: FZ ->Λ
f(H) = pH, f(B) = pB, f(A) = pA, ... permutations des stickers ∈ Sx
U,V ∈M , U~V ssi U,V donnent même état (U,V ∈Ker(f))
et M=FZ/~ = FZ/Ker(f) = K fini

il est plus facile, et plus compréhensible de définir
M = < H, B, A, P, G, D > ; avec la convention U=V si U,V donnent le même état
que de définir par
M = FZ/Ker(f)

Remarque

ΓA signifie on fait la rotation Γ puis la rotation A et ΓA≠AΓ, le résultat, on se trouve sur la couche G7 .::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 1,2,... ,48 comme indique la fig ci-dessous

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 pA de X, un élément de Sx , pA∈Sx , la rotation A ordonne à pA 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 {pH, pB, pA, pP, pG, pD} de Sx et soit Λ les permutations engendrées par {pH, pB, pA, pP, pG, pD}
Λ = < pH, pB, pA, pP, pG, pD > et
Λ+ = < pH, pB, pA, pP, pG, pD, pΓ, pΨ, pΩ >

Permutations standards
pH = (19,35,27,43)(41,17,33,25)(8,6,1,3)(18,34,26,42)(7,4,2,5)
pB = (22,46,30,38)(40,24,48,32)(9,11,16,14)(23,47,31,39)(10,13,15,12)
pA = (6,41,11,40)(35,8,46,9)(17,19,24,22)(7,44,10,37)(18,21,23,20)
pP = (3,33,14,48)(43,1,38,16)(25,27,32,30)(2,36,15,45)(26,29,31,28)
pG = (6,22,14,27)(17,9,32,1)(35,40,38,33)(4,20,12,29)(34,37,39,36)
pD = (8,25,16,24)(19,3,30,11)(41,43,48,46)(5,28,13,21)(42,45,47,44)

Permutations étendues
pΓ = (7,18)
pΨ = (8,41,19)
pΩ = (7,4)(18,34)

Permutations tranches
ph = (21,37,29,45)(44,20,36,28)
pd = (7,26,15,23)(18,2,31,10)
pa = (4,42,13,39)(34,5,47,12)

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\gap4r7\bin
C:\gap4r7\bin>gap
gap>
Ici on colle le text gap_rubikcube.txt
gap_rubikcube.txt

Les permutations de Λ , pH, pB, ... ∈Sx 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 '6' par exemple, elle ne peut pas se placer en '44' par ex , ou encore à chaque fois que '6' bouge , l'étiquette '17' bouge aussi... le '6' a un mouvement de S8 et de rotation autour d'un triangle équilatérale (le '6' peut se placer en '35' ou '17'). les pH, pB, ... sont alors décomposées en 4 morceaux que l'on nomme 'état' s:
s = (u,x,v,y) avec u∈S12, x∈Z212, v∈S8, y∈Z38

G+ = (S12 x Z212) x (S8 x Z38)

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=A4=[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 à S12 (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 à Z212 (Z2 = un groupe à 2 éléments), finalement pour les arêtes on a S12 x Z212

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

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

G+ = (S12 x Z212) x (S8 x Z38)

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) = (xu(1), xu(2), xu(3),..., xu(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 ⊂ S12 x Z212 x S8 x Z38

°NOTE :
- ex: u = (1,3,5,2) et x = (x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12)
u(x) = (x3, x1, x5, x4, x2, x6, x7, x8, x9, x10, x11, x12)
-Certains auteurs définissent le produit de deux états comme:
(u,x)(u',x') = ( uu', x + u-1(x') ) mais notre définition a un avantage c'est qu'elle relève exactement ce qui se passe sur le Rubik's Cube.

-On a: u(x+x') = u(x) + u(x')

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 pA∈SX => é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+)
Λ = <pH, pB, pA, pP, pG, pD> , le groupe des permutations des 48 étiquettes (Λ ⊂ S48)
G = le groupe du Rubik's Cube (G ⊂ G+)

Tous les 3 sont isomorphes .
-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

M: Les mouvements Λ : Les permutations des stickers
G: L'ensemble des états

On a:
M+ ⇒ Λ+ ⇒ G+
M ⇒ Λ ⇒ G

Résumé
  1. Quelque soit la démarche on doit arriver à:
    G+ = S12 x Z212 x S8 x Z38
  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 = < T,K > où T = HPGHG'H'P' et K = D²AGB'D' (Frank Barnes)

[1] 2 3 4 5 6 7 8 9

Accueil

DMJ: 27/02/2017









Facile

Moyen

Difficile

Les Crazy

Les Stars

Divers

Théorie des Twists

Quiz (Master Cube)