6.1 Le problème des chapeaux

Le problème des chapeaux (Hatcheck problem) est un problème classique de la combinatoire. Il s’énonce comme suit:

Si $\displaystyle n$ personnes déposent leur chapeau à la consigne au début d’une soirée, et qu’à la fin la dame travaillant à la consigne ayant un peu trop fêté leur remet leur chapeau de manière aléatoire, qu’elle est la probabilité qu’aucune des $\displaystyle n$ personnes ne reçoivent son propre chapeau ?

Le problème est une application du principe d’inclusion-exclusion. On commence par remarquer qu’il y a $\displaystyle n!$ façons de remettre les chapeaux aux hommes. De plus, si $\displaystyle i$ est un entier entre $\displaystyle 0$ et $\displaystyle n$ , alors il y a:

\displaystyle\binom{n}{i}(n-i)!=\frac{n!}{i!(n-i)!}(n-i)!=\frac{n!}{i!}

façon de remettre les chapeaux de sorte qu’au moins $\displaystyle i$ personnes reçoivent leur propre chapeau. Par le principe d’inclusion-exclusion, on a donc:

\displaystyle\sum_{i=0}^{n}\frac{(-1)^{i}n!}{i!}

façon de distribuer les chapeaux de sorte qu’aucun des hommes ne reçoive leur propre chapeau. Maintenant, pour obtenir une probabilité, il suffit de diviser par $\displaystyle n!$ , ce qui nous donne:

\displaystyle\textrm{Probabilit\'{e}}=\sum_{i=0}^{n}\frac{(-1)^{i}}{i!}

Voici la solution du problème des chapeaux pour quelques valeurs de $\displaystyle n$ .

Solution du problème des chapeaux

$\displaystyle n$	1	2	3	4	5	6	7	8	9
Probabilité	0,00000	0,50000	0,33333	0,37500	0,36667	0,36806	0,36786	0,36788	0,36788

En regardant attentivement les valeurs que nous avons obtenues, il est facile de remarquer que la probabilité converge très rapidement vers une valeur proche de $\displaystyle 36,8\%$ . En fait, il est facile de trouver quelle est la valeur exacte vers laquelle la probabilité converge. Nous avons déjà rencontré la série suivante lorsque nous avons étudié les fonctions génératrices exponentielles:

\displaystyle e^{x}=\sum_{i=0}^{\infty}\frac{x^{n}}{n!}

En comparant cette série avec l’expression pour la probabilité que nous venons d’obtenir, on peut donc conclure que la probabilité qu’aucun des hommes ne reçoive son propre chapeau lorsque le nombre de personnes est suffisamment grand est donc:

\displaystyle\textrm{Probabilit\'{e}}=\sum_{i=0}^{n}\frac{(-1)^{i}}{i!}% \longrightarrow\sum_{i=0}^{\infty}\frac{(-1)^{i}}{n!}=e^{-1}=\frac{1}{e}% \approx 0.36788

Ce qui est exactement la valeur que nous avions observée dans notre tableau. La solution du problème des chapeaux est donc approximativement $\displaystyle 36,8\%$

Les dérangements

Le problème des chapeaux est en fait un cas particulier de ce l’on appelle un dérangement. De combien de façon peut-on ré-ordonner un ensemble de $\displaystyle n$ éléments distincts de sorte qu’aucun élément ne se retrouve à sa position originale. On dénote la solution du problème par $\displaystyle D_{n}$ ou $\displaystyle n\textrm{\textexclamdown}$ . Basé sur notre solution du problème des chapeaux, le nombre de dérangement est donné par:

\displaystyle D_{n}=n\textrm{\textexclamdown}=\sum_{i=0}^{n}\frac{(-1)^{i}n!}{% i!}

Basé sur cette formule, il est maintenant facile de déterminer les valeurs de $\displaystyle D_{n}$ pour de petit $\displaystyle n$ . On a donc le tableau ci-dessous.

Nombres de dérangement

$\displaystyle n$	0	1	2	3	4	5	6	7	8	9
$\displaystyle D_{n}$	0	1	2	9	44	265	1854	14833	133496	1334961