Formule, Etat

16 Jan 2013

Introduction ... Il est vraiment important de distinguer deux choses: formule (rotation, mouvement, manoeuvre, mélange, ...) et état (motif, configuration, ...)

- Une formule transforme un état en un autre état.
- Un état est un élément qui décrit le Cube


Action, Opèrer, Agir....

Voyons qu'est qu'on a dans la main ?

- D'un côté, on a un ensemble de formules M formé par des rotations de base {H,B,A,P,G,D}, et deux formules considérées comme identiques si elles donnent le même état.
- De l'autre côté, un ensemble d'états G qui décrit le Cube.
- On selecte l'état "résolu" (une couleur par face) e .

Et voilà les données.

Comme nous avons déjà dit, une formule transforme un état en un autre, commençons donc par le commencement ... à partir de l'état résolu e on fait une rotation A -par exemple-, le Cube se trouve donc en un autre état, au lieu de faire la rotation A , on peut faire avec n'importe quel formule par exemple [DH], ... Donc, soit U une formule quelconque , on applique U sur e et on se trouve sur un autre état s, qu'on va noter:
e•U = s (lire: on applique U à e)

On voit bien maintenant la différence entre U et s .

Cette oppération '•' possède 2 propriétés:
1. x•I = x (I=formule Identique, x=état) ==> On ne fait rien, donc rien ne change !!!!
2. (x•U)•V = x•(UV) où U, V sont des formules

On dit que M (formule) agit (opère, ...) sur G (état)

De plus on impose la condiction suivante:
3. e•U = e•V => U=V (par définition, axiome)

Formule, Etat

Il y a une bijection entre M et G , voyons ...
Soit
f: M -> G
U -> f(U) = e•U
Le but est donc de montrer que f est bijective.

1. f est injective
f(U) = f(V)
e•U = e•V
(e•U)•V' = (e•V)•V'
e•(UV') = e•(VV') propriété 2
e•(UV') = e•I
UV' = I propriété 3
d'où
U=V

f est donc injective , en fait f est injective par définition même

2. f est surjective
On prend donc un élément de G , et il faut trouver une formule dont il provient
e=(u,x,v,y)∈G et on a:
1. ∑ xi = 0 (mod 2) avec x = (x1,x2,...,x12)
2. ∑ yi = 0 (mod 3) avec y = (y1,y2,...,y8)
3. sig(u)=sig(v)

La preuvre est constructive, càd on construit petit à petit la formule
On va faire ça en plusieurs étapes.
On coupe (u,x,v,y) en deux morceaux (u,x,v,y) = (u,x-u(x),v,y-v(y))(id,x,id,y)

Soient les 3 formules suivantes:
F1 = A[DH]A'H => permuter 2 arêtes
F2 = (A[DH]A'H)² => pivoter 2 arêtes
F3 = [DH]G'[HD]G => 3-cycle-sommets
F4 = [DH]²G'[HD]²G => pivoter 2 sommets opposés

¤ (u,x-u(x),v,y-v(y)) :
Placer les arêtes
On utilise F1 (et la conjugaison) pour placer les arêtes comme exige u, c'est possible car les transpositions engendrent S12
Puis on utilise F2 (et la conjugaison) pour pivoter les arêtes comme exige x-u(x), c'est possible grâce à la loi des flips

Placer les sommets
On utilise F3 (et la conjugaison) pour placer les sommets comme exige v, c'est possible grâce à la loi de parité .
Puis on utilise F4 (et la conjugaison) pour pivoter les sommets comme exige y-v(y), c'est possible grâce à la loi des twists

¤ (id,x,id,y) :
Pivoter les arêtes
On utilise F2 (et la conjugaison) pour pivoter les arêtes comme exige x, c'est possible grâce à la loi des flips

Pivoter les sommets
On utilise F4 (et la conjugaison) pour pivoter les sommets comme exige y, c'est possible grâce à la loi des twists

Finalement on trouve une grosse grosse formule pour l'état (u,x,v,y).

f est surjective.

Finalement on a une bijection entre M et G. On peut même démontrer que M et G sont isomorphes.
Une formule <=> un état , une formule gènère un état et un seul, un état provient d'une formule unique .

NOTE : Parfois on écrit s = U (au lieu de s = e•U) ça signifie que pour avoir l'état s on utilise la formule U

Commentaire

Il y a beaucoup de gens qui pensent qu'il existe plusieurs formules pour un seul état ...
par exemple:
(H²D²)3(B²D²)3 qui permute les arêtes: état s = (HA)<->(HP) et (HB)<->(BP)
(H²G²)3(B²G²)3 qui permute les arêtes: état s = (HA)<->(HP) et (HB)<->(BP)

Ou encore, à l'état résolu e:
A4 ==> état résolu e
[HD]6 ==> état résolu e
I ==> état résolu e

Comme on dit qu'elles sont toutes identiques, il faut alors dire: il y a une seule formule pour un état mais il y a des différentes façons d'écrire la formule.
(H²D²)3(B²D²)3 = (H²G²)3(B²G²)3
D'=D3
De même à l'état résolu e:
il y a une seule formule pour l'état e mais il y a plusieurs l'écriture de cette formule
A4 = [DH]6 = I

C'est exactement quand vous écrivez:
* 1/2 = 0,5 = 3/6
l'inverse de 2 est unique mais il y a plusieurs l'écriture
ou encore
permutation identique id
* id = (a) = (b)
la permutation identique id est unique , mais il y a plusieurs l'écriture
de même soit p un 3-cycle
* p = (a,b,c) = (b,c,a) = (c,a,b)
la permutation p est unique , mais il y a plusieurs l'écriture

Résumons

- Bien que M et G soient isomorphes mais ils sont très différents, leur rôle est différent , un éléments de M possède plusieurs l'écriture, pas pour G . M agit sur G et non à l'inverse, et M agit sur X mais pas G
- Beaucoup de gens pensent que M c'est le groupe du Rubik's Cube, c'est-à-dire l'ensemble des mouvements est le groupe du Rubik's Cube. MAIS NON !! (M,.) agit (opère) sur G, ou sur les étiquettes X={1,2,3,...,48} c'est tout !! , mais on peut dire |M| = |G|

- Beaucoup de gens pensent que la rotation A par exemple fait bouger les sommets (parce que visuellement c'est ça). MAIS NON !!! la rotation A "ordonne", à la permutation de bouger les sommets, c'est la permutation qui bouge les sommets (elle exécute l'orde de A). Mais pourquoi ça ? c'est simple c'est dans l'écriture de la permutation !!!
Nommons les sommets par exemple a, b, c quand on écrit:
p = (a,b,c) c'est bien
p(a)=b, p(b)=c et p(c)=a ==> p déplace a en b , etc ...
mais jamais
A(a)=b, A(b)=c et A(c)=a !!!
On voit donc bien que p bouge a en b - p(a)=b -

Voici ce qu'il faut retenir:
La rotation A∈M agit sur les étiquettes, crée donc une permutation p∈Sx des étiquettes, cette permutation p peut être "coupée" ou se transforme en 4 morceaux (u,x,v,y)∈G ces 4 morceaux forme ce qu'on appelle un état du Cube, et l'ensemble de ces états muni d'une loi assez compliquée forme un groupe G ce qu'on appelle le groupe du Rubik's Cube.

Quelques états intéressants

1. Le 4Spots

Le 4Spot ω : échanger les faces (A,P) et (G,D)
4Spot = ω = BP²A²BH'G²D²H' = [ha][hd] t
est un état intéressant, car il fait partie d'un état superloin (antipode, longueur=26) le SuperFlip4Spots = ∏ c'est le seul état superloin qu'on connait !

4Spot = ω = BP²A²BH'G²D²H' = [ha][hd] t

2. Le SuperFlip

On démontre (à part l'état résolu e) qu'il y a un seul état Φ qui commute avec tout le monde càd :
Φ s = s Φ , pour tout état s
Cet état Φ se nomme SuperFlip
Le but est de trouver une formule associé à cet état

¤ En 1992 Dik T. Winter a trouvé une formule de longueur 20f pour le Superflip, plus tard (1995) Michael Reid démontrait que la longueur de Superflip est 20f, autrement dit la formule de Dik T. Winter est minimale en f-rotation.

¤ En Jan/1995 Michael Reid a trouvé une formule de longueur 24 pour le Superflip, plus tard (Fev/1995) Jerry Bryan démontrait que la longueur de Superflip est 24, autrement dit la formule de Michael Reid est minimale.

Le SuperFlip Φ : 12 arêtes retournées
SuperFlip = Φ = D'H²PG' .AH'PBA .HB'GB² .A'DP'BA' .H'P'HB'
|Φ| = 24
Le SuperFlip joue un rôle important, il est le seul (à part l'identité e) dans le centre de G (le groupe du Rubik's Cube).

SuperFlip = Φ = D'H²PG' .AH'PBA .HB'GB² .A'DP'BA' .H'P'HB'

3. Le SuperFlip4Spot

Le SuperFlip4Spot ∏ : Il est composé du SuperFlip et du 4Spot, c'est le seul état superloin (longueur=26) qu'on connait !
SuperFlip4Spot = ∏ = H²B²G A² .H'BD² PH'B'D. GA²D HB' D'GHA'P'
Michael Reid a trouvé cette formule (1998) par ordinateur
et a prouvé que c'est une des plus courte formule |∏| = 26
En Août 2014 Tomas Rokicki et Morley Davidson a démontré que le diamètre du Rubik's Cube est 26 (33 ans de galère !!!)
Donc le SuperFlip4Spot est le seul état qui atteint le diamètre du Rubik's Cube.

SuperFlip4Spot = ∏ = H²B²G A² .H'BD² PH'B'D. GA²D HB' D'GHA'P'

On a une merveilleuse formule : ∏ = Φ ω = ω Φ

L'algorithme

Un algorithme de résolution d'entrée K est une suite finie d'instructions (d'actions) en lignes L1, L2, ..., Ln
  1. Chaque ligne désigne une seule action: Soit placer, soit pivoter, soit ranger, ....
  2. Chaque ligne utilise des formules F de K, leur inverse, leurs puissances, leurs conjugés (QFQ') , et les rotations cube tX où Q=une formule, X = rotation de base {H,B,A,P,G,D}
    exemple
    L1, Placer les centres : F tD F'
    L2, Placer les arêtes : F. G'FG
    L3, Pivoter les sommets : F4
    ....
Et on peut tenir le cube comme on veut.

Posons-nous la question suivante: Combien de formules qu'utilise un algorithme ?
Donc il est raisonnable de dire que le nombre de formules qu'utilise l'algorithme c'est le nombre de formules dans l'entrée pour faire fonctionner l'algorithme.

Certaine partie de la résolution n'a pas besoin de l'algorithme , c'est intuitif et on convient de noter cette partie "0" ça signifie "pas besoin de formules, c'est intuitif"

Exemples
K = {T=[DG'], Q=[GD']}
Algo A:
-Placer les sommets : 0 , c'est intuitif, pas besoin de formules
-Placer les centres: T²
-Pivoter les sommets : T3 Q3
Algo A utilise 2 formules
Pendant l'étape par ex , "placer les centres" on peut tenir le cube comme on veut et utiliser la conjugaison de T² càd des trucs de la forme XT²X' où X est une formule.
L'utilisation de la conjugaison est normal, car la formule T² ne déplace que certains centres précises donc à elle seule ne peut pas placer tous les centres, il faut T² et ses conjugués XT²X'.

K = {θ=A[DH]A'.H }
Algo B:
-Placer les arêtes: θ
-Placer les sommets: θ
-Pivoter les arêtes: θ²
-Pivoter les sommets: θ4
Algo B utilise 1 formule

Algo C:
-Si les arêtes sont en état impair alors H
-Placer les arêtes: P²H'G'D.P²GD'H'.P²
-Pivoter les arêtes: AH²A² .B' [H' G' ]B. A²H' A' H'
-Placer des sommets: D² .P²DAD'. P²DA' D
-Pivoter les sommets: HAB'A²H .G²H'G². AH'A²BA²
Algo C utilise 5 formules

Algo D:
K = {θ=A[DH]A'.H , ζ=[DH]}
-Placer des arêtes; θ
-Pivoter les arêtes: θ²
-Placer des sommets: ζ.G'ζ'G
-Pivoter les sommets: θ4
Algo D utilise 2 formules



[1] 2 3 4 5 6 7 8

Accueil

DMJ: 21/06/2021









Facile

Moyen

Difficile

Les Crazy

Les Bandages

Les Stars

Divers

Le MathCubing

Quiz (Master Cube)