La symétrie J-conjugaison

28 Jui 2013

Préface Parfois on entend dire que:
- Le nombre 43252003274489856000 d'états du Rubik's Cube n'est pas bon !! on a compté plusieurs fois le même état et donc il faut le diviser par 24 car le Cube a 24 symétries!!
- Ou encore ce nombre n'est pas tout à fait correct !! car on a compté plusieurs fois le même état, le nombre correct est 901083404981813616, c'est le nombre d'état distincts du Rubik's Cube ???

Alors où est la vérité ?


Au début ...

Il faut remonter vers les années 1980 , on s'est posé la question suivante:
-Quel est le nombre de rotations nécessaire b, pour restaurer le Rubik's Cube à partir de n'importe quel état ?
On peut prendre par ex b = 65256 c'est bien, mais il y a beaucoup trop de rotations non utilisées ....
de même si on prend b = 23 , il y a des états qu'on ne peut pas s'en sortir avec 23 rotations par ex l'état SuperFlip !!
Chercher b revienr à chercher le diamètre du Rubik's Cube.

Donc on a le graphe (le graphe Cayley) du Rubik's Cube mais ce graphe est énorme !!! l'idée est de réduire ce graphe à fin que la recherche du diamètre soit accessible par l'ordinateur ...
En 1994 Dan Hoey a eu l'idée suivante : On va classer les états suivant un certain nombre de critère, ainssi on réduit le nombre sommets donc on réduit le graphe. Mais alors quels sont les critères ? les critères utilisés connus sous le nom de: "La symétrie J-conjugaison" !!

La symétrie J-conjugaison

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).

Pour bien comprendre le concept "symétrie J-conjugaison" observons ces trois images ci-dessous
Parmi ces trois images lequel est l'état résolu ? et pourquoi ?

image (a) image (b)

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.

Le critère utilisé est la "symétrie J-conjugaison" où J est le groupe des isométries du cube, il a 48 éléments en voici :

Isométries positives
===================
Identité (1)
RotCentre/±4 (3+3)
RotCentre/2 (3)
RotArete/2 (6)
RotSommet/±3 (4+4)

Isométries négatives
====================
SymCentrale (1)
RéfRot/4 (6)
Sym (3)
SymArete (6)
RéfRot/6 (8)
----------------------
Total = 48 éléments

J agit (opère) sur G :
G x J ---> G
(s,f) ---> s•f

on définit la symétrie J-conjugaison ainsi:

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

Formule de Burnside

Rappelle sur la formule de Burnside.
Soient K un groupe fini et X un ensemble fini, K agit sur X (on passe un élément de X à un autre par un élément de K)
On pose Fg = { x ∈X / x•g = x } l'ensemble des points fixes de g∈K , Fg ⊂ X

Lemme de Burnside
w = 1/|K| . ∑g∈K |Fg|
où w = le nombre d'orbites
C'est la somme des points fixes quand g parcourt K

On prend K=J et X=G
Grâce à cette formule et un programme informatique on a trouvé 901 083 404 981 813 616 classes . Les classes se distribuent en fonction des éléments de J de la façon suivante:

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

Chaque classe contient donc un certain nombre d'états.

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.

Les gens disent donc n'importe quoi !! (souvent d'ailleurs).

1 2 3 4 5 [6] 7 8

Accueil

DMJ: 10/06/2021









Facile

Moyen

Difficile

Les Crazy

Les Bandages

Les Stars

Divers

Le MathCubing

Quiz (Master Cube)