Forum de mathématiques - Bibm@th.net

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Exercice de dénombrement

Bonjour,

Je m'entraîne sur les exercices de dénombrement du site, tout allait bien mais sur l'exercice 6 j'obtiens des résultats différents de la correction:
https://www.bibmath.net/ressources/inde … &type=fexo

SUJET:

Dans cet exercice, on attend des réponses qui ne sont pas des valeurs numériques, mais des expressions en termes de factorielles, sous la forme la plus simple possible.
1. Combien y-a-t-il de façons de répartir les 52 cartes d'un jeu entre 4 joueurs N, S, E, O, chacun possédant 13 cartes.
2. Parmi ces façons, combien y-en-a-t-il qui sont telles que chaque joueur n'a qu'une seule couleur (par exemple, N a les 13 piques, S a les 13 coeurs,...)?
3. Combien y-a-t-il de façons que deux joueurs quelconques aient chacun une seule couleur?

Mon travail:

Les questions et 1 et 2 c'est okay, j'ai la même chose que la correction

Pour la question 3:

J'obtiens [tex]\frac{72 \times 26!}{13!^2}-5 \times 4![/tex]

Alors que la correction obtient [tex]\frac{72 \times 26!}{13!^2}-6 \times 4![/tex]

J'ai l'impression qu'il y a une coquille dans la correction car ils ont obtenu comme moi [tex]\binom{4}{2}-1[/tex]
Mais au lieu d'écrire que cela fait [tex]5[/tex]  ils ont écrit [tex]6[/tex].
Est-ce que vous pourriez s'il vous plaît me dire si mon résultat est bien correct?

Merci beaucoup à vous

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Exercice de dénombrement

Bonjour

  Oui il y a bien une coquille dans la correction et ton résultat est correct. Je vais corriger !

F.

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Re : Exercice de dénombrement

Bonjour,

D'accord, merci pour votre réponse ^^

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Exercice de dénombrement

Bonsoir,

Et pour rester sur le jeu de bridge (passionnant au demeurant), il y a eu un post intéressant  pour dénombrer le nombre de mains (13 cartes, 4 couleurs) possibles sans chicane
( i.e.  pas de couleur vide ): ça peut compléter ton exo et je pense que c'est un bon entraînement.

https://www.bibmath.net/forums/viewtopic.php?id=14556

A.

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Re : Exercice de dénombrement

Bonsoir,

Avec plaisir, je vais étudier ça, merci beaucoup ^^

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Exercice de dénombrement

Bonjour,

Sur la même page bibmath que ton exercice, une variante de la question des grilles de Fleissner ( plus facile) à 9 trous parmi 36 consiste à se demander combien il y en a , de manière que jamais les 9 trous ne se superposent à la fois, selon l'une des 3 rotations indiquées.

▼une réponse simple

Alors que la question originale de l'exercice demande le dénombrement des grilles telles que aucun des trous ne se correspondent versus les 3 rotations,
cette variante demande le dénombrement des grilles telles que par chaque rotation, au moins 1 trou ne se superpose pas.
La réponse est simplement $\binom{36}{9}$.
En effet si une rotation faisait correspondre 2 à 2 les trous répondant à la question, comme il y en a 9 il faudrait qu' au moins 1 trou (car un nombre impair) reste inchangé au cours de la rotation, ce qui est impossible.
Toutes les grilles conviennent donc, par chacune des 3 rotations, au moins un trou vient sur un non-trou.

A.

Dernière modification par bridgslam (12-11-2022 14:31:02)

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Re : Exercice de dénombrement

Bonjour Bridgslam,

Oui, de toute façon je comptais faire tous les exos histoire de m'améliorer. Je vais me pencher sur cet exercice en premier, je lirai votre résultat après pour ne pas me spoil :D
Merci beaucoup de vos conseils ^.^

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Exercice de dénombrement

Bonsoir,

Oui apprendre à compter est toujours très amusant, et dans mon cas quasi jubilatoire (!).
Une autre réponse pour la question 1 originale des grilles de Fleissner:

▼une autre solution directe

je viens de trouver une autre possibilité.
Acceptons de coder un trou par 0, son homologue d'un quart de tour par 1, son homologue d'un demi-tour par 2, et enfin le dernier par 3.
Une grille de Fleissner est complètement caractérisée par la donnée de ces chiffres dans un quart de grille donnée (disons la N-E pour fixer les idées).
Chacune des 9 cases de ce quart de grille doit avoir un chiffre parmi { 0, 1, 2 ,3}, toutes possibilités acceptées.
Il s'agit donc de dénombrer le nombre d'applications d'un ensemble à 9 éléments ( les cases de ce quart de grille) dans un ensemble à 4 éléments.
On a directement le résultat $4^9$

Bonne fin de soirée
A.

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Exercice de dénombrement

Bonjour,

Je suis loin d'être compétent en cryptographie et ne connais pas non plus la petite histoire de ces grilles ni comment elles ont été utilisées dans le cadre de la guerre.

Je peux néanmoins imaginer le codage secret suivant:

Données publiques :

- le système des grilles de  Fleissner
- une grille carrée préremplie de n² chiffres ( n étant pair )
- une rotation d'un quart, ou de deux quarts , ou de trois quarts dans le sens horaire

Donnée privée:

- 1 grille de Fleissner parmi les $4^{n²/4}$

J'imagine que la quantité de grilles possibles ( à croissance plus qu'exponentielle avec n) donnera du fil à retordre à l'espionnage.
n=6 correspondant à l'exercice fournit tout de même 262144 possibilités de grilles.
Deux crans de plus pour n fournit un nombre de grille de l'ordre de $10^{15}$.

La difficulté peut être renforcée en utilisant par exemple une autre grille de Fleissner annexe pour déterminer les trous de la grille.
Ou encore si $n²/4$ est un carré de côté pair, utiliser les valeurs trouvées pour rejouer dessus une grille de Fleissner... ( il faut cette fois que n soit multiple de 4...
une valeur telle que n=8 sera déjà pas mal )
Etc.

A.

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Re : Exercice de dénombrement

Merci beaucoup à vous Bridgslam,
J'en suis hélas pas à un assez haut niveau de compréhension du dénombrement, mais vos remarques me seront
précieuses pour m'améliorer

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Exercice de dénombrement

Bonsoir,

De rien.
Quelques fois la situation est difficile à se représenter, il peut alors être utile de simplifier à l'extrême pour mieux visualiser et généraliser ensuite.
Par exemple ici prendre une grille de Fleissner de côté 2.
les grilles possibles sont:

  x o      o x     x x       x x
  x x      x x     o x       x o          où o représente le trou ( ici unique)

La première est représentée par 0 dans son quart N-E, la seconde 3, la troisième par 2, la quatrième par 1, selon le codage adopté dans le sens trigonométrique.
Le fait que le quartier N-E n'ait plus 1 mais 4 cases, puis 9 (cas de l'exo du site) etc,  ne changera pas grand-chose à la compréhension.
Il y aura juste plus de possibilités.

A.

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Re : Exercice de dénombrement

Bonsoir Bridgslam,

Effectivement, avant de me lancer sur cet exercice j'ai appris à utiliser le crible de Poincarré appliqué au calcul des dérangements car je ne connaissais pas assez d'outils pour les dénombrements.
Maintenant je me lance sur cet exercice. Merci pour votre exemple c'est effectivement bien plus facile de visualiser ainsi.

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Re : Exercice de dénombrement

Bonjour Brigslam,

Après avoir résolu l'exercice, je trouve la même chose que votre seconde réponse. Pour ce qui est de la première réponse
je trouve que [tex]\binom{36}{9}[/tex] englobe des cases qui sont identiques par rotation et donc qui ne répondent pas au critère d'être unique par rotation.

Je trouve la même chose que votre deuxième réponse à savoir que résoudre ce problème revient à former un carré qui représente un quart. On a forcément besoin de former ce carré si l'on veut avoir une chance de "toucher toutes les cases" suite à 3 rotations successives. Pour chaque case d'un des quarts, on a une case identique dans chaque autre quart par rotation. Donc on peut répartir chacune des cases du carré que l'on souhaite former entre les 4 quarts. Ce qui nous offre 4 possibilités pour placer chaque case.
Soit [tex]4^{\frac{n^2}{4}}[/tex] possibilités pour une grille de Fleissner de taille n avec n pair.

J'ai trouvé cet exercice vraiment intéressant, j'ai pris du plaisir à le résoudre contrairement aux autres qui étaient très frustrants à résoudre

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Exercice de dénombrement

Bonjour,

Oui, mon premier post se rapportait à une variante de la question posée dans l'exercice, et la réponse est logiquement différente.

Sinon on s'aperçoit qu' un codage spécifique d'un problème permet parfois de le résoudre plus naturellement qu'avec un dénombrement direct.
Ça me rappelle la question des combinaisons avec répétitions, dans la même veine...

Content que ça vous ait plu.
Bon a-m

A.

Dernière modification par bridgslam (16-11-2022 13:24:33)

shurkan

Membre

Inscription : 11-11-2022

Messages : 10

Re : Exercice de dénombrement

Bonjour Bridgslam,

Ah oui effectivement.
Oui c'est vrai, et c'est bien plus plaisant à résoudre de cette façon.
Merci, bon après-midi à vous aussi ^.^

Dernière modification par shurkan (16-11-2022 13:28:09)