Méthode de Thistlethwaite

28 Jui 2013

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 16 rotations donc il faut au minimum 17 rotations...

2- Une autre question aussi intéressante: On se donne un nombre b et se pose la question suivante:
Quel que 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 longueur |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²| = 1f

Un raisonement simple permet de trouver qu'il y a des états qu'on ne peut pas s'en sortir avec 16f rotations (a=17f)

- Le 1er coup : 6 faces à choisir {H,B,A,P,G,D} , on prend par ex la face A, on a alors 3 choix : A, A', A² et comme il y a 6 faces on a: 3x6=18 choix.
A: A,A',A² ⇒ 3x6 = 18

- Le 2ème coup : on évite de reprendre A sinon on revient au même point, donc 5 faces à choisir {H,B,P,G,D} ,on prend par ex la face D
D: D,D',D² ⇒ 3 x 5 = 15, comme on a 18 choix au 2ème coup d'où
18 x 15

- Le 3ème coup : on évite de reprendre D sinon on revient au même point, mais on peut reprendre A car D a modifié A, on ne revient pas au même point si on reprend A, donc 5 faces à choisir {H,B,A,P,G} , on prend par ex P
P: P,P',P² ⇒ 3 x 5 = 15, mais on a 18x15 choix d'où
18 x 15 x 15

- Le 4ème coup : on évite de reprendre P, donc 5 faces à choisir {H,B,A,G,D} , on prend par ex H
H: H,H',H² ⇒ 3 x 5 = 15,
mais on a maintenant 18x15x15 choix d'où
18 x 15x15x15
......

Le nombre d'états en n rotations vaut donc:
S = 18 + 18.15 + 18.152 + 18.153 + ... + 18.15n-1 (il y a n ternes)
S = 18(1 + 15 +152 +153+ ... +15n-1)
S = 18(15n - 1)/(15 - 1) ≈ 9.15n/7
15n ≈ 7x4,3x1019/9
15n ≈ 3,34x1019
En passant par ln
n ≈ [ln(3,34)+19ln(10)]/ln(15)
n ≈ 16,60
d'où
n = 17

la borne inférieure est donc a = 17f autrement dit il existe des états dont on n'a aucun espoir de les restaurer avec 16f rotations !
on a 17f ≤ m ≤ b

Analyse

Pour trouver le majorant b, Thistlethwaite a une idée géniale suivante:

On a d'un côté (M, .) le groupe des formules, et de l'autre côté (G, .) le groupe du Rubik's Cube, le groupe des états.
Si on se donne une tour {Hi}i de sous proupes de M
M = H0 ⊃ H1 ⊃ H2 ⊃ ... ⊃ Hn = {I}
à cette tour il correspond à une tour {Ei}i de sous ensembles de G
G = E0 ⊃ E1 ⊃ E2 ⊃ ... ⊃ En = {e}
où les Ei sont des états atteints par les Hi
Ainsi on a donc un algorithme de résolution (on part de G et on arrive à {e}), on pourrait alors calculer le nombre de rotations utilisées dans cet algorithme donc un majorant b de m.

Les classes

Pour comprendre l'idée de Thistlethwaite, càd comment il compte le nombre de rotations, il faut 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 prendre simplement une tour à un étage :
Soit H un sous-groupe de M (H n'est pas forcement normal) et E les états atteints par H
H ⊂ M, et E ⊂ G
H étant donné, les classes H\M ={ HR, HS, HT, ... } où les R, S, T, ... ∈M sont, donc aussi données . Soient s un état quelconque de G et Q la formule associée à s : e•Q = s ∈ G


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: HR = Hψ1, HS = Hψ2, HT = Hψ3, ... où les ψi∈M et sont des plus courts et |ψi|=longueur
on pose
L = Max {|ψ1|, |ψ2|, |ψ3|, ...}

Q étant un élément de M , mais comme les classes forment une partition de M donc Q se trouve quelque part dans Hψ1, ou Hψ2, ou Hψ3, ...
supposons que Q soit dans Hψ3 ça signifie:
Q = Γψ3 avec Γ∈H
d'où

Q = Γψ3
Qψ'3 = Γ
e•(Qψ'3) = e•Γ
(e•Q)•ψ'3 = e•Γ
s•ψ'3 = e•Γ = t ∈E , car Γ est dans H
d'où:
s•ψ'3 = t ∈E

Donc on passe de l'état s à l'état t au maximum L rotations.

NOTE Il est clair qu'on ne cherche pas les ψi à 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 ψi) , il vaut |M|/|H| donc on peut toujours trouver
L = max {|ψ1|, |ψ2|, |ψ3|, ...} par ordinateur. Donc H est donné , L est donné.

Méthode de Thistlethwaite

Dans cette section on applique le couple (M,H) par les couples (Hi,Hi+1)
Thistlethwaite a proposé la suite Hi des sous groupes de M suivantes :
H0 = M = < A, P, G, D, H, B >
H1 = < A², P², G, D, H, B >
H2 = < A², P², G², D², H, B >
H3 = < A², P², G², D², H², B² >
H4 = {I}

Et il utilisait un programme informatique qui charchait les f-longueur et il trouvait que pour passer :
¤ de G à E1, il y a 2048 ψi et le maxi |ψi|=7f , càd L=7f
¤ de E1 à E2, il y a 1082565 ψi et le maxi |ψi|=13f , càd L=13f
¤ de E2 à E3, il y a 29400 ψi et le maxi |ψi|=15f , càd L=15f
¤ de E3 à E4, il y a 663552 ψi et le maxi |ψi|=17f , càd L=17f

Soit au total b=52f rotations , 18f ≤ m ≤ 52f
NOTE: Avec quelques astuces on arrive à diminuer b=45f (7f+10f+13f+15f) dans la méthode de Thistlethwaite
D'après nos marquages, l'orientation
H1 signifie : toutes les arêtes sont bien orientées
H2 signifie : toutes les arêtes et les sommets sont bien orientées


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 les années on augmente le minorant a et on diminue le majorant b

On compte |A²| = 1f

Juillet, 1981 : Morwen Thistlethwaite, 17f ≤ m ≤ 52f
Décembre, 1990 : Hans Kloosterman, 17f ≤ m ≤ 42f
Mai, 1992 : Michael Reid, 17f ≤ m ≤ 39f
Mai, 1992 : Dik Winter, 17f ≤ m ≤ 37f
Janvier, 1995 : Michael Reid a trouvé le SuperFlip a=20f, 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
Finalement en Juillet, 2010 : Tomas Rokicki, Herbert Kociemba, Morley Davidson, et John Dethridge, 20f ≤ m ≤ 20f

Autrement dit le diamètre du Rubik's Cube en f-rotation (|A²|=1f) est exactement 20f. Il fallait 30 ans pour répondre à cette question.

Note :
Voici quelques états les plus difficiles: les superloin (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 superloin

Remarque Il est naturel de poser la question: quel est le diamètre du Rubik's Cube ?
La réponse est 26 (Oût 2014)

On compte |A²|=2

Avec le même raisonnement pour la métrique face, on peut trouver un minorant pour la métrique quart.

- Le 1er coup : 6 faces à choisir {H,B,A,P,G,D} , on prend par ex la face A, on a alors 2 choix : A, A' et comme il y a 6 faces on a: 2x6=12 choix.
A: A,A' ⇒ 2x6 = 12

- Le 2ème coup : on évite de reprendre A sinon on revient au même point, donc 5 faces à choisir {H,B,P,G,D} ,on prend par ex la face D
D: D,D' ⇒ 2 x 5 = 10, comme on a 12 choix au 2ème coup d'où
12 x 10

- Le 3ème coup : on évite de reprendre D sinon on revient au même point, mais on peut reprendre A car D a modifié A, on ne revient pas au même point si on reprend A, donc 5 faces à choisir {H,B,A,P,G} , on prend par ex P
P: P,P' ⇒ 2 x 5 = 10, mais on a 12x10 choix d'où
12 x 10 x 10

- Le 4ème coup : on évite de reprendre P, donc 5 faces à choisir {H,B,A,G,D} , on prend par ex H
H: H,H' ⇒ 2 x 5 = 10,
mais on a maintenant 12x10x10 choix d'où
12 x 10x10x10
......

Le nombre d'états en n rotations vaut donc:
S = 12 + 12.10 + 12.102 + 12.103 + ... + 12.10n-1 (il y a n ternes)
S = 12(1 + 10 +102 +103+ ... +10n-1)
S = 12(10n - 1)/(10 - 1) ≈ 4.10n/3
10n ≈ 3x4,3x1019/4
10n ≈ 3,22x1019
En passant par ln
n ≈ [ln(3,22)+19ln(10)]/ln(10)
n ≈ 19,50
d'où
n = 20

la borne inférieure est donc a = 20 autrement dit il existe des états dont on n'a aucun espoir de les restaurer avec 19 rotations !
on a 20 ≤ m ≤ b

Durant les années on augmente le minorant a et on diminue le majorant b

On compte |A²| = 2

Janvier, 1981 : Dan Hoey montre que : 21 ≤ m ≤ 140
Juillet, 1981 : Morwen Thistlethwaite montre que b=52x2=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 trouvé le SuperFlip a=24, 24 ≤ m ≤ 42
Août, 1998 : Michael Reid a trouvé le SuperFlip4Spot a=26, 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
Finalement Août, 2014 : Tomas Rokicki et Morley Davidson démontrent que b=26, 26 ≤ m ≤ 26

Autrement dit le diamètre du Rubik's Cube 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)
∏ = SuperFlip4Spot = 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 (minimale)

|∏|=26
|Φ|=24
|Φ|=20f
Le diamètre du Rubik's Cube est: 26 ou 20f

1 2 3 4 5 6 [7] 8

Accueil

DMJ: 22/06/2021









Facile

Moyen

Difficile

Les Crazy

Les Bandages

Les Stars

Divers

Le MathCubing

Quiz (Master Cube)