Et si le Père Noël se trompait ?

La vie de Père Noël n’est pas une sinécure. En plus d’avoir à apporter des cadeaux à des millions d’enfants avec des contraintes temporelles et physiques quasiment impossibles à remplir, il doit faire face à une angoisse terrible chaque année: apporter le bon cadeau au bon enfant. Signalons que le fait qu’il boive une bouteille de vodka avant chaque tournée pour se donner du courage (et se réchauffer) n’arrange en rien ce problème.

Et si le Père Noël se trompait complètement cette année ? Et s’il rendait tous les enfants de la Terre malheureux (sans exception) ? Plus précisément, la question à laquelle nous allons répondre dans cet article est la suivante: quelle est la probabilité qu’aucun enfant ne reçoive, le 25 Décembre au matin, le cadeau qui lui était destiné ? (ce qui serait tout de même une sacrée coïncidence…)

Mise en place du problème

Dans la suite de cet article, nous noterons par $n$ le nombre d’enfants que le Père Noël va voir cette année. On suppose qu’on a numéroté tous ces enfants de $1$ à $n$ une bonne fois pour toute. De même, on numérote de $1$ à $n$ tous les cadeaux (ou lots de cadeaux car certains enfants en reçoivent plusieurs !) de telle sorte que le cadeau numéro $k$ appartienne à l’enfant numéro $k$ .

Nous représenterons à l’aide de la notation $\sigma$ la tournée du Père Noël le 24 Décembre au soir de la façon suivante:

$\sigma(k)$ est le numéro du cadeau que le Papa Noël a déposé chez l’enfant numéro $k$

Ainsi, si le Père Noël apporte le bon cadeau à l’enfant $k$ alors $\sigma(k)=k$ . Et le Père Noël se trompera complètement cette année si pour tout nombre entier $k$ compris entre $1$ et $n$ , $\sigma(k) \neq k$ .

Afin de calculer la probabilité qui nous intéresse dans cet article, à savoir la probabilité qu’aucun enfant ne reçoive le cadeau qui lui est destiné, on fait l’hypothèse que toutes les tournées ont la même probabilité d’apparaître (même si la présence d’alcool dans le sang de ce monsieur tout rouge peut quand même nous faire sérieusement douter de la validité de cette hypothèse). Ainsi, il nous faut donc trouver le nombre $d_n$ de tournées $\sigma$ pour lesquelles $\sigma(k) \neq k$ pour tout $k$ .

Sachant qu’il y a $n!$ tournées possibles au total (chaque tournée est, comme vous l’avez peut-être déviné, une permutation de l’ensemble $\{1, \cdots, n \}$ ), la probabilité $p$ cherchée vaudra $p=\dfrac{d_n}{n!}$

Mais avant de nous lancer tout de suite dans le cas général de $n$ enfants, voyons ce qu’il se passe dans le cas d’un petit nombre d’enfants, pour mieux comprendre.

Cas d’un enfant (n=1)

Cette année, tous les enfants de la Terre ont été particulièrement peu sages. Seul un enfant a su se tenir correctement. La tournée du Père Noël n’en sera que plus facile me direz-vous.

Puisqu’il n’y a qu’un enfant (et donc qu’un seul cadeau à livrer), il n’y a aucune chance pour que ce petit enfant reçoive un cadeau qui n’est pas le sien. La probabilité cherchée est donc $p=0$ .

Cas de deux enfants

Dans le cas où il n’y a que deux enfants à livrer (et donc qu’il n’y a que deux cadeaux à apporter), la seule façon de se tromper est d’apporter le cadeau n°2 à l’enfant 1 et le cadeau n°1 à l’enfant 2. Il n’y a donc qu’une seule façon de se tromper totalement, et la probabilité cherchée est donc $p=\dfrac{1}{2!}=\dfrac{1}{2}$ .

Cas de trois enfants (non, je vous rassure, on ne va pas tous les faire comme ça…)

Introduisons une notation. Pour représenter la tournée dans laquelle l’enfant 1 reçoit le cadeau de l’enfant 2, l’enfant 2 reçoit le cadeau de l’enfant 3 et l’enfant 3 reçoit le cadeau de l’enfant 1, nous écrirons:

$\left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{array} \right)$

Dans la ligne du haut, sont écrits les numéros des enfants. Le numéro correspondant dans la ligne juste en dessous est le numéro du cadeau reçu par cet enfant.

Vous pouvez vérifier rapidement que les seules tournées pour lesquelles aucun enfant ne reçoit son cadeau sont

$\left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{array} \right)$ et $\left( \begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \\ \end{array} \right)$

ce qui donne deux possibilités. La probabilité cherchée est donc $p=\dfrac{2}{3!}=\dfrac{1}{3}$ .

Le cas général

On se place à présent dans le cas où le Père Noël va rendre visite à $n$ enfants (avec $n\geq 3$ ). Nous allons trouver le nombre de tournées $d_n$ où aucun enfant ne reçoit son cadeau en faisant la disjonction des cas suivante:

Soit l’enfant 1 reçoit le cadeau de l’enfant 2;
Soit l’enfant 1 reçoit le cadeau de l’enfant 3;
etc.
Soit l’enfant 1 reçoit le cadeau de l’enfant $n$ .

Cela donne $n-1$ cas à étudier (l’étude de chaque cas est similaire).

Cas où l’enfant 1 reçoit le cadeau de l’enfant 2.
Nous allons distinguer deux sous-cas disjoints:

a) Soit alors l’enfant 2 reçoit le cadeau de l’enfant 1. Ainsi, les enfants 1 et 2 ont vus leurs cadeaux échangés par le Père Noël. Autrement dit, la tournée $\sigma$ est de la forme:
$\left( \begin{array}{ccccc} 1 & 2 & 3 & ... & n \\ 2 & 1 & \sigma(3) & ... & \sigma(n) \end{array} \right)$
On remarque donc que les cadeaux 3, 4, …, $n$ vont être distribués parmi les enfants 3, 4, …, $n$ . Il suffit donc de compter combien de tournées avec les $n-2$ enfants 3, 4, …, $n$ incluant les cadeaux 3, 4, …, $n$ sont telles qu’aucun enfant ne reçoive le bon cadeau. Par définition, ce nombre est $d_{n-2}$ .

b) Soit l’enfant 2 ne reçoit pas le cadeau de l’enfant 1 ( $\sigma(2)\neq 1$ ). Ainsi, les tournées cherchées sont de la forme:
$\left( \begin{array}{ccccc} 1 & 2 & 3 & ... & n \\ 2 & \sigma(2) & \sigma(3) & ... & \sigma(n) \end{array} \right)$
Si on renomme les enfants 2, 3, 4, …, $n$ en 2′, 3′, 4′, …, $n'$ , et si on renomme les cadeaux 1, 3, 4, …, $n$ en 2′, 3′, 4′, …, $n'$ , alors le nombre de tournées cherché est le même que le nombre de tournées pour lesquelles on distribue aux enfants 2′, 3′, …, $n'$ les cadeaux 2′, 3′, …, $n'$ sans qu’aucun enfant $k'$ n’obtienne le cadeau $k'$ qui lui correspond. Par définition, ce nombre vaut $d_{n-1}$ .

Par suite (a) + b)), le nombre de tournées pour lesquelles l’enfant 1 reçoit le cadeau de l’enfant 2 et pour lesquelles aucun enfant ne reçoit son cadeau est $d_{n-1}+d_{n-2}$ .
De la même manière, on montre que le nombre de tournées dans lesquelles l’enfant 1 reçoit le cadeau de l’enfant $k$ et où aucun enfant ne reçoit le bon cadeau est $d_{n-1}+d_{n-2}$ .
Au final, le nombre de tournées pour lesquelles aucun enfant ne reçoit son cadeau attitré est $d_n= (d_{n-1}+d_{n-2}) + (d_{n-1}+d_{n-2}) + \cdots + (d_{n-1}+d_{n-2})$ . D’où:

$\boxed{d_n = (n-1) (d_{n-1}+d_{n-2})}$

Calcul explicite de la suite $\left( \dfrac{d_n}{n!} \right)$

Nous venons de trouver une relation de récurrence vérifiée par le suite $(d_n)$ . Nous allons nous en servir pour exprimer explicitement la suite $\left( \dfrac{d_n}{n!} \right)$ qui n’est rien d’autre que la probabilité qu’on recherche. Commençons par remarquer que la relation précédente donne:

$d_n - n d_{n-1} = (-1) . [ d_{n-1} - (n-1) d_{n-2}]$

Si $(v_n)$ est la suite définie par $v_n=d_n - n d_{n-1}$ , on a donc

$v_n=(-1) v_{n-1} = (-1)^2 v_{n-2} = ... = (-1)^{n-2} v_2$

Comme $v_2= d_2 - 2 \times d_1 = 1 - 2 \times 0 = 1$ ( $d_2$ et $d_1$ ont été calculés dans les paragraphes ci-dessus), on en déduit que

$d_n-n d_{n-1}=(-1)^{n-2}$

c’est-à-dire

$d_n=n d_{n-1}+(-1)^{n}$

En divisant la relation ci-dessus par $n!$ , on obtient

$\dfrac{d_n}{n!} = \dfrac{d_{n-1}}{(n-1)!} + \dfrac{(-1)^n}{n!}$

d’où

$\dfrac{d_n}{n!} - \dfrac{d_{n-1}}{(n-1)!} = \dfrac{(-1)^n}{n!}$

En sommant les deux membres de 3 à n, on reconnaît une somme télescopique, ce qui donne au final:

$\dfrac{d_n}{n!} - \dfrac{d_{3-1}}{(3-1)!} = \displaystyle{\sum_{k=3}^{n}\dfrac{(-1)^k}{k!} }$

Donc,

$\dfrac{d_n}{n!} = \dfrac{d_{2}}{2!} + \displaystyle{\sum_{k=3}^{n}\dfrac{(-1)^k}{k!} }$

Comme $d_2=1$ , on a donc

$\boxed{\dfrac{d_n}{n!} = \displaystyle{ \sum_{k=2}^{n}\dfrac{(-1)^k}{k!}} }$

Ouf !

Bon alors, combien de chances a le Père Noël de se planter lamentablement ?

Revenons au problème qui nous occupe. Comme nous venons de le voir, la probabilité qu’aucun enfant ne reçoive le bon cadeau est

$p=\dfrac{d_n}{n!}= \displaystyle{ \sum_{k=2}^{n}\dfrac{(-1)^k}{k!} }$

Voici un tableau dans lequel on a calculé une valeur approchée de cette probabilité pour quelques valeurs de $n$ :

$\begin{array}{c|c|c|c|c|c|c|c|c|c} n & 1 & 2 & 3 & 4 & 5 & 10 & 30 & 60 & 100 \\ \hline p & 0 & 0.5 & 0.333... & 0.375 & 0.36666.... & 0.36787946... & 0.36787944... & 0.36787944... & 0.36787944... \\ \end{array}$

(J’ai calculé ces valeurs à l’aide d’un programme écrit avec Algobox. Mais au-delà de $n=100$ , le programme plantait, la factorielle devenait trop grande…)

Question: peut-on préciser cette probabilité dans le cas où $n$ est bien plus grand ? Car il n’y a pas que 100 enfants sur cette planète….

Vers quoi tend cette probabilité ?

Tout d’abord, remarquons que $\displaystyle{ \sum_{k=2}^{n}\dfrac{(-1)^k}{k!} }= \displaystyle{ \sum_{k=0}^{n}\dfrac{(-1)^k}{k!} }$ . Ensuite, étalons un peu notre science en disant que $\displaystyle{ \sum_{k=0}^{+\infty}\dfrac{(-1)^k}{k!} }$ n’est rien d’autre que le nombre $e^{-1}$ . Notre probabilité tend donc, quand $n$ est grand, vers

$\dfrac{1}{e}=0.3678794411714423215955237701614608674458111310317678...$

Avec encore plus de connaissances sur les séries alternées, on peut affirmer que, s’il y a $n$ enfants, la différence $|p-\dfrac{1}{e}|$ est inférieure à $\dfrac{1}{(n+1)!}$ . Ainsi, la probabilité que le Père Noël se trompe entièrement dans ses cadeaux sera égale à 0.3678794411 (à $10^{-10}$ près) dès que $(n+1)!$ est plus grand que $10^{10}$ c’est-à-dire dès que $n$ est plus grand que 13.

A fortiori, dans le cas où $n$ est de l’ordre de plusieurs millions, $n$ est plus grand que 13 (oui !) et la probabilité qu’aucun enfant ne reçoive le cadeau qui est le sien est de 0.3678794411 à $10^{-10}$ près.

En résumé…

La probabilité que le Père Noël se trompe entièrement est proche de 36% lorsque le nombre d’enfants à visiter est de l’ordre de plusieurs millions.

Autrement dit, et c’est un fait étonnant (voire contre-intuitif), chaque année, le Père Noël a plus d’une chance sur trois de ne distribuer le bon cadeau à aucun enfant ! C’est donc une belle performance que presque tous les enfants reçoivent leur cadeau attitré sous le sapin chaque 25 Décembre.

Bravo petit Papa Noël ! (et n’oublie surtout pas de m’apporter ma console de jeux cette année…)

(N.B: le nombre $d_n$ de cet article s’appelle le nombre de dérangements ou encore sous-factorielle, et il s’agit du nombre de permutations sans points fixes).

3 commentaires pour Et si le Père Noël se trompait ?

Ping : Stirling 2 – Le retour | Blogdemaths
Ping : Stirling 2 – Le retour | Actumaths
VivideNoël dit :

18 décembre 2014 à 11 h 37 min

Vu la facilité évidente des calculs (ironie) il vaut mieux ne pas croire au Père Noël, ainsi, on n’aura pas à se poser de question. lol !

J’aimeJ’aime

Réponse

Votre commentaire Annuler la réponse.

Entrez votre commentaire...

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

E-mail (adresse strictement confidentielle)

Nom

Site web

Vous commentez à l’aide de votre compte WordPress.com. ( Déconnexion / Changer )

Vous commentez à l’aide de votre compte Facebook. ( Déconnexion / Changer )

Annuler

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.