Confusion entre états et classe (orbite)

Sur le net, il y a beaucoup de confusions .... à éviter.
Avatar de l’utilisateur
morphocode
Megaminx
Megaminx
Homme
Balance
Messages : 655
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Confusion entre états et classe (orbite)

Message non lupar morphocode » Mar 4/05/2021 11:17

Si vous chercher le nombre d'états du Pocket sur internet vous verrez peut-être le nombre 3674160 aulieu de 88179840.
En fait les auteurs qui proposent le nombre 3674160 comme le nombre d'états du Pocket, confondent entre "état" et "classe (=orbite)" !!
Pour comprendre il faut revenir tout au début de l'histoire....

En 1993, Jerry Bryan écrivait un article expliquant le calcul du diamètre du Pocket (cet article est mal compris par beaucoup de gens).
Pour ce faire Bryan a classé les états du Pocket suivant un certain nombre de critères, plus précisement suivant le groupe de déplacement D
du cube (qui contient 24 éléments),
deux états s, t sont dans la même classe ssi:
s ~ t ⇔ ∃f∈D tel que s•f = t
du coup les états du Pocket sont partagés en 3674160 classes (de 24 éléments chaqu'une)

Ces classes forme un graphe T dont le diamètre est le même que celui du Pocket,
Bryan a fait un programe informatique et a trouvé le diamètre de T vallait 14 donc le diamètre du Pocket aussi,
mais le diamètre du Pocket c'est le diamètre du graphe d'états ===> d'où la confusions 3674160 est le nombre d'états du Pocket.


distance ==> nombre d'états
0 ==> 1
1 ==> 12
2 ==> 114
3 ==> 924
4 ==> 6539
5 ==> 39528
6 ==> 199926
7 ==> 806136
8 ==> 2761740
9 ==> 8656152
10 ==> 22334112
11 ==> 32420448
12 ==> 18780864
13 ==> 2166720
14 ==> 6624

NOTE : L'erreur se propage à la vitesse grande V à cause des copier/coller (brut, sauvage...) et qu'elle est difficile à corriger.
l'article publiait en 1993 on est en 2021 (28 ans après) on voit encore des texts notant 3674160 comme le nombre d'états du Pocket !!!

:cdingue: :facher: O\O
Dernière édition par morphocode le Mer 2/06/2021 09:14, édité 1 fois.
Image

Avatar de l’utilisateur
morphocode
Megaminx
Megaminx
Homme
Balance
Messages : 655
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Re: Confusion entre états et classe (orbite)

Message non lupar morphocode » Mar 1/06/2021 08:55

Si vous chercher le nombre d'états du Rubik's Cube sur internet vous verrez parfois le nombre 901 083 404 981 813 616
au lieu de 43 252 003 274 489 856 000 .
En fait ceux qui proposent le nombre 901 083 404 981 813 616 comme le nombre d'états du Rubik's Cube, confondent entre "état" et "classe (=orbite)" !!
Voyons de plus près ...

Avant de parler "mathématiquement" du Rubik's Cube il faut "orienter" le Cube càd déclarer officielement qui est le Haut, qui est la Droite ....
traditionnellement on oriente le Cube ainsi:
H(aut)=b(lanc), B(as)=j(aune), A(vant)=v(ert), P(ostérieur)=k(lein), G(auche)=o(range), D(roite)=r(ouge).

Parmi ces trois images lequel est l'état résolu ? et pourquoi ?


Image
image (a)

Image
image (b)

Image
image (c)


l'image (b) est l'état résolu car les centres ne sont pas bougés, comme les centres de (a) et de (c) ont bougé ces images
ne présentent pas l'état résolu ! et pourtant si on tient un Rubik's Cube résolu à la main ces 3 états jouent le même rôle ....
d'où l'idée de classer (mettre dans la même boîte) les états du Rubik's Cube suivante un certain nombre de critères .... à fin que les états (a), (b), (c) soient dans la même classe, dans la même boîte.
Quelles sont les critères ?
En 1994 Dan Hoey a proposé de classer les états suivant le critère J-conjugaison où J est le groupe des isométries du cube (ce groupe a 48 éléments),
plus précisement deux états s,t sont dans la même classe (même boîte) ssi:
il existe un f€J tel que (e•f) (s•f-1) = t , où e=état résolu
Avec un programme informatique il a trouvé 901 083 404 981 813 616 classes , chaque classe contient donc un certain nombre d'états.

Classe de Type . . . . . Nombre de classes
=============== . . . . =======================
Identité (1) = 901 083 401 551 872 000

RotCentre/±4 (3+3) = 18 432

RotCentre/2 (3) = 955 514 880

RotArete/2 (6) = 318 504 960

RotSommet/±3 (4+4) = 629 856

------------------

SymCentrale (1) = 955 514 880

RéfRot/4 (6) = 55 296

Sym (3) = 1 146 617 856

SymArete (6) = 53 084 160

RéfRot/6 (8) = 1 296

------------- -----------------------------------------
48 éléments , Total = 901 083 404 981 813 616 classes

Le nombre 901 083 404 981 813 616 est donc le nombre de classes (les classes J-conjugaison) et non le nombre d'états de G.

NOTE : Le but de la classification des états pour réduire le graphe du Rubik's Cube, en effet les classes forment un nouveau graphe T (dont le diamètre est le même que celui du Rubik's Cube) beaucoup plus petit que le graphe du Rubik's Cube, on peut donc plus facilement l'expoter comme la cherche du diamètre ....

¤ Rot=Rotation, Sym=Symétrie, Réf=Réflexion
Image