Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 06-02-2012 23:09:05
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 349
Drôles de grilles
Salut à tous,
Voici encore un problème de dénombrement... Regarder la grille suivante :
Elle a la particularité suivante : elle est constituée de 36 petits carrés dont 9 sont "troués".
Si on tourne la grille d'un 1/4 de tour, d'un 1/2 tour ou de 3/4 de tour, les trous que l'on obtient ne sont jamais superposés
aux autres (de sorte qu'ainsi on décrit les 36 petits carrés).
J'ai deux questions :
1. Combien peut-on fabriquer de telles grilles?
2. Quel algorithme employer pour fabriquer "aléatoirement" une telle grille?
Fred.
PS : Nerosson aura tout de suite reconnu leur origine... N'oubliez pas qu'une partie du site est en chantier (sur mon ordi simplement pour le moment).
Hors ligne
#4 07-02-2012 12:31:47
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 349
Re : Drôles de grilles
Salut,
Je suis d'accord avec la réponse jpp.
Mais ma méthode de dénombrement ne fait pas apparaitre le nombre [tex]4^9[/tex] comme naturel.
C'est presque un incident de factorisation. Et la votre?
Fred.
Hors ligne
#6 07-02-2012 15:53:09
- nerosson
- Membre actif
- Inscription : 21-03-2009
- Messages : 1 658
Re : Drôles de grilles
Salut à tous,
Bien entendu, il s'agit d'une grille tournante. Comme il me semble bien avoir fait un "jus" sur ce sujet dans le passé et dans le site cryptographie, je n'y reviens pas.
Pourquoi vous autres, les aigles des mathématiques et de l'informatique, vous laissez tomber de votre hauteur des solutions sans vous mettre à la portée du premier demeuré venu (vous voyez de qui je veux parler...).
Combien de grilles tournantes peut-on fabriquer avec un carré de 9. Je suis un peu mortifié d'avouer que je ne m'étais pas posé la question.
Sauve qui peut ! je vais essayer de raisonner !
Premier trou : 36 possibilités.
Deuxième trou : 32 possibilités.
Troisième trou : 28 possibilités.
Quatrième trou : 24 possibilités.
Cinquième trou : 20 possibilités.
Sixième trou : 16 possibilités.
Septième trou : 12 possibilités.
Huitième trou : 8 possibilités.
Neuvième trou : 4 possibilités.
Ce qui me donne :
36 x 32 x 28 x 24 x 20 x 16 x 12 x 8 x 4 = 4 (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2) = 4 x 9! = 4 x 362880 = 1 451 520.
J'attends avec anxiété de savoir si je n'ai pas dérâpé quelque part !
Dernière modification par nerosson (07-02-2012 16:05:22)
Hors ligne
#7 07-02-2012 16:28:48
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 349
Re : Drôles de grilles
C'est presque cela Nérosson, sauf que :
1. Ton 4 est en facteur de chaque terme du produit, et non d'un seul...
2. Si on échange le 1er trou et le 9ème trou, on obtient la même grille. Il faut donc tenir compte des permutations des trous...
Fred.
PS: Nérosson a bonne mémoire. Il a effectivement écrit quelque chose sur le forum aux sujets des grilles tournantes.
Hors ligne
#9 07-02-2012 19:59:40
- nerosson
- Membre actif
- Inscription : 21-03-2009
- Messages : 1 658
Re : Drôles de grilles
Salut à tous,
@Fred,
Moi, je me focalise sur mon raisonnement en neuf lignes. Je n'ai pas vu que parmi ces possibilités, il pourrait y en avoir qui feraient double emploi, bien que je me sois posé la question.
Je fais un premier trou : il est évident que je peux le placer en 36 positions, ce qui, pour la suite, "invalide" trois autres positions. Mon deuxième trou, je peux donc le placer en 32 positions ("32 positions" : Yoshi va encore me regarder d'un oeil torve et soupçonneux...).
J'ai donc pour les deux premiers 36 x 32 = 1152 positions. Et c'est là que je commence à comprendre que tu as bien raison. En effet, la position case 29 pour le premier trou et case 31 pour le deuxième trou, c'est kif-kif position 31 pour le pour le premier trou et case 29 pour le deuxième (sous réserve que le premier n'exclut pas le deuxième).
Combien y a-t-il jusque là de doubles emplois ? A mon avis : 32 x36 = 1152, autrement dit, toutes les positions sont en double et il n'y aurait jusqu'ici que 576 positions valables par exemple 29-31 mais pas 31-29.
Je peux choisir mon troisième trou parmi 36 - 8 = 28 cases, ce qui me conduirait à 576 x 28 = 16 128 possibilités, sauf que (si la case choisie a le numéro 15, les combinaisons 15-29-31, 29-15-31 et 29-31-15 font triple emploi, ce qui, jusqu'ici me donnerait 16 128 /3 = 5 376 possibilités valables.
Après le quatrième trou, je devrais avoir (5 376 x 24) /4 = 32 256 possibilités valables,
après le cinquième trou, je devrais avoir (32 256 x 20) / 5 = 129 024 possibilités valables,
après le sixième trou, je devrais avoir (129 024 x 16) / 6 = 344 064 possibilités valables,
après le septième trou, je devrais avoir (344064 x 12) / 7 = 589 824 possibilités valables,
après le huitième trou, je devrais avoir (589 824) x 8) / 8 = 589 824 possibilités valables,
après le neuvième trou, je devrais avoir (589 824 x 4) / 9 = 262 144 possibilités valables.
J'obtiens, par d'autre voies, le même résultat que jpp, résultat que confirme Fred (sacré jpp, je l'aurai un jour, je l'aurai... comme dit la pub).
Hors ligne
#10 08-02-2012 20:28:08
- amatheur
- Membre
- Inscription : 02-10-2011
- Messages : 299
Re : Drôles de grilles
salut
pour la question 2, je fais comme suit: j'aurais besoin d'un générateur de nombre pseudo-aléatoire, et d'une grille déjà faite, je coderai les trous avec les chiffres de 1 à 9, je demande à mon générateur de me fournir des nombre de 9 chiffres dont la forme décimale est d [tex]{a}_{1}..{a}_{9}[/tex] , une fois le chiffre obtenu, je transformerai ma grille en faisant subir au trou i une rotation de [tex]{a}_{i}\frac{\pi }{4}[/tex] dans le sens horaire ou anti horaire selon que la somme des chiffres [tex]{a}_{1}\,à\,{a}_{i-1}[/tex] est paire ou impaire " je ne sais pas si ce dernier astuce ajoute quelque chose à la complexité de la méthode ou la rend plus vulnérable!" qu'en pense les spécialistes de la crypto?
Dernière modification par amatheur (08-02-2012 20:28:46)
Hors ligne