Confusion entre état et classe (orbite)

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

Confusion entre état et classe (orbite)

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

Le Pocket et le nombre 3674160
====================================

Si vous cherchez le nombre d'états du Pocket sur internet vous verrez peut-être le nombre 3674160 au lieu de 88179840.

Observons les trois images (a), (b) et (c) ci-dessous

Image
image (a)
Image
image (b)
Image
image (c)

Pour un Jury de compétition ces états représentent l'état résolu.
Et le nombre d'états (dans le sens des Jurys ) est m=3674160
En réalité m=3674160 est le nombres de classes d'équivalence !


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 le critère nommé D-symétrie, plus précisément suivant le groupe de déplacement D du cube (qui contient 24 éléments).

D agit librement (= seul id a des points fixes) sur G
G x D -> G
(s,f) -> s•f = t

à '•' on associe la relation d'équivalence ~ suivante:
deux états s , t sont dans la même classe ssi:
s ~ t ⇔ ∃f∈D tel que s•f = t

La formule de Burnside donne:
w = 1/|D| ∑|Ff| ; somme sur f∈ D
comme l'action est libre Ff = Ø si f ≠ id et Fid = G
w = |G|/24 = 88179840/24 = 3674160
du coup les états du Pocket sont partagés en 3674160 D-classes (de 24 éléments chaque une)

Ces classes forme un graphe T dont le diamètre est le même que celui du Pocket :
BRYAN a fait un programme informatique et a trouvé le diamètre de T qui valait 14 donc le diamètre du Pocket aussi,

Les distances du graphe T:

Distance D-classes
==============================
0 ==> 1
1 ==> 6
2 ==> 27
3 ==> 120
4 ==> 534
5 ==> 2256
6 ==> 8969
7 ==> 33058
8 ==> 114149
9 ==> 360508
10 ==> 930588
11 ==> 1350852
12 ==> 782536
13 ==> 90280
14 ==> 276
===========================
Total D-classes : 3674160


Comme 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.
D'autre part, dans une compétition, le Jury considère qu'un élément s ∈ cl(e) de la classe de e est l'état résolu d'où la confusion entre classe et état


On a fait aussi un programme qui calcule directement le diamètre du Pocket et ça donne

Les distances du graphe 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
===============================
total états: 88179840


Voici un script en GAP qui calcule le nombre d'états du Pocket


Code : Tout sélectionner


#gap_pocket.txt
#         5     7
#            H   
#         3     1
#25    23|21    19|17    31|29    27
#   G    |   A    |   D    |   P 
#43    37|39    33|35    45|47    41
#         11    9
#            B   
#         13    15
# Pocket=le groupe Pocket (= Rubik sans arêtes)
pH :=  (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
pB :=  (9,15,13,11)(33,45,41,37)(35,47,43,39);
pA :=  (1,35,11,23)(17,9,37,3)(19,33,39,21);
pP :=  (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
pG :=  (3,39,13,27)(21,11,41,5)(23,37,43,25);
pD :=  (1,29,15,33)(17,31,45,35)(19,7,47,9);
pPsi := (1,17,19);

LAMBDAPLUS :=  Group( pH, pB, pA, pP, pG, pD, pPsi );
LAMBDA := Group( pH, pB, pA, pP, pG, pD );
N := 3 ;;

Print( "\n" );
Print( "|LAMBDA+| = ",Size( LAMBDAPLUS ), "\n" );
Print( "|LAMBDA| = ", Size( LAMBDA ) , "\n" );
Print( "N = ",  N , "\n" );
Print( "|G+| = ", Factorial(8) * (3^8) , "\n" );
Print( "|G| = |G+|/N = ",( Factorial(8) * (3^8) ) / N , "\n" );





:cdingue: :facher: O\O (confusion entre état et classe)
Dernière édition par Morphocode le Lun 3/01/2022 18:02, édité 2 fois.
Image

Avatar de l’utilisateur
Morphocode
Crazy
Crazy
Homme
Balance
Messages : 784
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Re: Confusion entre état et classe (orbite)

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

Le Rubik's Cube et le nombre 901 083 404 981 813 616
==================================================

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 .

Voyons de plus près ...

Avant de parler "mathématiquement" du Rubik's Cube il faut "orienter" le Cube càd déclarer officiellement 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).

La J-Symétrie

Parmi ces trois images ci-dessous 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 dans la main ces 3 états jouent le même rôle (pour un Jury de compétition) ...
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 .... afin que les états (a), (b), (c) soient dans la même classe, dans la même boîte.
Quelles sont les critères ?


On utilise le critère J-Symétrie , où J est le groupe des isométries du cube (ce groupe a 48 éléments),
plus précisément deux états s et t (on ignore les centres) sont dans la même classe (même boîte) ssi:
il existe un f€J tel que s•f = t (on ignore les centres)
On troue N = |G|/48 le nombre de J-classes


==> En 1994 Jerry BRYAN a proposé de classer les états suivant un autre critère nommé "J-conjugaison"
plus précisément deux états s=e•V , V€M et t sont dans la même classe (même boîte) ssi:
il existe un f€J tel que e•(f V f-1) = t , où e=état résolu
il a calculé et a trouvé 901 083 404 981 813 616 classes , chaque classe contient donc un certain nombre d'états .

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

RotCentre±90° (3+3) = 18 432

RotCentre180° (3) = 955 514 880

RotArete180° (6) = 318 504 960

RotSommet±120° (4+4) = 629 856

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

SymCentrale (1) = 955 514 880

SymRot±90° (3+3) = 55 296

SymPlan (3) = 1 146 617 856

SymArete (6) = 53 084 160

SymRot±120° (4+4) = 1 296

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

Le nombre 901 083 404 981 813 616 est donc le nombre de J-conjugaison classes 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 (gardant certaines propriétés du Rubik's Cube) beaucoup plus petit que le graphe du Rubik's Cube, on peut donc plus facilement l'exploiter comme la recherche du diamètre ....

¤ Rot=Rotation, Sym=Symétrie
Image

Avatar de l’utilisateur
Morphocode
Crazy
Crazy
Homme
Balance
Messages : 784
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Re: Confusion entre états et classe (orbite)

Message non lupar Morphocode » Jeu 1/02/2024 18:47

GAP 4.4.12 ICI
https://www.gap-system.org/Releases/4.4.12.html


Voici un programme en GAP qui calcule le nombre de J-conjugaison classes
Dans la fenêtre de cmd
cd\
cd gap4r4
cd bin
gap < gap_J-rugik.txt

https://fan2cube.fr/gap_J-rubik.txt

Image
Image

Code : Tout sélectionner


#         5  6  7
#         4  H  8
#         3  2  1
#25 28 23|21 26 19|17 32 31|29 30 27
#38 G  36|12 A  10|34 D  40|16 P  14
#43 44 37|39 42 33|35 48 45|47 46 41
#         11 18 9
#         20 B  24
#         13 22 15

# Iso=le groupe isometrie du cube
j1 := (6, 46, 18, 26)(8, 14, 24, 12)(38, 48, 36, 32)(2, 30, 22, 42)(16, 20, 10, 4)(28, 40, 44, 34)
(5, 45, 11, 17)(7, 13, 9, 3)(21, 31, 41, 35)(43, 33, 23, 29)(1, 25, 15, 37)(47, 39, 19, 27) ;
j2 := (6, 16, 22, 14)(8, 24, 20, 4)(38, 30, 40, 46)(2, 10, 18, 12)(28, 32, 48, 44)(34, 42, 36, 26)
(5, 31, 15, 43)(7, 45, 13, 25)(21, 19, 33, 39)(1, 35, 11, 23)(47, 41, 27, 29)(3, 17, 9, 37);
Iso := Group(j1,j2) ;

# Dep=le groupe isometrie+ du cube (24) Dep = ssg de Iso
Dep := Group(  ( 1,11)( 2,18)( 3, 9)( 4,24)( 5,15)( 6,22)( 7,13)( 8,20)(10,12)
        (14,16)(17,37)(19,39)(21,33)(23,35)(25,45)(26,42)(27,47)(28,48)(29,41)
        (30,46)(31,43)(32,44)(34,36)(38,40),
      ( 1,15)( 2,22)( 3,13)( 4,20)( 5,11)( 6,18)( 7, 9)( 8,24)(10,16)(12,14)
        (17,45)(19,47)(21,41)(23,43)(25,37)(26,46)(27,39)(28,44)(29,33)(30,42)
        (31,35)(32,48)(34,40)(36,38),
      ( 1,17,19)( 2,32,10)( 3,31,33)( 4,40,42)
        ( 5,45,39)( 6,48,12)( 7,35,21)( 8,34,26)( 9,23,29)(11,25,47)(13,43,41)
        (14,22,44)(15,37,27)(16,18,28)(20,38,46)(24,36,30),
      ( 1,35,11,23)( 2,10,18,12)( 3,17, 9,37)( 4, 8,24,20)( 5,31,15,43)
        ( 6,16,22,14)( 7,45,13,25)(19,33,39,21)(26,34,42,36)(27,29,47,41)
        (28,32,48,44)(30,40,46,38)  ) ;

# Rubik=le groupe du Rubik's Cube      
pH := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
pB := (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);
pA := (2,34,18,36)(26,10,42,12) (1,35,11,23)(17,9,37,3)(19,33,39,21);
pP := (6,38,22,40)(30,14,46,16) (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
pG := (4,12,20,14)(28,36,44,38) (3,39,13,27)(21,11,41,5)(23,37,43,25);
pD := (8,16,24,10)(32,40,48,34) (1,29,15,33)(17,31,45,35)(19,7,47,9);
Rubik := Group(pH,pB,pA,pP,pG,pD);

# Pocket=le groupe Pocket (= Rubik sans arêtes)
#pH :=  (1,3,5,7)(17,21,25,29)(19,23,27,31) ;
#pB :=  (9,15,13,11)(33,45,41,37)(35,47,43,39);
#pA :=  (1,35,11,23)(17,9,37,3)(19,33,39,21);
#pP :=  (7,25,13,45)(29,27,41,47)(31,5,43 ,15);
#pG :=  (3,39,13,27)(21,11,41,5)(23,37,43,25);
#pD :=  (1,29,15,33)(17,31,45,35)(19,7,47,9);
#Pocket := Group(pH,pB,pA,pP,pG,pD);

G := Rubik ;;
GG := "Rubik" ;;
J := Iso ;;
JJ := "J" ;;
 
etat := 0 ;;
Jcjg := 0 ;;

    # Les classes des sous groupes conjugaisons de J
    Cl := ConjugacyClassesSubgroups( J );;
    ptfixe := [];

   Print("\n\n No \tetat \tclasses-conjugaisons\n" );
   Print("================================================== \n" );
    # pour tout classe Cl[i], on cherche les pt fixes générés par Cl[i]
    for i  in [Length(Cl),Length(Cl)-1..1]  do

        # prendre un représentant
        H := Representative( Cl[i] );

        # les pt fixes engendrés par H
        aux := Size( Centralizer( G, H ) );

        # si Q inclus dans H,on supprime dans H les pt fixes générés par Q
        for k  in [Length(Cl),Length(Cl)-1..i+1]  do
            for Q  in Elements( Cl[k] )  do
                if IsSubgroup( Q, H )  then
                  aux := aux - ptfixe[k];   
                fi;
            od;
        od;

        # sauver les pt fixes génégrés par H
        ptfixe[i] := aux;

        # print N° classe
        Print("\n ", i, ":\t" );

        # le nbr de pt fixes (= nbr états) générés par Cl[i]
        Print( Size(Cl[i]) *  ptfixe[i], "\t" );
      etat := etat + ( Size(Cl[i]) *  ptfixe[i] );

        # le nbr de J-cjg classes générés par Cl[i]
        Print( (Size(Cl[i]) *  ptfixe[i]) /  Index(J,H), " " );
      Jcjg := Jcjg + ( (Size(Cl[i]) *  ptfixe[i] )/  Index(J,H) );
      
    od;
   Print("\n\n ",GG," = ", etat, "\n" );
   Print("\n ",JJ,"-cjg = ", Jcjg , "\n" );
   
      


Image
Image

Avatar de l’utilisateur
Morphocode
Crazy
Crazy
Homme
Balance
Messages : 784
Inscription : Lun 25/11/2013 17:06
Localisation : Paris
Contact :

Re: Confusion entre état et classe (orbite)

Message non lupar Morphocode » Ven 12/07/2024 18:57

Le Domino et le nombre 406425600
====================================

Si vous cherchez le nombre d'états du Domino sur internet vous verrez peut-être le nombre 406425600 au lieu de 1625702400 .

Observons les trois images (a), (b) et (c) ci-dessous

Image
image (a)
Image
image (b)
Image
image (c)

Pour un Jury de compétition ces états représentent l'état résolu.
Et le nombre d'états (dans le sens des Jurys ) est m=406425600
En réalité m=406425600 est le nombres de classes d'équivalence !


On va classer les états du Domino suivant le critère nommé D-symétrie, où D = { H90, H-90, H180, id }
H90 = rotation le Cube entier à 90° suivant l'axe Haut-Bas
H-90 = rotation le Cube entier à -90° suivant l'axe Haut-Bas
H180 = rotation le Cube entier à 180° suivant l'axe Haut-Bas
|D| = 4



D agit librement (= seul id a des points fixes) sur G
G x D -> G
(s,f) -> s•f = t

à '•' on associe la relation d'équivalence ~ suivante:
deux états s , t sont dans la même classe ssi:
s ~ t ⇔ ∃f∈D tel que s•f = t

La formule de Burnside donne:
w = 1/|D| ∑|Ff| ; somme sur f∈ D
comme l'action est libre Ff = Ø si f ≠ id et Fid = G
w = |G|/4 = 1625702400/4 = 406425600
du coup les états du Domino sont partagés en 406425600 D-classes (de 4 éléments chaque une)

Script en GAP pour calculer le nombre d'état du Domino

Code : Tout sélectionner


# gap_domino.txt
#         5  6  7
#         4  H  8
#         3  2  1
#25 28 23|21 26 19|17 32 31|29 30 27
#43 44 37|39 42 33|35 48 45|47 46 41
#         11 18 9
#         20 B  24
#         13 22 15
#H=49,B=50
#
#Domino : sommets et arêtes n'ont pas d'orientations !!
pH := (2,4,6,8)(26,28,30,32) (1,3,5,7)(17,21,25,29)(19,23,27,31);;
pB := (18,24,22,20)(42,48,46,44) (9,15,13,11)(33,45,41,37)(35,47,43,39);;
pA := (2,18)(26,42) (1,11)(17,37)(19,39)(3,9)(23,35)(21,33);;
pP := (6,22)(30,46) (7,13)(31,43)(29,41)(5,15)(25,45)(27,47);;
pG := (4,20)(28,44) (3,13)(21,41)(23,43)(5,11)(27,39)(25,37);;
pD := (8,24)(32,48) (1,15)(19,47)(17,45)(7,9)(29,33)(31,35);;

LAMBDA := Group( pH,pB, pA,pP, pG, pD );;
Print( "\n |LAMBDA| = ",Size( LAMBDA ), "\n" );
Print( "|G| = ", Factorial(8) * Factorial(8)  , "\n" );



Image
Image