![](/img/vague-bas-gauche.png) |
#1 - 19-04-2012 09:39:03
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Aide sur le dénombremet
Voilà, j'ai encore besoin d'aide... ![neutral](img/smilies/neutral.png) Hier, je me suis mis à calculer le nombre de pièces qui pouvaient exister dans un jeu. Mais je n'ai pas réussi.
![http://img826.imageshack.us/img826/3914/jeudeformes.png](http://img826.imageshack.us/img826/3914/jeudeformes.png) Comme je l'ai dessiné plus haut, ce jeu consiste en une pièce de 8 parties coloriables.
Cette pièce est parfaitement carrée, et a ainsi 4 axes de symétrie. Je voulais calculer le nombre de pièces qui pouvaient exister, en remplissant chaque case grise, soit par du noir, soit par du blanc.
MAIS, c'est là le mais, ce n'est pas 256 pièces, car je veux omettre les pièces équivalentes, (c'est à dire si on colorie les cases d'en haut, on ne va pas créer une autre pièce qui est noire sur le côté). C'est à dire à une symétrie près. La question est: Combien de pièce y aura t il au final?
Merci de votre aide ![smile](img/smilies/smile.png) Promath
Un promath- actif dans un forum actif
#2 - 19-04-2012 15:06:42
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
Ade sur le dénombrement
Bonjour, Je dirais 2^8 = 256 (comme tu l'as fait remarqué) que je divise successivement par 4 et par 2 pour tenir compte des rotations et des symétries. Je divise seulement par 2 pour les symétries car sinon il y a double emploi avec certaines rotations. Au final, ça donne 32 possibilités. Bonne journée.
#3 - 19-04-2012 15:52:26
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Aide usr le dénombrement
Je crois que faire ainsi je marche pas, car lorsqu'on divise par le nombre de symétries, le but est de ne pas compter deux fois la même pièce (éviter donc de la compter dans un sens puis dans l'autre etc...) mais il y a de nombreuses pièces qu'on ne compte déjà qu'une fois (ou moins que 8 fois) (avec la méthode du 256): les pièces symétriques.
Je pense que la bonne manière de procéder est de faire le dénombrement par familles de symétrie. Tant de pièces totalement symétriques + tant de pièces comportant uniquement la symétrie verticale etc...
#4 - 19-04-2012 17:23:15
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
aide sur le dénombeement
Merci. @Franky: Comme l'a dit clydevil, il y en a plus de 32 @Clydevil: Merci! Mais c'est long, non????
Un promath- actif dans un forum actif
#5 - 19-04-2012 18:06:00
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
Aide sur el dénombrement
J'en trouve 1 à 0 case , 2 à 1 case , 6 à 2 cases , 13 à 3 cases , 19 à 4 cases , 13 à 5 cases , 6 à 6 cases , 2 à 7 cases et 1 à 8 cases
Soit au total : 1 + 2 + 6 + 13 + 19 + 13 + 6 + 2 + 1 = 63
#6 - 20-04-2012 09:14:41
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
aide sur le sénombrement
Je voulais dire "a une rotation près"... J'en dénombre 1+8+14+25+14+8+1=71
Un promath- actif dans un forum actif
#7 - 20-04-2012 09:57:06
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Aide sur le dénombremnt
J'avais souvenir d'avoir croisé cela: http://eljjdx.canalblog.com/archives/20 … 85364.html
Comme ici tes classes d'équivalence sont "jolies" vu que ce sont de simple symétries/rotation, tu pourras peut être appliquer cela ![big_smile](img/smilies/big_smile.png) Si ce genre de chose ne s'applique pas, même si c'est long, je ne vois pas d'autre manière que de te taper le dénombrement par famille d'équivalence symétrie etc... ![tongue](img/smilies/tongue.png)
#8 - 20-04-2012 11:23:21
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
aide qur le dénombrement
Je n'ai pas trop compris l'histoire des moyennes avec les rotations inchangées. ![sad](img/smilies/sad.png)
Un promath- actif dans un forum actif
#9 - 20-04-2012 12:25:54
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
aide sur le sénombrement
Promath- a écrit:Je voulais dire "a une rotation près"... J'en dénombre 1+8+14+25+14+8+1=71
8 (ou bien c'est 1 )solutions à 1 case noire ? La case est dans un coin ou au milieu d'un côté non ?
#10 - 20-04-2012 17:42:54
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
Aide sur le dénombremnet
Pardon, je me suis trompé...
Un promath- actif dans un forum actif
#11 - 20-04-2012 19:19:26
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Aide sur e dénombrement
Re,
Oui donc j'ai lu la page et c'est bien exactement notre cas.
Nous on a un ensemble de 256 éléments potentiellement différents.
Dans cet ensemble on déclare (arbitrairement c'est notre choix) que certains sont équivalents, mais on ne le fait pas n'importe comment: on a définit une suite d'opérations sur nos éléments ou si l'un est l'image d'un autre par une de nos opération alors c'est identique.
Nos opérations en questions sont les 4 symétries axiales, 3 rotations (1/4, 2/4 et 3/4 de tour) ainsi que l'identité (pas d’opérations).
Au final ces 8 opérations forment ce qu'on appelle un groupe.
Wiki rappelle: un groupe est un ensemble muni d'une loi de composition interne associative admettant un élément neutre et, pour chaque élément de l'ensemble, un élément symétrique.
Notre groupe est ici l'ensemble de nos 8 transformations muni de l'opération de composition. Quelque soit notre manière de composer nos transformations ça en donnera une de nos 8. (le groupe est stable avec la loi donnée). La composition est bien associative dans notre cas, ie par exemple(R1.S1).R2 donne le même effet que R1.(S1.R2). Son élément neutre c'est l'opération identité (car si on la compose à n'importe quoi il reste n'importe quoi). Enfin quelque soit l'opération considérée il existe une opération ou si on la compose avec donne l'identité (ça c'est pour l'élément symétrique) Donc voila pour notre groupe de transformations agissant sur notre ensemble d'éléments.
Et dans ce cadre le lemme de Burnside s'applique, et ça se fait ainsi: Pour chaque transformations de notre groupe on compte le nombre d'éléments inchangés ça donne:
id -> 256 (ne change personne) R1 -> 4 (avec les coins et les milieu bord, sans les coin et avec les milieux bord, avec etc...) R2 -> 16 pièces possibles inchangées. (il faut que les briques opposées soient de même type) R3-> 4 SVerticale -> 32 (on fixe la gauche et les milieu des bords haut bas et ça contraint le reste) SHorizontale -> 32 SDiago1 -> 32 SDiago2 ->32
Et la le lemme est magique il dit de faire la moyenne entre ces 8 nombres: (256 + 4 + 16 + 4 + 32 + 32 + 32 + 32) / 8 = 51.
La réponse est donc 51.
Et la comme on ne trouve pas pareil je cherche ou j'ai mal appliqué le théorème ou ou tu as fait une bourde :p
Ha oui toi tu ne comptes pas les rotations comme des opérations inchangeantes? donc pas de bol car avec uniquement les symétries et l'identité on a plus un groupe (car la composée de deux symétries donne autre chose qu'une symétrie, en l’occurrence une rotation) Cela dit c'est certainement incohérent de ne pas compter les rotations car ça voudrait dire qu'une pièce A verticalement symétrique a une pièce B elle même diagonalement symétrique à une pièce C alors A et C ne serait pas identique de ton point de vu (alors que je serais près à parier que si :p) Donc je reste sur le 51.
Au passage une remarque: par contre ne tenir compte que des rotations et considérer que les pièces symétriques ne sont pas les mêmes çà marche, car les rotations forment bien un groupe. Et notre moyenne de Burnside donnerait: (256+4+16+4)/4 = 70 éléments différents. (avec rotations uniquement)
#12 - 20-04-2012 20:25:50
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
aide sur lr dénombrement
En faisant une rotation de 2 crans sur les 256 premiers nombres en binaire,
00000000 00000000 00000000 00000000 = 0 0 0 0 00000001 00000100 00010000 01000000 = 1 4 8 16 ...
jusqu'à 256
Je ne garde dans la première colonne que les éléments non encore vus donc qui ne font pas l'objet d'une symétrie déjà vue...
Il me reste 71 éléments ce qui est assez proche de ta réponse :
1.0 : 00000000 2.1 : 00000001 3.2 : 00000010 4.3 : 00000011 5.5 : 00000101 6.6 : 00000110 7.7 : 00000111 8.9 : 00001001 9.10 : 00001010 10.11 : 00001011 11.13 : 00001101 12.14 : 00001110 13.15 : 00001111 14.17 : 00010001 15.18 : 00010010 16.19 : 00010011 17.21 : 00010101 18.22 : 00010110 19.23 : 00010111 20.25 : 00011001 21.26 : 00011010 22.27 : 00011011 23.29 : 00011101 24.30 : 00011110 25.31 : 00011111 26.34 : 00100010 27.35 : 00100011 28.37 : 00100101 29.38 : 00100110 30.39 : 00100111 31.41 : 00101001 32.42 : 00101010 33.43 : 00101011 34.45 : 00101101 35.46 : 00101110 36.47 : 00101111 37.51 : 00110011 38.53 : 00110101 39.54 : 00110110 40.55 : 00110111 41.57 : 00111001 42.58 : 00111010 43.59 : 00111011 44.61 : 00111101 45.62 : 00111110 46.63 : 00111111 47.85 : 01010101 48.86 : 01010110 49.87 : 01010111 50.89 : 01011001 51.90 : 01011010 52.91 : 01011011 53.94 : 01011110 54.95 : 01011111 55.102 : 01100110 56.103 : 01100111 57.106 : 01101010 58.107 : 01101011 59.110 : 01101110 60.111 : 01101111 61.119 : 01110111 62.122 : 01111010 63.123 : 01111011 64.126 : 01111110 65.127 : 01111111 66.170 : 10101010 67.171 : 10101011 68.175 : 10101111 69.187 : 10111011 70.191 : 10111111 71.255 : 11111111
Pour simplifier, je considère en partant d'une case donnée, dans un sens donné, qu'une combinaison n'est valable que si sa traduction en binaire est inférieure ou égale à la traduction de ses rotations de 2 crans.
Si je n'ai pas commis d'erreur, les mathématiciens devraient pouvoir en sortir une règle, mais là , je ----->![roll](img/smilies/roll.png)
#13 - 20-04-2012 20:46:01
- Clydevil
- Expert de Prise2Tete
- Enigmes résolues : 29
- Messages : 914
- Lieu: Seahaven island
Aide sur l dénombrement
Salut, Mouarf j'ai 70 et toi 71 donc forcement c'est que j'ai oublié un cas dans le comptage pour faire la moyenne dans la formule de burnside ou que tu as compté un cas en trop. Je vais voir ou ca couille.
#14 - 20-04-2012 22:05:47
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3218
- Lieu: Luxembourg
Adie sur le dénombrement
Le litige porte forcément sur le nombre de combinaisons à quatre cases, compte tenu de la "symétrie" des solutions.
#15 - 21-04-2012 07:08:42
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
Aie sur le dénombrement
70 effectivement, je l'ai refait sur tableur au lieu de le faire à la main... 89 était déjà traité avec 86.
1 0 00000000 2 1 00000001 3 2 00000010 4 3 00000011 5 5 00000101 6 6 00000110 7 7 00000111 8 9 00001001 9 10 00001010 10 11 00001011 11 13 00001101 12 14 00001110 13 15 00001111 14 17 00010001 15 18 00010010 16 19 00010011 17 21 00010101 18 22 00010110 19 23 00010111 20 25 00011001 21 26 00011010 22 27 00011011 23 29 00011101 24 30 00011110 25 31 00011111 26 34 00100010 27 35 00100011 28 37 00100101 29 38 00100110 30 39 00100111 31 41 00101001 32 42 00101010 33 43 00101011 34 45 00101101 35 46 00101110 36 47 00101111 37 51 00110011 38 53 00110101 39 54 00110110 40 55 00110111 41 57 00111001 42 58 00111010 43 59 00111011 44 61 00111101 45 62 00111110 46 63 00111111 47 85 01010101 48 86 01010110 49 87 01010111 50 90 01011010 51 91 01011011 52 94 01011110 53 95 01011111 54 102 01100110 55 103 01100111 56 106 01101010 57 107 01101011 58 110 01101110 59 111 01101111 60 119 01110111 61 122 01111010 62 123 01111011 63 126 01111110 64 127 01111111 65 170 10101010 66 171 10101011 67 175 10101111 68 187 10111011 69 191 10111111 70 255 11111111
#16 - 21-04-2012 09:38:43
- Promath-
- Elite de Prise2Tete
- Enigmes résolues : 18
- Messages : 1416
- Lieu: Au fond de l'univers
iAde sur le dénombrement
Un promath- actif dans un forum actif
#17 - 21-04-2012 09:43:20
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
aide sur le débombrement
Compte ... ![big_smile](img/smilies/big_smile.png)
![http://www.prise2tete.fr/upload/gwen27-aideaudenombrement.jpg](http://www.prise2tete.fr/upload/gwen27-aideaudenombrement.jpg)
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |