Problèmes sur le dénombrement

Le cadenas

Un cadenas s'ouvre avec un code de quatre chiffres, chacun choisi entre \(0\) et \(9\).

1. Combien de codes différents existe-t-il ?

   Un code est un \(4\)-uplet : l'ordre compte, et les répétitions sont permises.

   $$ 10^4 = 10 \ 000 \ \text{codes} $$
2. Combien comportent quatre chiffres tous différents ?

   Le premier chiffre se choisit de \(10\) façons, le deuxième de \(9\), et ainsi de suite :

   $$ 10 \times 9 \times 8 \times 7 = 5 \ 040 \ \text{codes} $$
3. Quelle est la probabilité d'ouvrir le cadenas du premier coup, au hasard ?

   Les \(10 \ 000\) codes sont équiprobables, et un seul convient :

   $$ p = \frac{1}{10 \ 000} = 0.0001 $$

Le comité de classe

Une classe compte \(30\) élèves, dont \(18\) filles et \(12\) garçons. On doit élire un comité de \(4\) élèves, sans distinction de rôle.

1. Combien de comités différents peut-on former ?

   L'ordre ne compte pas - les quatre membres ont le même rôle :

   $$ \binom{30}{4} = 27 \ 405 \ \text{comités} $$
2. Combien comportent un élève donné, disons Léa ?

   Léa étant retenue, il reste à choisir \(3\) élèves parmi les \(29\) autres :

   $$ \binom{29}{3} = 3 \ 654 \ \text{comités} $$
3. Combien comportent au moins une fille ?

   Il est plus court de compter ceux qui n'en comportent aucune - donc quatre garçons - et de les retrancher :

   $$ \binom{12}{4} = 495 $$

   $$ 27 \ 405 - 495 = 26 \ 910 \ \text{comités} $$
4. Vérifier la relation de Pascal sur \(\binom{30}{4}\).

   La relation donne \(\binom{30}{4} = \binom{29}{3} + \binom{29}{4}\), soit :

   $$ 3 \ 654 + 23 \ 751 = 27 \ 405 $$

   C'est exactement la question 2 et son contraire : les comités qui contiennent Léa, et ceux qui ne la contiennent pas.

La main de cartes

On distribue une main de \(5\) cartes dans un jeu de \(32\), qui contient \(4\) rois.

1. Combien de mains différentes peut-on recevoir ?

   Une main est un ensemble : l'ordre de distribution n'y change rien.

   $$ \binom{32}{5} = 201 \ 376 \ \text{mains} $$
2. Combien contiennent exactement deux rois ?

   On choisit \(2\) rois parmi \(4\), puis \(3\) cartes parmi les \(28\) qui n'en sont pas :

   $$ \binom{4}{2} \times \binom{28}{3} = 6 \times 3 \ 276 $$

   $$ 19 \ 656 \ \text{mains} $$
3. Combien contiennent au moins un roi ?

   Par l'événement contraire : les mains sans aucun roi se choisissent parmi les \(28\) autres cartes.

   $$ \binom{28}{5} = 98 \ 280 $$

   $$ 201 \ 376 - 98 \ 280 = 103 \ 096 \ \text{mains} $$

   Compter directement aurait demandé quatre calculs - un, deux, trois ou quatre rois - puis leur somme.

Les chemins du quartier

Un livreur à vélo part du point \(A\) et doit rejoindre le point \(B\). Les rues forment un quadrillage : de \(A\) à \(B\), il faut parcourir \(4\) blocs vers l'est et \(3\) blocs vers le nord. Le livreur ne recule jamais : chacun de ses déplacements est un bloc vers l'est ou un bloc vers le nord.

On repère un carrefour par le couple \((i \ ; \ j)\) : \(i\) blocs à l'est de \(A\), \(j\) blocs au nord. Ainsi \(A = (0 \ ; \ 0)\) et \(B = (4 \ ; \ 3)\).

1. Déterminer le nombre de trajets possibles.

   Un trajet est une suite de \(7\) déplacements, dont exactement \(3\) vers le nord : il est entièrement décrit par le choix des rangs de ces trois déplacements parmi les sept.

   $$ \binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35 $$

   $$ 35 \ \text{trajets} $$
2. Un chantier ferme le carrefour \(Q = (3 \ ; \ 1)\). Déterminer le nombre de trajets qui l'évitent.

   On compte plutôt ceux qui y passent : un tel trajet se coupe en deux morceaux indépendants, de \(A\) à \(Q\) puis de \(Q\) à \(B\).

   $$ A \to Q : \ 3 \ \text{est et} \ 1 \ \text{nord} \hspace{2em} \binom{4}{1} = 4 $$

   $$ Q \to B : \ 1 \ \text{est et} \ 2 \ \text{nord} \hspace{2em} \binom{3}{2} = 3 $$

   Le principe multiplicatif donne \(4 \times 3 = 12\) trajets passant par \(Q\).

   $$ 35 - 12 = 23 \ \text{trajets} $$
3. Un second chantier ferme le carrefour \(R = (1 \ ; \ 2)\). Déterminer le nombre de trajets qui évitent les deux carrefours fermés.

   Par le même découpage, les trajets passant par \(R\) sont au nombre de :

   $$ \binom{3}{2} \times \binom{4}{1} = 3 \times 4 = 12 $$

   Reste à savoir combien passent par les deux. Pour aller de \(R = (1 \ ; \ 2)\) à \(Q = (3 \ ; \ 1)\), il faudrait descendre d'un bloc ; pour aller de \(Q\) à \(R\), il faudrait revenir de deux blocs vers l'ouest. Ni l'un ni l'autre n'est permis.

   $$ \text{aucun trajet ne passe par les deux} $$

   Les deux ensembles de trajets interdits sont donc disjoints, et l'on soustrait leurs effectifs sans correction :

   $$ 35 - 12 - 12 = 11 \ \text{trajets} $$
4. Retrouver ce nombre en portant sur le quadrillage, carrefour par carrefour, le nombre de trajets qui y mènent.

   On arrive à un carrefour soit par l'ouest, soit par le sud : le nombre de trajets qui y mènent est la somme des deux nombres portés par ces deux voisins - c'est la relation de Pascal, lue sur le plan. Un carrefour fermé porte \(0\).

   $$ j = 3 $$	$$ 1 $$	$$ 1 $$	$$ 4 $$	$$ 7 $$	$$ 11 $$
   $$ j = 2 $$	$$ 1 $$	$$ 0 $$	$$ 3 $$	$$ 3 $$	$$ 4 $$
   $$ j = 1 $$	$$ 1 $$	$$ 2 $$	$$ 3 $$	$$ 0 $$	$$ 1 $$
   $$ j = 0 $$	$$ 1 $$	$$ 1 $$	$$ 1 $$	$$ 1 $$	$$ 1 $$
   	$$ i = 0 $$	$$ i = 1 $$	$$ i = 2 $$	$$ i = 3 $$	$$ i = 4 $$

   $$ 11 \ \text{trajets, comme par le dénombrement} $$

   Les deux méthodes ne disent pas la même chose. La première suppose qu'on sache écarter le double comptage ; la seconde n'en a pas besoin, et tiendrait encore avec dix chantiers.

Deux formules de tournoi

Huit équipes s'inscrivent à un tournoi. L'organisateur hésite entre deux formules, et deux équipes sont données favorites.

• Formule à élimination directe : les huit équipes sont placées au hasard dans les huit positions d'un tableau à trois tours ; le perdant de chaque match est éliminé.

• Formule à poules : les huit équipes sont réparties au hasard en deux poules de quatre ; dans chaque poule, toutes les équipes se rencontrent ; les deux premières s'affrontent en finale.

1. Déterminer le nombre de matchs de chaque formule.

   À élimination directe, chaque match élimine exactement une équipe, et il faut en éliminer sept pour qu'il n'en reste qu'une.

   $$ 7 \ \text{matchs} $$

   Dans une poule de quatre, un match est une paire d'équipes, soit \(\binom{4}{2} = 6\) matchs, et il y a deux poules, plus la finale.

   $$ 2 \times 6 + 1 = 13 \ \text{matchs} $$
2. Dans la formule à élimination directe, déterminer le nombre d'affiches possibles au premier tour, puis la proportion de celles qui opposent d'emblée les deux favoris.

   Une affiche de premier tour est un partage des huit équipes en quatre paires. On peut aligner les huit équipes (\(8!\) façons), puis lire les paires deux par deux : l'ordre dans chaque paire ne compte pas (\(2^4\)), ni l'ordre des quatre paires (\(4!\)).

   $$ \frac{8!}{2^4 \times 4!} = \frac{40 \ 320}{16 \times 24} = 105 $$

   Si les deux favoris forment une paire, il reste à apparier six équipes :

   $$ \frac{6!}{2^3 \times 3!} = \frac{720}{8 \times 6} = 15 $$

   $$ \frac{15}{105} = \frac{1}{7} $$
3. Déterminer, pour chaque formule, la proportion des tirages qui permettent aux deux favoris de ne se rencontrer qu'en finale.

   À poules. Un tirage est un partage en deux poules de quatre. En choisissant les quatre équipes de la première poule, on compte chaque partage deux fois :

   $$ \frac{1}{2} \binom{8}{4} = \frac{70}{2} = 35 \ \text{partages} $$

   Les favoris sont séparés lorsque la poule du premier favori se complète par trois des six équipes restantes :

   $$ \binom{6}{3} = 20 \hspace{2em} \text{soit} \hspace{2em} \frac{20}{35} = \frac{4}{7} $$

   À élimination directe. Les favoris ne peuvent se rencontrer en finale que s'ils sont dans deux moitiés différentes du tableau. Une fois la position du premier fixée, le second occupe l'une des sept positions restantes, dont quatre sont dans l'autre moitié.

   $$ \frac{4}{7} \ \text{dans les deux formules} $$
4. Trancher : le tournoi doit tenir en une journée de huit heures, un match durant quarante minutes, et deux terrains sont disponibles.

   Deux terrains permettent deux matchs de front, soit au mieux \(\frac{8 \times 60}{40} \times 2 = 24\) matchs. Les deux formules tiennent donc dans la journée, et le critère d'équité les départage encore moins : il vaut \(\frac{4}{7}\) pour les deux.

   Ce qui les sépare est ailleurs :

   • À élimination directe, une équipe peut rentrer chez elle après \(40\) minutes de jeu. Sept matchs pour huit équipes, cela fait moins de deux matchs par équipe en moyenne.

   • À poules, chaque équipe joue trois matchs assurés, et treize matchs occupent les deux terrains pendant \(4 \ \text{h} \ 20\).

   $$ \text{la formule à poules : six matchs de plus, et personne ne repart après un seul} $$

   Le calcul n'a pas tranché tout seul - il a seulement montré que l'argument de l'équité du tirage ne tranchait rien, et que la journée avait de la place. Restait le seul critère que les deux formules distinguent vraiment : le temps de jeu garanti.