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 (au maximum) avec b rotations ??
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

Pour chaque formule V on associe une longueur notée |V| c'est le nombre de rotations qu'elle contient:
ex: |H| = 1, |H'| = 1, |H²| = 2, |I| = 0
V = HB²PA'D3G'²
|V| = 10

Attention!! V = T n'implique pas |V| = |T| !!!
par ex A' = A3 ==> |A'| ≠ |A3|


Le nombre minimum de rotations


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

- 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

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 groupes 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 = { HK, HS, HT, ... } où les K, S, T, ... (dans 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 (puisque M est fini -c'est ici donc qu'on a besoin que M soit fini-), parmi ces éléments il y a un "plus court" , et on peut prendre ce "plus court" comme représentant de la classe.
Soient: HK = Hψ1, HS = Hψ2, HT = Hψ3, ... où les ψi∈M et sont des plus courtes 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 = < H, B, A, P, G, D >
H1 = < H, B, A², P², G, D >
H2 = < H, B, A², P², G², D² >
H3 = < H², B², A², P², G², D² >
H4 = {I}

Et il utilisait un programme informatique qui charchait les longueurs et il trouvait que pour passer :
¤ de G à E1, il y a 2048 ψi et le maxi |ψi|=14 , càd L=14
¤ de E1 à E2, il y a 1082565 ψi et le maxi |ψi|=26 , càd L=26
¤ de E2 à E3, il y a 29400 ψi et le maxi |ψi|=30 , càd L=30
¤ de E3 à E4, il y a 663552 ψi et le maxi |ψi|=34 , càd L=34

Soit au total b=104 rotations , 20 ≤ m ≤ 104
NOTE: Avec quelques astuces on arrive à diminuer b=90 (14+20+26+30) .

D'après le diagrame de marquages
H1 signifie : toutes les arêtes sont bien orientées
H2 signifie : toutes les arêtes et les sommets sont bien orientées

==> Passer de G à E1 signifie : à partir de l'état s∈G il existe une formule V , |V|≤14 tel que s•V=t et on peut résoudre t en utilisant uniquement les rotations de H1
==> Passer de E1 à E2 signifie : à partir de l'état t∈E1 il existe une formule T , |T|≤26 tel que t•T=q et on peut résoudre q en utilisant uniquement les rotations de H2
==> Passer de E2 à E3 signifie : à partir de l'état q∈E2 il existe une formule C , |C|≤30 tel que q•C=c et on peut résoudre c en utilisant uniquement les rotations de H3
==> Passer de E3 à E4={e} signifie : à partir de l'état c∈E3 il existe une formule N , |N|≤34 tel que c•N=e

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

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

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

Théorème (Tomas Rokicki, Morley Davidson 2014): quel que soit l'état s, il existe une formule V avec |V|≤26 telle que s•V=e
Autrement dit le diamètre du Rubik's Cube est 26. huuff !! 33 ans de galère !!...

Le SuperFlip de formule
Φ = D'H²PG'AH'PBAHB'GB²A'DP'BA'H'P'HB'
(Mike Reid trouvé par ordinateur, plus courte formule |Φ|=24)
Le SuperFlip4Spot de formule
Π = H²B²GA²H'BD²PH'B'DGA²DHB'D'GHA'P'
(Mike Reid trouvé par ordinateur, prouvé par Mike Reid plus courte formule 26)
Π = ADG'PBAD'HBPD'B'D'PH²B²P²DGB²DG (minimale)
c'est le seul état SuperLoin (antipode) que l'on connait.

|Φ|=24
|Π|=26
Le diamètre du Rubik's Cube est: 26

Remarques

Parfois on compte |A²|=1 on dit qu'on utilise la métrique face-rotation et on note avec un 'f' :
ex: |H| = 1f, |H'| = 1f, |H²| = 1f, |I| = 0f
V = HB²PA'D3G'²
|V| = 7f
Dans ce cas on démontre que le diamètre du Rubik's Cube vaut 20f

Théorème (Tomas Rokicki, Herbert Kociemba, Morley Davidson, et John Dethridge, 2010): quel que soit l'état s, il existe une formule V avec |V|≤20f telle que s•V=e

Voici quelques états les SuperLoin en f-rotation (20f, antipodes)
Le SuperFlip dont la formule est
Φ = AH'A²B'PHD'A'GB'D'H'GHP'B²D'AH²B² (|Φ|=20f)
X = DGH²AH'BA²D²P²GH²A'P'HD²BA²HD²H
Y = AH'A²B'PHD'A'GB'D'H'GHP'B²D'AH²B²
Il y a environ 490.000.000 états SuperLoin en f-rotation

|Φ|=20f
|Π|=20f

1 2 3 4 5 6 [7] 8

Accueil

DMJ: 08/03/2022









Facile

Moyen

Difficile

Les Crazy

Les Bandages

Les Stars

Divers

Le MathsCubing

Quiz (Master Cube)