Méthode de Thistlethwaite

15 Mar 2017

Position du problème En résovant le Rubik's Cube, on se pose deux questions naturelles suivantes:

1- On se donne un nombre a, et se pose la question suivante:
existent-ils des situations (des états) dont on n'a aucun espoir de restaurer le Cube avec un nombre de rotations moindre que a ? autrement dit il faut au minimum a rotations pour s'en sortir.
exemple si on prend a = 2, il est clair qu'il y a des états qu'on ne peut pas s'en sortir avec une seule rotation.
Les états dont on peut s'en sortir avec une seule rotation sont des états assez simples. il est donc naturelle de se demander s'il y des états plus compliqués ?, on augmente donc a, par exp a=10,11,... nous montrerons par un raisonnement simple qu'il y a des états dont on ne peut pas s'en sortir avec 17 rotations donc il faut au minimum 18 rotations...

2- Une autre question aussi intéressante: On se donne un nombre b et se pose la question suivante:
Quelque soit l'état, est il toujours possible de s'en sortir avec b rotations (au maximum) ??
par exemple si on prend b=36540, peut on toujours s'en sortir avec b=36540 rotations ? la réponse est sûrement 'oui', on a donc l'intérêt de diminuer b

Pour a : on augmente a pour avoir les états plus compliqués
Pour b : on diminue b pour économiser les rotations
Soit m le nombre de rotations de la restauration, le problème revient donc à minorer et majorer m: a ≤ m ≤ b

Il y a deux façons de compter les rotations:
* Si on compte A² vaut 2 , on note |A²| = 2
exp: |H| = 1, |H'| = 1, |H3| = 3, |I| = 0
* Si on compte A² vaut 1 on dit, dans ce cas qu'on utilise la métrique face et on note |A²| = 1f ou |A²|f = 1
exp: |H| = 1f, |H'| = 1f, |H3| = 2f, |H4| = 2f , |I| = 0f
donc pour chaque formule F on associe à une longeur |F| ou |F|f exemple
F = HB²PA'D3G'²
|F| = 10
|F| = 7f
Attention!! U = V n'implique pas |U| = |V| !!!


Le nombre minimum de rotations


Dans tout ce qui suit nous utilisons la métrique face, donc |A²| = 1

Un raisonement simple permet de trouver qu'il y a des états qu'on ne peut pas s'en sortitr avec 17 rotations (a=18)
- Le 0eme coup neutre, il n'y a rien à faire : 1
- Le 1eme coup on a 3 choix par ex: A, A', A² et comme il y a 6 faces donc: 3x6=18
- Le 2eme coup on a: 18x18=182
- Le 3eme coup on a: 18x18x18=183
Le nombre d'états en n rotations vaut donc:
S = 1 + 18 + 182 + 183 ... + 18n-1 (il y a n ternes)
S = (18n-1)/(18-1) ≈ 18n/17
18n/17 ≈ 4,3x1019
18n ≈ 73,1x1019
En passant par ln
n ≈ [ln(73,1)+19.ln(10)]/ln(18)
n ≈ 48,04/2,8
n ≈ 17,15
d'où
n = 18
la borne inférieure est donc a = 18f autrement dit il existe des états dont on n'a aucun espoir de les restaurer avec 17f f-rotations !
on a 18f ≤ m ≤ b

En 1995 Michael Reid démontre qu'il existe des états dont on ne peut pas s'en sortir avec 19f rotations (a=20f), par ex le superflip Φ (toutes les arêtes sont renverées), on a donc 20f ≤ m ≤ b. Il nous reste maintenant à trouver un majorant b de m.

Analyse

Pour ne pas alourdir les écritures on va nommer les pièces comme indique la fig ci-dessous, les xi sont des arêtes et les yi sont des sommets.


A chaqu'étape de résolution, on range les pièces petit à petit en faisant attention de ne pas détruire ce qu'on a fait.

Voici un algorithme de résolution:
On part un état s mélangé et Q la formule associée à s (e•Q = s).

1. Ranger les arêtes Bas E1 = {x9, x10, x11, x12}
Soit H1 l'ensemble des formules qui laissent E1 invariant.
H1 est un sous groupe de M, car les formules qui laissent invariant un ensemble forment un groupe. Remarque H1 n'est pas forcement normal.
Soit Q1 une formule telle que Q'1 range les arêtes Bas alors
QQ'1=T1 ∈H1 ; M ⊃ H1

2. Finir le Bas E2 = {x9, x10, x11, x12, y5, y6, y7, y8}
Soit H2 l'ensemble des formules qui laissent E2 invariant,
Soit Q2 une formule telle que Q'2 range les sommets Bas sans toucher E1 alors
T1Q'2=T2 ∈H2 ; H1 ⊃ H2 .

3. Finir l'équateur E3 = {x9, x10, x11, x12, y5, y6, y7, y8, x5, x6, x7, x8 }
Soit H3 l'ensemble de formules qui laissent E3 invariant,
Soit Q3 une formule telle que Q'3 range les arêtes-équateur sans toucher E2 alors
T2Q'3=T3 ∈H3 ; H2 ⊃ H3 .

4. Ranger les arêtes Haut E4 = {x9, x10, x11, x12, y5, y6, y7, y8, x5, x6, x7, x8, x1, x2, x3, x4 }
Soit H4 l'ensemble de formules qui laissent E4 invariant,
Soit Q4 une formule telle que Q'4 range les arêtes-Haut sans toucher E3 alors
T3Q'4=T4 ∈H4 ; H3 ⊃ H4 .

5. Finir le Haut E5 = {x9, x10, x11, x12, y5, y6, y7, y8, x5, x6, x7, x8, x1, x2, x3, x4, y1, y2, y3, y4}
Soit H5 l'ensemble de formules qui laissent E5 invariant, ⇒ H5 = I
Soit Q5 une formule telle que Q'5 range les sommets-Haut sans toucher E4 alors
T4Q'5=T5 ∈H5 ; H4 ⊃ H5 .

On voit donc qu'on a une suite d'inclusion de sous groupes de M
M ⊃ H1 ⊃ H2 ⊃ H3 ⊃ H4 ⊃ H5 = I
qui range étape par étape les pièces du Cube jusqu'à l'état résolu
∅ ⊂ E1 ⊂ E2 ⊂ E3 ⊂ E4 ⊂ E5 = Cube-résolu

A chaqu'algorithme de résolution on a une suite d'inclusion des sous groupes Hi ⊃ Hi+1 comme ci-dessus, et inversement si on a une suite d'inclusion des sous groupes Hi ⊃ Hi+1 de M on aura un algorithme de résolution, donc si la suite Hi est donnée on peut calculer le nombre maximal de rotations que utilise l'algorithme.
Telle est l'idée de Thistlethwaite

Les classes

Soit donc une suite d'inclusion de sous groupes de M
M ⊃ H1 ⊃ H2 ... ⊃ Hi ⊃ Hi+1 ... ⊃ Hn = I
Pour comprendre la méthode de Thistlethwaite, càd comment il compte le nombre de rotations, il faut donc connaître la notion de classes. Thistlethwaite a utilié les classes pour compter les rotations c'est vraiment génial comme l'angle d'attaque.

Pour fixer les idées on va placer dans un cas générique: Soientt E l'ensemble des pièces à ranger, et H l'ensemble de formules qui rangent les pièces de E. H est un sous-groupe de M et H laisse E invariant
H étant donné, les classes H\M ={ Ha, Hb, Hc, ... } sont donc aussi données . Soient s un état quelconque et Q la formule associée à s : e•Q = s


Une classe a un nombre fini d'éléments, parmi ces éléments il y a un "plus court" , et on peut prendre ce "plus court" comme représentant de la classe.
Soient: Ha = Hm1, Hb = Hm2, Hc = Hm3, ... où les mi sont des plus courts et |mi|=longeur
on pose
L = Max {|m1|, |m2|, |m3|, ...}

Q étant un élément de M , mais comme les classes forment une partition de M donc Q se trouve quelque part dans Hm1, ou Hm2, ou Hm3, ...
supposons que Q soit dans Hm3 ça signifie:
Q = Tm3 avec T∈H

e•Q = s
e•(Tm3) = s
(e•T)•m3 = s
e•T = s•m'3
s•m'3 = t avec t = e•T

On passe donc de l'état s à l'état t au maximum L rotations.

NOTE Il est clair qu'on ne cherche pas les mi à la main !!! , les ordinateurs sont là pour ça ...
En effet le nombre d'éléments d'une classe est fini, souvenez vous il vaut |H|. Donc on peut très bien faire un programme qui cherche le plus court élément d'une classe. Pour trouver L là aussi il y a un nombre fini de classes (de mi) , il vaut |M|/|H| donc on peut toujours trouver
L = max {|m1|, |m2|, |m3|, ...} par ordinateur. Donc H est donné , L est donné.

Méthode de Thistlethwaite

Dans cette section on applique le couple (M,H) par (Hi,Hi+1)
Thistlethwaite propose la suite Hi des sous groupes de M suivante
H0 = M = < G, D, A, P, H, B >
H1 = < G, D, A, P, H², B² >
H2 = < G, D, A², P², H², B² >
H3 = < G², D², A², P², H², B² >
H4 = I
Et il démontrait que pour ranger E1 le nombre maximum de rotations vaut L=7
E2 ==> L=13 rotations
E3 ==> L=15 rotations
E4 ==> L=17 rotations
Soit au total 52 rotations , 18f ≤ m ≤ 52f
Note: Avec quelques astuces on arrive à diminuer b=45f dans la méthode de Thistlethwaite

Remarque : Le travail Thistlethwaite est important, il nous dit deux choses:
1. On est sûr de s'en sortir !!.
2. Quelque soit l'état du Cube on le restaure au maximum 52f rotations.

Durant des années on diminue le majorant

métrique face |A²|f = 1
Juillet, 1981 : Morwen Thistlethwaite 18f ≤ m ≤ 52f
Décembre, 1990 : Hans Kloosterman 18f ≤ m ≤ 42f
Mai, 1992 : Michael Reid 18f ≤ m ≤ 39f
Mai, 1992 : Dik Winter 18f ≤ m ≤ 37f
Janvier, 1995 : Michael Reid 20f ≤ m ≤ 29f
Décembre, 2005 : Silviu Radu 20f ≤ m ≤ 28f
April, 2006 : Silviu Radu 20f ≤ m ≤ 27f
Mai, 2007 : Dan Kunkle and Gene Cooperman 20f ≤ m ≤ 26f
Mars, 2008 : Tomas Rokicki 20f ≤ m ≤ 25f
April, 2008 : Tomas Rokicki and John Welborn 20f ≤ m ≤ 23f
Août, 2008 : Tomas Rokicki and John Welborn 20f ≤ m ≤ 22f
Juillet, 2010 : Tomas Rokicki, Herbert Kociemba, Morley Davidson, et John Dethridge 20f ≤m≤ 20f

Autrement dit le nombre de Dieu pour le Rubik's Cube est exactement 20f en métrique face (|A²|f=1) . Il fallait 30 ans pour répondre à cette question.

Note :
Voici quelques états les plus difficiles: les Superdur (20f)
Superflip Φ = AH'A²B'P. HD'A'GB'. D'H'GHP'. B²D'AH²B² (|Φ|=20f)

X = DGH²AH'. BA²D²P²G. H²A'P'HD². BA²HD²H
Y = AH'A²B'P. HD'A'GB'. D'H'GHP'. B²D'AH²B²
Il y a environ 490.000.000 états Superdur

Remarque Il est naturel de poser la question: quel est le nombre maximal de rotation pour la métrique q-rotation (|A²|=2) ?
La réponse est 26 (Oût 2014)

métrique quart |A²|=2
Janvier, 1981 : Dan Hoey montre qu'il y a des états qui demandent au minimum 21 rotations 21 ≤ m ≤ 140
Juillet, 1981 : Morwen Thistlethwaite montre que b=104 rotations suffisent 21 ≤ m ≤ 104
Mai, 1992 : Michael Reid montre b=56, 21 ≤ m ≤ 56
Janvier, 1995 : Michael Reid 21 ≤ m ≤ 42
Janvier, 1995 : Michael Reid 22 ≤ m ≤ 42
Août, 1998 : Michael Reid a=26 superflip 26 ≤ m ≤ 42
Novembre, 2005 : Silviu Radu 26 ≤ m ≤ 40
Janvier, 2006 : Bruce Norskog 26 ≤ m ≤ 38
Janvier, 2006 : Silviu Radu 26 ≤ m ≤ 36
Mars, 2006 : Silviu Radu 26 ≤ m ≤ 35
Juillet, 2007 : Silviu Radu 26 ≤ m ≤ 34
Janvier, 2009 : Tomas Rokicki 26 ≤ m ≤ 32
Janvier, 2009 : Tomas Rokicki 26 ≤ m ≤ 31
Février, 2009 : Tomas Rokicki 26 ≤ m ≤ 30
Juin, 2009 : Tomas Rokicki 26 ≤ m ≤ 29
Août, 2014 : Tomas Rokicki et Morley Davidson démontrent finalement que le nombre de Dieu pour la métrique quart est 26. huuff !! 33 ans de galère !!...

Superflip Φ = D'H²PG' AH'PBA HB'GB² A'DP'BA' H'P'HB' (Mike Reid trouvé par ordinateur, plus courte formule |Φ|=24)
π=Flipspot = H²B²G A² H'BD² PH'B'D GA²D HB' D'GHA'P' (Mike Reid trouvé par ordinateur, prouvé par Mike Reid plus courte formule 26)
π = ADG'PBA D'HBPD' B'D'PH² B²P²D GB²DG

|π|=26
|Φ|=24
|Φ|=20f

1 2 3 4 5 6 [7] 8

Accueil

DMJ: 15/03/2017









Facile

Moyen

Difficile

Les Crazy

Les Stars

Divers

Théorie des Twists

Quiz (Master Cube)