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)
RotCentre180° (3)
RotCentre±90° (3+3)
RotArete180° (6)
RotSommet±120° (4+4)
Isométries négatives
====================
SymCentrale (1)
SymPlan (3)
RéflRot (6)
SymArete (6)
Réfl (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 F
g = { x ∈X / x•g = x } l'ensemble des points fixes de g∈K , F
g ⊂ X
Lemme de Burnside
w = 1/|K| . ∑
g∈K |F
g|
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
RotCentre180° (3) = 955 514 880
RotCentre±90° (3+3) = 18 432
RotArete180° (6) = 318 504 960
RotSommet±120° (4+4) = 629 856
------------------
SymCentrale (1) = 955 514 880
SymPlan (3) = 1 146 617 856
RéflRot (6) = 55 296
SymArete (6) = 53 084 160
Réfl (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.
1 2 3 4 5 [6] 7 8
Accueil
DMJ: 09/05/2023