Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #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énnombrement

Voilà, j'ai encore besoin d'aide... neutral
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
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
Promath


Un promath- actif dans un forum actif
  • |
  • Répondre

#0 Pub

 #2 - 19-04-2012 15:06:42

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3207
Lieu: Luxembourg

Aide sur le dénombremen

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 sur lz 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 qur le dénombrement

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,896E+3

Aide sur le dénombremennt

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 dénmobrement

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éombrement

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

 #8 - 20-04-2012 11:23:21

Promath-
Elite de Prise2Tete
Enigmes résolues : 18
Messages : 1416
Lieu: Au fond de l'univers

AAide sur le dénombrement

Je n'ai pas trop compris l'histoire des moyennes avec les rotations inchangées. sad


Un promath- actif dans un forum actif

 #9 - 20-04-2012 12:25:54

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

Aide sur le dénombremen

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 qur le dénombrement

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

Aiide sur le 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,896E+3

Aide sur le dénombrment

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

 #13 - 20-04-2012 20:46:01

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 914
Lieu: Seahaven island

aide sur le dénombremenr

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 : 3207
Lieu: Luxembourg

Aide sur le dénomrement

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,896E+3

Aide sur le dénombreement

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

aife sur le dénombrement

Donc on est bien sur 70?
Maintenant que je sais le nombre, je vais faire le cas par cas.(enfin essayer)neutral

Mais j'ai 1 question:combien y a t-il de pièces qui ont 4 noirs, 4 blancs? big_smile

En tout cas , Merci, merci beaucoup. smile

1+2+8+14=25
25+25+23=73
J'ai du me tromper encore...


Un promath- actif dans un forum actif

 #17 - 21-04-2012 09:43:20

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,896E+3

zide sur le dénombrement

Compte ... big_smile
http://www.prise2tete.fr/upload/gwen27-aideaudenombrement.jpg

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
22-07-2015 Blabla
07-12-2020 Blabla
P2T
01-04-2012 Blabla
P2T
Aide technique par racine
09-11-2012 Blabla
16-12-2009 Blabla
27-04-2015 Blabla
21-10-2010 Blabla
P2T
Rugby par kosmogol
04-02-2011 Blabla
P2T
09-12-2011 Blabla

Mots clés des moteurs de recherche

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete