La face cachée du Rubik's Cube

06 Feb 2017

Structure mathématique du Rubik's Cube Le Rubik's Cube est célèbre non seulement parce que c'est un casse-tête vraiment intéressant, mais aussi parce qu'il contient une bonne dose de mathématique de haut niveau !!!


Construction le groupe G Rubik's Cube

On ne rentre pas dans le détaille dans la contruction (action de M+ sur les stickers X,...) on passe directement à la phase d'analyse.

- On a 12 arêtes qui baladent partout, donc on a affaire avec S12, mais les arêtes peuvent aussi se pivoter en 2 positions c'est un truc Z212, pour les arêtes tout se passe dans:
S12 x Z212
- On a 8 sommets qui baladent partout, donc on a affaire avec S8, mais les sommets peuvent aussi se pivoter en 3 positions c'est un truc Z38, pour les sommets tout se passe dans:
S8 x Z38
Finalement tout se passe dans
G+ = S12 x Z212 x S8 x Z38 c'est l'ensemble de tous les états du cube.
G+ muni la loi suivante, qui lui confère un groupe, le groupe étendu du puzzle
(u,x,v,y)(u',x',v',y') = ( uu', x+u(x'), vv', y+v(y') )

et un élément de G c'est par définition:
s=(u,x,v,y)∈G+
u ∈S12, x ∈Z212, v ∈S8, y ∈Z38
qui vérifie:
1. ∑ xi = 0 (mod 2) en abrégeant x=0 (mod 2) avec x = (x1,x2,...,x12)
2. ∑ yi = 0 (mod 3) en abrégeant y=0 (mod 3) avec y = (y1,y2,...,y8)
3. sig(u)=sig(v)

Il nous reste maintenant à montrer la "connexion" entre M et G, tout celà se fait en plusieurs étapes

Connexion entre M et G

Le but est de montrer la propriété suivante:
Chaque formule gènère un état (normal, légale) , chaqu'état provient d'une formule

Chaqu'état provient d'une formule

On prend donc un élément de G , et il faut trouver une formule dont il provient
s=(u,x,v,y)∈G+ vérifiant les trois conditions (1), (2) et (3)
On va faire ça en plusieurs étapes.
On coupe (u,x,v,y) en deux morceaux (u,x,v,y) = (1,x,1,y)(u,0,v,0)

Cas 1: (u,0,v,0)
L'état (u,0,v,0) signifie que les sommets et les arêtes sont mal placés mais bien orientés.
Soient les 3 formules suivantes:
F1 = D².H'D'H'.(DH)².DH'D => déplacer 3 arêtes sans toucher les autres pièces, un 3-cycle
F2 = [HD]G'[DH]G => déplacer 3 sommets sans toucher les autres pièces, un 3-cycle
F3 = [D'H²]D'AD. HD'H'D'.A'D²H' => permuter un couple d'arêtes et un couple de sommets sans toucher les autres pièces.

- Si sig(u)=sig(v)=1
On utilise F1 (et la conjugaison) , pour placer les arêtes, c'est possible car F1 est un 3-cycle , et que A12 (sig(u)=1 paire) est engendré par les 3-cycle
même chose pour les sommets on utilise F2 (et la conjugaison) , pour placer les sommets.
- Si sig(u)=sig(v)= -1
On utilise F3 (et la conjugaison), on revient alors au cas précédent

Cas 2: (1,x,1,y)
L'état (1,x,1,y) signifie que les sommets et les arêtes sont bien placés mais pas orientés.
Soient 2 formules suivantes:
F4 = AH²A² .B' [H'G' ]B .A²H' A' H' => pivoter 2 arêtes sans toucher les autres pièces
F5 = [HD]²G'[DH]²G => pivoter 2 sommets sans toucher les autres pièces
On utilise F4 (et la conjugaison) , pour pivoter les arêtes, la dernière sera automatiquement bien orientée à cause de x=0 (mod 2)
On utilise F5 (et la conjugaison) , pour pivoter les sommets, le dernier sera automatiquement bien orienté à cause de y=0 (mod 3)

Finalement pour trouver une formule pour l'état (u,x,v,y) on fait simplement
- Utiliser les formules F1,F2,F3 pour placer les arêtes et les sommets => (u,0,v,0)
- Utiliser la formule F4,F5 pour orienter les arêtes et les sommets => (1,x,1,y)
Donc l'état (u,x,v,y) = (1,x,1,y)(u,0,v,0) correspond bien à une formule (on démontrera que la formule est unique)

Chaque formule gènère un état

On prend donc une formule L -un élément de M- , la formule gènère un état (u,x,v,y)∈G+, il faut montrer que
1. x=0 (mod 2)
2. y=0 (mod 3)
3. sig(u)=sig(v)

(3) => Pour une rotation de base, on a sig(u).sig(v)=1 donc pour une formule on a sig(u).sig(v) x sig(u').sig(v') x sig(u").sig(v")... = 1x1x1 ... = 1

(1)+(2) => Parmi les écritures de la formule L qui donne (u,x,v,y) on prend la plus courte (c'est exactement comme 2/4, 4/8, 8/16 ... on prend le plus simple 1/2)
longeur=|L|=n, on va raisonner par récurrence sur n
Pour n=1 , on a x=0 (mod 2) et y=0 (mod 3) pour toute rotation de base {H,B,A,P,G,D}
Supposons que la propriété soit vraie pour n, montrons qu'elle reste encore vraie pour n+1
Soit Q une formule de longeur=|Q]=n+1, mais on passe de n à n+1 par une rotation de base
Q = LZ avec Z=rotation de base => (u',x',v',y') = (u,x,v,y)(p,a,q,b)
x' = x + u(a)
y' = y + v(b)
comme
x=0 (mod 2) l'hypothèse de récurrence
u(a)=0 (mod 2) la permutation u ne change pas le modulo
d'où
x'=0 (mod 2)
de même
y=0 (mod 3)
v(b)=0 (mod 3)
d'où
y'=0 (mod 3)

Résumer: Toute formule produit un élément de G (état standard), tout élément de G (état standard) provient de M
Remarque :
1. Bien que M et G soient isomorphes, on ne peut pas identifier G=M, car M et G ne jouent pas le même rôle, M agit sur G, et non à l'inverse , on fait la rotation A et on voit les étiquettes se déplacent, on ne déplace pas les étiquettes (décoller/coller) pour voir la face A tourne !!!!
2. Le Rubik's Cube est un twist enphasé.

Vérification des lois

Rappel
G+ = S12 x Z212 x S8 x Z38 c'est l'ensemble de tous les états du cube.
et un élément de G est quelque chose comme ça:
s=(u,x,v,y)∈G+
u ∈S12, x ∈Z212, v ∈S8, y ∈Z38
qui vérifie:
1. ∑ xi = 0 (mod 2)
2. ∑ yi = 0 (mod 3)
3. sig(u)=sig(v)

G+ = S12 x Z212 x S8 x Z38 = L'ensemble de tous les états du cube, c.à.d. les états produits par tous les mouvements y compris le démontage/remontage du cube autrement dit pour n'importe quelle permutation, orientation de sommets et d'arêtes
G+ est le groupe étendu du Rubik's Cube
G = Le groupe du Rubik's Cube (seulement les états engendrés par les rotations {H,B,A,P,G,D} )

Vérifions ces 3 lois sur [AH]

[AH] = AHA'H'


Loi des flips: la somme des orientations des arêtes est pair
x1=blanc-vert=0,x4=blanc-rouge=1,x6=vert-orange=1 on a bien:
0+x1+x4+x6=0 (mod 2)

Loi des twists: la somme des orientations des sommets est un multiple de 3
y1=blanc-rouge-vert=0,y4=blanc-bleu-rouge=2,y6=jaune-orange-vert=2,y2=blanc-vert-orange=2 on a bien:
0+y1+y4+y6+y2=0 (mod 3)

Loi de parité: les permutations des arêtes et des sommets ont la même signature
arêtes: u=1->4->6 sig(u) = (-1)3-1 = 1
sommets: v=(1,4)(6,2) sig(v) = (-1)2 = 1
d'où
sig(u)=sig(v)
c'est magique non ? !!! :-) :-)

Remarque:
I. Ne pas confondre un trou-arête (emplacement) avec une arête, un trou-arête est un objet fixe à 2 facettes, tandis qu'une arête est un objet mobile à 2 couleurs, qui se déplace de trou en trou !! (même remarque pour les trous-sommets et les sommets).
II. Si les centres sont orientés (avec des images par ex) alors le Rubik's Cube devient un SuperRubik's Cube. On voit que le centre (H) a la même signature que les arêtes (ou sommets) en effet si m = le nombre de rotations 90° des centres, on pose
sig(c) = (-1)m
et
sig(u)=sig(v)=sig(c)
Autrement dit si c est pair alors u doit être une permutation paire. A l'état résolu, la signature des arêtes est paire (sig(u)=1) donc la signature des centres aussi c'est-à-dire sig(c) = (-1)2k , la somme des centres doit être un multiple de 2x90° = 180° (k180).
Ceci explique pourquoi on ne peut pas tourner un centre à ±90° tout seul, mais toujours deux centres l'un 90°, et l'autre -90° ou bien un centre à 180° .
On a 46/2 = 2048 ( divisé par 2 à cause de la loi sig(c)=sig(u)=sig(v) ) de nombres de positions en plus qui faut multiplier avec le nombres d'états.

1 2 [3] 4 5 6 7 8 9

Accueil

DMJ: 06/02/2017









Facile

Moyen

Difficile

Les Crazy

Les Stars

Divers

Théorie des Twists

Quiz (Master Cube)