Le lemme des bergers

Exercice de TD · niveau 2 · mathématiques MPSI, chapitre 18 — Dénombrement · B. Listes, arrangements, permutations

Énoncé

a) Soient $E$ et $F$ deux ensembles finis et $φ : E \to F$ une application surjective telle que chaque $y \in F$ ait exactement $k$ antécédents. Montrer que $∣ E ∣ = k ∣ F ∣$ .

b) En déduire le nombre de dispositions de $n$ convives distincts autour d'une table ronde, deux dispositions étant identifiées lorsqu'elles se déduisent l'une de l'autre par une rotation. Retrouver le résultat en fixant un convive.

c) De combien de façons peut-on distribuer les $32$ cartes d'un jeu en quatre mains de $8$ cartes, les quatre joueurs étant distincts ?

d) Que devient le résultat si les quatre paquets sont anonymes ? Justifier soigneusement la division.

Corrigé

Ce qu'on a le droit d'utiliser. Le principe d'addition sur une partition, les permutations ( $n!$ ), les combinaisons. La stratégie : quand chaque objet est compté exactement $k$ fois, on divise par $k$ — et l'on vérifie ce « exactement » à chaque fois, parce que c'est lui qui rend la division licite.

a) Le lemme. Les ensembles d'antécédents $φ^{- 1} ({y})$ , pour $y \in F$ , sont deux à deux disjoints — un élément de $E$ n'a qu'une image — et recouvrent $E$ — tout élément a une image. Ils forment donc une partition de $E$ en $∣ F ∣$ classes, chacune de cardinal $k$ par hypothèse. Par le principe d'addition, $∣ E ∣ = y \in F \sum φ^{- 1} ({y}) = y \in F \sum k = k ∣ F ∣.$ C'est le lemme des bergers : pour compter les moutons, on compte les pattes et l'on divise par quatre.

b) La table ronde. Soit $E$ l'ensemble des dispositions numérotées : les places de la table sont numérotées de $1$ à $n$ , et une disposition est une bijection des convives sur les places ; $∣ E ∣ = n!$ . Soit $F$ l'ensemble des dispositions à rotation près, et $φ : E \to F$ l'application qui oublie la numérotation. Elle est surjective, et chaque disposition circulaire a pour antécédents ses $n$ rotations. Ces $n$ rotations sont deux à deux distinctes parce que les convives sont discernables : une rotation non triviale déplace le convive $C_{1}$ sur une autre place, donc change la disposition numérotée. Le lemme donne $n! = n ∣ F ∣$ , soit $∣ F ∣ = (n - 1)! .$ En fixant un convive. Asseyons $C_{1}$ où l'on veut : à rotation près, toute disposition en admet une et une seule où $C_{1}$ occupe cette place. Une fois $C_{1}$ posé, les places sont repérées (« à sa gauche », « en face », …) et les $n - 1$ autres convives se répartissent librement sur les $n - 1$ places restantes : $(n - 1)!$ . Les deux voies donnent le même nombre — la seconde est la première où l'on a choisi un représentant par classe.

c) Quatre joueurs distincts. On constitue la main du joueur $J_{1}$ : $(8 32)$ choix ; puis celle de $J_{2}$ parmi les $24$ cartes restantes : $(8 24)$ ; puis $J_{3}$ : $(8 16)$ ; les $8$ dernières vont à $J_{4}$ : une façon. Le principe de multiplication donne $N = (8 32) (8 24) (8 16) (8 8) = \frac{32 !}{8 ! 24 !} \cdot \frac{24 !}{8 ! 16 !} \cdot \frac{16 !}{8 ! 8 !} \cdot 1 = \frac{32 !}{( 8 ! ) ^{4}},$ les factorielles intermédiaires $24!$ et $16!$ se simplifiant en chaîne. Numériquement, $N = 99561092450391000$ , environ $1 0^{17}$ .

Une seconde lecture. Distribuer, c'est écrire sur chaque carte le nom de son propriétaire : un mot de $32$ lettres sur l'alphabet ${J_{1}, J_{2}, J_{3}, J_{4}}$ où chaque lettre apparaît $8$ fois. On choisit les $8$ places de $J_{1}$ , puis les $8$ places de $J_{2}$ parmi les $24$ restantes, et ainsi de suite : le même produit.

d) Quatre paquets anonymes. Soit $E$ l'ensemble des distributions à joueurs distincts, $∣ E ∣ = N$ , et $F$ l'ensemble des partitions du jeu en quatre paquets de $8$ cartes, sans étiquette. L'application $φ : E \to F$ qui oublie les noms est surjective, et les antécédents d'une partition donnée sont les façons d'attribuer les quatre noms à ses quatre paquets : il y en a $4! = 24$ , et elles sont deux à deux distinctes parce que les quatre paquets sont deux à deux distincts — disjoints et non vides, deux paquets différents ne sont jamais le même ensemble de cartes, donc deux attributions différentes des noms donnent deux distributions différentes. Le lemme des bergers s'applique : $∣ F ∣ = \frac{N}{4 !} = \frac{32 !}{( 8 ! ) ^{4} 4 !} = 4148378852099625,$ environ $4 \times 1 0^{15}$ .

Le point délicat. On n'a le droit de diviser que parce que toutes les fibres ont le même cardinal, ici $24$ . Ce n'est pas toujours le cas : pour les colliers, où l'on identifie aussi une disposition à son image miroir, certaines dispositions sont leur propre miroir, les classes n'ont pas toutes le même cardinal, la division brutale par $2 n$ est fausse, et il faut un outil plus fin. La vérification « chaque objet est compté exactement $k$ fois » fait partie de la démonstration.

Contrôle sur un petit cas. Quatre cartes $a, b, c, d$ en deux mains de deux, joueurs distincts : $\frac{4 !}{( 2 ! ) ^{2}} = 6$ , ce que confirme l'énumération des mains de $J_{1}$ : $ab, a c, a d, b c, b d, c d$ . Paquets anonymes : $6/2! = 3$ , à savoir ${ab ∣ c d}$ , ${a c ∣ b d}$ , ${a d ∣ b c}$ .

Ce que l'exercice installe. Quotienter par une symétrie : on compte l'objet rigidifié, puis on divise par le nombre de symétries, après avoir vérifié qu'elles agissent sans point fixe. La question à se poser en premier est toujours : les paquets portent-ils un nom ? C'est cette mécanique qui deviendra, en seconde année, le théorème de Lagrange et le comptage des orbites.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.