Autour d'une table ronde : diviser, mais à bon escient

Exercice de TD · niveau 2 · mathématiques (PTSI), chapitre 15 — Dénombrement · B. Listes, arrangements, permutations

Énoncé

a) De combien de façons $n$ convives distincts ( $n \geq 2$ ) peuvent-ils s'asseoir autour d'une table ronde, deux dispositions étant identiques si elles se déduisent l'une de l'autre par une rotation ?

b) Et si $n \geq 3$ perles distinctes sont enfilées sur un collier que l'on peut aussi retourner ?

c) De combien de façons peut-on partager les $32$ cartes d'un jeu en quatre paquets de huit cartes, non attribués ? Justifier la division.

d) On forme des colliers de quatre perles, deux noires et deux blanches, identifiés à rotation près. Que donne « la division par $4$ » ? Dénombrer directement, et expliquer l'échec.

e) (Géométrie des solides) On inscrit les nombres $1, 2, \dots, 6$ sur les six faces d'un cube, un nombre par face ; deux dés sont identiques si l'un se déduit de l'autre par une rotation du cube. Montrer qu'il existe exactement $24$ rotations du cube qui le laissent globalement invariant (choisir la face amenée en dessous, puis le quart de tour), et qu'une rotation autre que l'identité déplace au moins une face. En déduire le nombre de dés différents. Retrouver ce nombre directement, en posant la face $1$ en dessous.

Corrigé

L'outil : le lemme des bergers. Soit $ϕ : E \to F$ une application surjective entre ensembles finis, telle que chaque élément de $F$ ait exactement $k$ antécédents. Alors $∣ E ∣ = k ∣ F ∣$ . En effet, les ensembles d'antécédents des éléments de $F$ sont deux à deux disjoints — un élément de $E$ n'a qu'une image — et recouvrent $E$ : ils forment une partition de $E$ en $∣ F ∣$ classes de $k$ éléments, et le principe d'addition conclut. Pour compter les moutons, on compte les pattes et l'on divise par quatre — à condition que chaque mouton ait quatre pattes. On ne divise que si chaque objet est compté exactement $k$ fois.

a) La table ronde. Numérotons les chaises : il y a $n!$ placements numérotés. L'application qui oublie la numérotation, et ne garde que la disposition à rotation près, est surjective, et chaque disposition a pour antécédents ses $n$ rotations. Ces $n$ rotations sont deux à deux distinctes, parce que les convives sont distincts : une rotation non nulle déplace le convive $C_{1}$ sur une autre chaise. Le lemme donne $n! = n \times (nombre de dispositions)$ : il y a $(n - 1)!$ dispositions. Seconde voie : on assied $C_{1}$ sur une chaise fixée — chaque disposition a exactement un représentant ainsi — et les $n - 1$ autres se répartissent sur les $n - 1$ chaises restantes : $(n - 1)!$ . Contrôle pour $n = 3$ : $2$ dispositions, « $A$ , $B$ , $C$ » et « $A$ , $C$ , $B$ » dans le sens de rotation.

b) Le collier retournable. Chaque collier correspond à exactement deux dispositions à rotation près : une disposition et son image dans un miroir. Elles sont distinctes pour $n \geq 3$ : la perle $1$ a deux voisines distinctes, l'une dans le sens des aiguilles d'une montre, l'autre dans le sens contraire ; une rotation conserve laquelle est « dans le sens des aiguilles », le retournement les échange. Le lemme donne $\frac{( n - 1 )!}{2}$ colliers. Pour $n = 2$ , la division échouerait — elle donnerait $\frac{1}{2}$ — parce que l'unique disposition est sa propre image.

c) Les paquets anonymes. Soit $N = \frac{32 !}{( 8 ! ) ^{4}}$ le nombre de donnes à quatre joueurs distincts (exercice 3). L'application qui efface les noms des joueurs envoie chaque donne sur un partage en quatre paquets ; chaque partage a pour antécédents les $4! = 24$ façons d'attribuer ses quatre paquets aux quatre joueurs, deux à deux distinctes parce que les quatre paquets sont deux à deux distincts — disjoints et non vides. Le lemme donne $\frac{32 !}{( 8 ! ) ^{4} 4 !} = 4148378852099625 partages,$ environ $4 \times 1 0^{15}$ . Contrôle minuscule : $4$ cartes en deux mains de deux donnent $\frac{4 !}{( 2 ! ) ^{2}} = 6$ donnes et $3$ partages.

d) L'échec. Avec les positions numérotées de $1$ à $4$ , un collier est un mot de quatre lettres avec deux $N$ et deux $B$ : $(2 4) = 6$ mots. « La division par $4$ » donne $\frac{6}{4} = 1, 5$ — absurde. Directement : à rotation près, les deux perles noires sont voisines ou opposées, et il y a $2$ colliers. L'explication : la classe du premier contient $4$ mots, $N N B B$ , $N B B N$ , $B B N N$ , $B N N B$ ; celle du second n'en contient que $2$ , $N B N B$ et $B N B N$ , car la rotation d'un demi-tour laisse $N B N B$ inchangé. Les classes n'ont pas toutes le même cardinal : $4 + 2 = 6$ , et le lemme des bergers ne s'applique pas.

e) Les dés. Les rotations du cube. Une rotation qui laisse le cube globalement invariant envoie chaque face sur une face, et deux faces adjacentes sur deux faces adjacentes. Elle est déterminée par l'image de deux faces adjacentes — disons la face du dessous et la face avant : l'image de la face du dessous fixe l'axe vertical du cube tourné, celle de la face avant fixe l'orientation autour de cet axe — un fait de géométrie des solides, que la manipulation d'un dé rend évident et qu'on admet ici. Pour construire une rotation, on choisit la face qui viendra en dessous, $6$ choix, puis, cette face étant posée, l'un des $4$ quarts de tour autour de l'axe vertical, qui amène en face avant l'une des $4$ faces adjacentes à la nouvelle face du dessous : $6 im es 4 = 24$ choix, qui donnent $24$ rotations deux à deux distinctes, puisqu'elles diffèrent par l'image de la face du dessous ou par celle de la face avant. Il y a exactement $24$ rotations, l'identité comprise. Une rotation qui ne déplace aucune face envoie la face du dessous sur elle-même et la face avant sur elle-même : elle a les mêmes images de ces deux faces que l'identité, donc c'est l'identité.

Le lemme des bergers. Numérotons les faces du cube posé devant nous : un étiquetage est une bijection des six faces vers ${1, \dots, 6}$ , et il y en a $6! = 720$ . L'application qui oublie la position du cube, et ne garde que le dé à rotation près, est surjective ; chaque dé a pour antécédents les $24$ étiquetages obtenus en faisant tourner le cube par les $24$ rotations. Ces $24$ étiquetages sont deux à deux distincts : si deux rotations $r$ et $r^{'}$ donnaient le même étiquetage, la rotation « $r$ suivie de l'inverse de $r^{'}$ » laisserait chaque nombre sur sa face ; les six nombres étant distincts, elle ne déplacerait aucune face, et ce serait l'identité, d'où $r = r^{'}$ . Le lemme donne $720 = 24 \times (nombre de d e ˊ s)$ : il y a $30$ dés différents.

Directement. Tout dé peut être tourné de façon à poser la face $1$ en dessous. La face opposée, en dessus, porte l'un des $5$ nombres restants, et elle ne change plus par les rotations qui gardent la face $1$ en dessous, qui sont les $4$ quarts de tour autour de l'axe vertical. Les quatre faces latérales portent les $4$ nombres restants, en cercle, identifiés à rotation près autour de cet axe : c'est la table ronde du a) avec $4$ convives, $(4 - 1)! = 3! = 6$ dispositions. D'où $5 \times 6 = 30$ dés : les deux comptages s'accordent.

Le point délicat, commun à d) et e). Avant de diviser, il faut se demander si une symétrie fixe certains objets. Pour des convives, des cartes, des faces portant six nombres distincts, jamais : aucune rotation autre que l'identité ne fixe un dé, et la division par $24$ réussit. Pour des perles de même couleur, oui — la rotation d'un demi-tour fixe $N B N B$ — et la division devient fausse. Le dé et le collier bicolore sont les deux faces du même lemme.

Ce que l'exercice installe. Le lemme des bergers : 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 ? En géométrie des solides et en sciences industrielles, les $24$ rotations du cube sont les $24$ orientations possibles d'une pièce cubique qu'on repose dans son logement : décrire une orientation par « quelle face en dessous, puis quel quart de tour », c'est exactement le comptage du e).

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.