Introduction

La question est la suivante :

Pour préciser la question, on ne tient compte que du jour et du mois de naissance, pas de l'année ni des années bissextiles, on ne considère donc que les 365 jours, il ne s'agit pas de compliquer inu­ti­le­ment l'énoncé. D'autre part, pour éviter toute ambiguïté, on ne cherche pas à trouver exactement deux étudiants nés le même jour, mais s'il existe dans cette classe au moins deux étudiants nés le même jour.

Les sondages réalisés auprès des étudiants pour estimer le nombre en question, aboutissent im­man­qua­blement à une majoration très nette de la valeur réelle. En effet, il y a \(365\) jours dans l'année et il est tentant de penser qu'il faut beaucoup d'étudiants pour espérer en trouver deux nés le même jour. Le nombre proposé le plus fréquemment est \(182\). L'origine de cette réponse est sans doute liée au seuil de probabilité recherché \(1/2\) et le nombre de jours dans une année, mais aucune justification sensée de cette estimation n'a jamais été proposée.

Nous ne ferons pas durer le suspens, le seuil est de \(23\) étudiants et ce résultat peut paraître dé­con­cer­tant (d'où le qualificatif de paradoxe au sens de la langue naturelle). Par conséquent l'expérience est systématiquement menée grandeur nature avec les étudiants qui suivent ce cours. La réalité est bien sûr conforme au résultat. L'objectif de ce chapitre est d'introduire les concepts mathématiques (pour la plupart élémentaires) qui vont permettre de le prouver. Nous verrons également que ce paradoxe constitue un avertissement très sérieux lors de la conception de certains protocoles en cryptographie.

Ensembles finis et infinis

L'ensemble des entiers naturels

Comme son nom l'indique, l'ensemble des entiers naturels collecte les nombres qui nous semblent naturels, tout au moins depuis que les hommes se sont interrogés sur le dénombrement et l'ordre. Par extrapolation, on a bien conscience qu'énumérer les nombres pourrait durer éternellement malgré la finitude de nos existences et du monde qui nous entoure. Les questionnements phi­lo­so­phi­ques, religieux et scien­ti­fi­ques autour de l'existence et la nature de l'ensemble des entiers naturels ont tellement ob­sé­dés les hommes que le fruit de ces cogitations pourrait occuper un rayon complet de bi­blio­thè­que.

Il a fallu patienter jusqu'au début du siècle dernier pour que cet ensemble soit parfaitement caractérisé, c'est-à-dire défini grâce à des propriétés intrinsèques qu'il est le seul à posséder une fois dépouillé de tout autre attribut que de sa relation d'ordre :

En mathématiques, l'existence d'un ensemble naturel est acquise grâce à un axiome de la théorie des ensembles, l'axiome de l'infini.*(*) La construction ef­fec­ti­ve des entiers naturels est étudiée en lo­gi­que. C'est in­du­bi­ta­ble­ment l'ensemble séminal de cette théo­rie.

On peut démontrer, mais ce n'est pas l'objet de ce cours, que si l'on se donne deux ensembles na­tu­rels, il existe toujours entre eux une unique bijection croissante telle que sa bijection réciproque est elle aussi croissante (il s'agit d'un isomorphisme d'ensembles ordonnés, comme nous le verrons au prochain chapitre). Ceci signifie que même si ces deux ensembles naturels ne sont pas à strictement parler égaux, ils sont jumeaux, rien ne les distingue du point de vue de leurs relations d'ordres res­pec­ti­ves. Autrement dit, nous pouvons toujours identifier un ensemble naturel quelconque à un seul d'entre eux. John Von Neuman a imaginé un processus inductif de construction des éléments d'un ensemble naturel où l'ordre naturel \(\leq\) est hérité de la relation d'ordre constituée par l'inclusion ensembliste \(\subseteq\). Chaque nouvel ensemble ainsi construit contient un élément de plus que le précédent et chaque entier naturel \(n\) est codé par un ensemble de référence qui contient précisément \(n\) éléments.

Soit \(n\in\N\), la demi-droite \(\rrbracket n,\,\rightarrow\llbracket\) n'est pas vide, sans quoi \(n\) serait le plus grand élément de \(\N\), ce qui est absurde d'après la propriété 3 d'un ensemble naturel. Donc \(\rrbracket n,\rightarrow\llbracket\) admet un plus petit élément d'après la pro­prié­té 1 et on l'appelle le successeur de \(n\) que l'on note \(\succ(n).\)*(*) Il s'agit bien sûr de l'entier \(n+1\) mais nous n'avons pas encore défini l'addition. D'après la première propriété d'un ensemble naturel, \(\N\) contient un plus petit élément, on le note \(0\), son successeur \(1\), etc. et c'est une façon d'achever l'identification de cet ensemble à l'ensemble des entiers naturels bien connu du lecteur. Dans la suite du cours, on notera \(\N^*:=\N\setminus\{0\}\).

Il faut retenir que l'existence d'un successeur (resp. prédecesseur) n'est possible que grâce à la première (resp. deuxième) propriété d'un ensemble naturel.

Récurrences

Le principe de ré­cur­ren­ce (on dit parfois induction) est intimement lié à la structure d'ordre sur l'ensemble des entiers na­tu­rels. Il est parfaitement illustré par les vidéos spectaculaires de circuits de dominos qui tombent en cascade. Si l'on place correctement les dominos (i.e. si l'on s'assure qu'à tout endroit du circuit la chute d'un domino fera tomber le suivant, l'hérédité) et que l'on fait tomber le premier du circuit (l'initialisation), alors tous les dominos vont tomber à partir du premier.

Dans les différents théorèmes de récurrence qui vont suivre (récurrence simple, récurrence forte, récurrence multiple, récurrence finie), nous avons anticipé l'étude de l'addition dans \(\N\) pour écrire \(n+1\) au lieu de \(\succ(n)\) pour respecter les notations conventionnelles utilisées pour leurs énoncés.

Pour démontrer que \(P(n+1)\) est vrai, nous aurons parfois besoin de supposer que \(P(k)\) est vrai pour tous les entiers \(k\) compris entre \(a\) et \(n\).

Dans ce cas, il suffit de faire tomber les trois premiers (les \(k\) premiers) pour tous les faire tomber.

On peut également avoir besoin de démontrer une propriété pour un nombre fini de valeurs.

En guise d'exercice, le lecteur pourra énoncer et prouver le théorème de récurrence fini descendante où l'on fait tomber un nombre fini de dominos mais en partant du dernier.

Cardinaux.

Dans toutes les activités scientifiques, compter, dénombrer, estimer des quantités sont des pratiques essentielles et en apparence inoffensives. Malheureusement dès que l'on manipule des ensembles in­fi­nis, la notion de quantité s'avère délicate à généraliser et notre intuition est passablement mise en défaut. Il est par exemple logique de penser qu'il y a deux fois plus d'entiers naturels que d'entiers naturels pairs, or ce n'est pas le cas en un certain sens qu'il faudra préciser.

Plutôt que de dire que deux ensembles ont la même taille parce qu'ils ont le même nombre d'éléments, ce qui n'a de sens que si ces ensembles sont finis, on considère que deux ensembles sont de même taille si l'on est capable d'apparier chaque élément du premier avec un unique élément du second et réciproquement, à la manière des couples durant le slow du bal de promo où chaque étudiant a sa cavalière et qu'aucun ne se morfond sur le banc de touche. Les deux approches sont bien sûr équivalentes quand les ensembles sont finis, mais l'appariement a l'avantage de prolonger le concept si les ensembles sont infinis.

Le mot équipotent, contraction des mots latin equi (égal) et potent (puissant), signifie littéralement même puissance, au sens militaire du terme. L'équipotence est la bonne manière d'aborder la notion de cardinalité, elle permet de comparer la taille d'en­sem­bles quand bien même on ne peut pas les dénombrer. L'équipotence définit une relation d'équivalence sur une famille d'ensembles.

Soit \(n\in\N\). On note \(\N_n\) l'intervalle \(\llbracket 1,\,n\rrbracket \) pour l'ordre naturel avec la convention \(\N_0=\varnothing\), et on note \(\N^*\) l'en­semb­le \(\N\setminus\{0\}\). Il suffit d'observer le diagramme sagittal d'une injection, d'une surjection et d'une bijection entre deux ensembles finis pour se convaincre de la justesse de la proposition suivante (sans que cela ne constitue pour autant une preuve).

D'après la troisième assertion de la proposition ci-dessus, si un ensemble \(X\) est en bijection avec deux ensembles \(\N_m\) et \(\N_n,\) on a né­ces­sai­re­ment \(n=m\). En effet, en notant \(f:X\rg\N_n\) et \(g:X\rg\N_m\) ces deux bijections, la composée \(g\circ f^{-1}\) définit une bijection de \(\N_n\) dans \(\N_m\). Ceci légitime la définition suivante :

On ne parle de cardinal d'un ensemble que si cet ensemble est fini, dans le cas contraire il faut parler d'ensemble infini et non pas d'ensemble de cardinal infini, même si cet abus de langage est souvent pratiqué. Le cardinal d'un ensemble fini \(X\) est noté in­dif­fé­rem­ment \(\#X\) (usuel chez les anglo-saxons), \(\count{X}\) ou \(\text{card}(X)\).

Soit \(X\) et \(Y\) deux ensembles et \(f:X\rightarrow Y\) une application. On démontre que :

1. Toute partie \(A\) d'un ensemble fini \(X\) est finie et \(\count{A}\leq\count{X}\).
2. L'intersection d'une famille quelconque d'ensembles finis est fini,
3. Si \(X\) est fini alors \(\count{f(X)}\leq \count{X}\) avec égalité si et seulement si \(f\) est injective.
4. Si \(X\) est fini et \(f\) surjective, alors \(Y\) est fini et \(\count{Y}\leq \count{X}\) avec égalité si et ssi \(f\) est bijective.
5. Si \(f\) est injective et \(f(X)\) est fini alors \(X\) est fini et \(\count{X}=\count{f(X)}\).

On déduit de ces résultats le théorème suivant :

On définit l'addition de deux entiers naturels comme l'application \(+:\N\times\N\rightarrow\N\) définie par \begin{equation} \label{def:loiadd} x+y:=\count{X\cup Y} \end{equation} où \(X\) et \(Y\) sont deux ensembles quelconques disjoints et de cardinaux respectifs \(x\) et \(y\). On définit également le produit ou la multiplication de deux entiers naturels comme l'application \(\times:\N\times\N\rightarrow\N\) définie par \begin{equation} \label{def:loiprod} x\times y:=\count{X\times Y} \end{equation} mais cette fois les deux ensembles peuvent ne pas être disjoints. Notons que nous avons écrit ces applications avec une notation infixe plutôt que préfixe, \(x+y\) au lieu de \(+(x,y)\). Nous verrons au chapitre VI consacré aux structures que ces applications cons­ti­tuent des lois de compositions internes sur l'ensemble \(\N\) et nous étudierons leurs propriétés générales qui sont déjà bien connues du lecteur pour l'ensemble \(\N\).

Si \(a\mid b\), on dit que \(a\) divise \(b\) ou que \(a\) est un diviseur de \(b\) ou encore que \(b\) est un multiple de \(a\). C'est une relation d'ordre partiel (cf. exercice).

D'après cette définition, le nombre entier \(1\) n'est pas un nombre premier, il n'admet qu'un seul diviseur. Le plus petit nombre premier est donc l'entier naturel \(2\) et c'est le seul qui soit pair. On définit le plus grand commun diviseur comme le plus grand entier qui divise à la fois \(a\) et \(b\), on le note à la manière d'un couple \((a,b)\) ou parfois \(a\wedge b\), le contexte évitant toute confusion en général :

On définit le plus petit commun multiple de deux entiers \(a\) et \(b\), parfois noté \([a,b]\) ou encore \(a\vee b\) :

Si \((a,b)=1\), on dit que \(a\) et \(b\) sont premiers entre eux. Nous re­vien­drons en détail sur cette relation particulière et les interactions entre les deux lois additive et mul­tip­li­ca­ti­ve dans le chapitre consacré à l'Arithmétique.

On dit parfois qu'un ensemble est discret s'il est au plus dénombrable, dans le cas con­trai­re on dit qu'il est continu. Le terme discret qualifie plus généralement tout processus (au sens large) dans lequel le temps ou l'espace est indexé par un ensemble au plus dé­nom­bra­ble. Exemple : une horloge dont l'aiguille des secondes fait un bond à la position suivante à chaque seconde (processus discret) versus une horloge dont l'aiguille des secondes tourne continument autour du cadran (processus continu).

Nous pouvons à présent illustrer ce que nous disions en introduction au sujet des ensembles infinis et de la nécessité de se méfier de nos intuitions. Prenons par exemple l'ensemble des entiers naturels pairs : \[P:=\{n\in\N \such \exists k\in\N\ \ n=2k\},\] (parfois noté \(2\N\)) et soit \(f:\N\rightarrow P\) l'application définie par \(f(n):=2n\). Elle est injective car \(f(n)=f(m)\iff 2n=2m\iff n=m\). Elle est surjective car tout élément \(y\in P\) est pair ce qui signifie par définition qu'il existe un entier \(k\) tel que \(y=2k\), autrement dit \(k\) est l'antécédent de \(y\) que l'on cherchait. En conclusion, l'ensemble des entiers naturels pairs est équipotent à l'ensemble des entiers naturels, ce qui contredit l'idée informelle qu'il y a deux fois plus d'entiers que d'entiers pairs. C'est un résultat contre-intuitif puisque \(P\) est strictement inclus dans \(\N\) et pourtant les éléments de ces deux ensembles sont en bijection.

Analyse combinatoire

Il s'agit à présent d'étudier les cardinaux de certains ensembles finis. Cela va nous permettre (enfin) d'étudier le paradoxe des anniversaires. Plus généralement, calculer le cardinal d'ensembles est in­dis­pen­sa­ble en probabilités discrètes. Nous admettrons les propositions les plus difficiles à démontrer.

La définition de la multiplication de deux entiers \(n\) et \(m\) justifie immédiatement la proposition suivante et fournit au pas­sa­ge l'ex­pli­ca­tion de la notation du produit cartésien :

En itérant cette proposition \(n-1\) fois, on obtient le corollaire

Nous déjà rencontré la notation \(Y^X\) pour désigner l'ensemble des applications d'un ensemble \(X\) dans un ensemble \(Y\), en voici la justification :

On définit l'application factorielle de \(\N\) dans \(\N\) par

Et on note \(n!\) l'image d'un entier \(n\) pour cette application. C'est une fonction qui croît ex­trê­me­ment ra­pi­de­ment, bien plus rapidement que la fonction exponentielle. On a par exemple \(10!=3\,628\,800\) alors que \(\text{exp}(10)\approx 22\,026\).

Une bijection d'un ensemble fini sur lui-même s'appelle une permutation, une grande partie du prochain chapitre est consacrée à l'étude de ces bijections particulières.

La suite logique du cours serait de calculer le nombre de surjections d'un ensemble fini \(X\) dans un ensemble fini \(Y\), mais c'est un résultat plus difficile à établir, il faut donc patienter un peu.

Les coefficients binomiaux sont très utilisés en combinatoire, à tel point qu'il existe des ouvrages spécifiquement consacrés à leur étude, il faut donc en connaître les propriétés élémentaires. Soit \(p\) et \(n\) deux entiers tels que \(0\leq p\leq n\). On a

D'autre part,

Ce dernier résultat s'obtient simplement. L'équipotence définit une relation d'équivalence sur l'en­semb­le \({\mathscr P}(X)\) et les \(n+1\) classes d'équivalence sont constituées des parties \({\mathscr P}_p(X)\) de \(X\) à \(p\) éléments, \(p\in\llbracket 0,\,n\rrbracket \) formant une partition de \({\mathscr P}(X)\). L'égalité \((\ref{eq:cardparties})\) et la formule de sommation \((\ref{eq:sommation})\) permettent de conclure.

Le Triangle de Pascal est une table à deux entrées qui contient à la ligne \(n\) et à la colonne \(p\), le coefficient binomial \(\binom{n}{p}\). La \(n\)-ème ligne contient donc les \(n+1\) coefficients \(\binom{n}{p}\) pour \(p\in\llbracket 0,\,n\rrbracket \), ce qui explique la formation en triangle de ces nombres dans la table (il y a un coefficient de plus d'un eligne à la suivante). Il est construit ligne après ligne à l'aide d'un algorithme itératif qui s'appuie sur la formule \((\ref{id:comb2})\) : \begin{equation*} \begin{matrix} \ \ \ \text{ligne}~:\ \\ \text{colonne}~:\ \end{matrix} {\color{#FF8}\binom{n+1}{p+1}} ={\color{#88F}\binom{n}{p}}+{\color{#88F}\binom{n}{p+1}}. \end{equation*}

La formule du binôme de Newton fait apparaître les coefficients binomiaux dans le développement de \((x+y)^n\). Cette formule est valable dès que l'ensemble auquel appartiennent \(x\) et \(y\) est un anneau*(*) Nous étudierons cette structure dans le cha­pi­tre consacré à l'ari­thmé­ti­que. et que ces deux éléments commutent.

Savoir construire le triangle de Pascal permet de retrouver très rapidement les coefficients des dif­fé­rents termes de cette somme plutôt que d'apprendre par cœur les coefficients binomiaux.

Si l'on se donne deux ensembles \(X\) et \(Y\), le cardinal de leur réunion est égal à la somme de leurs car­di­naux moins le nombre d'éléments qu'ils ont en commun, soit

\[\count{X\cup Y}=\count{X}+\count{Y}-\count{X\cap Y}.\]

Nous admettrons le théorème suivant appelé principe d'inclusion/exclusion et qui gé­né­ra­li­se ce résultat.

La sommation de l'expression \((\ref{eq:somminout})\) se fait sur toute suite d'indices \((i_j)_{i\in\llbracket 1,\, k\rrbracket}\) strictement croissante et bornée par les valeurs \(1\) et \(n\).

Paradoxe des anniversaires

Nous avons à présent tous les outils pour étudier le paradoxe des anniversaires. La modélisation du problème passe par un encodage, c'est-à-dire une représentation des éléments concrets impliqués dans le problème à l'aide d'objets mathématiques abstraits. Il nous faut trouver un support pour re­pré­sen­ter les étudiants et un autre pour représenter les dates de naissance. Cette première phase est certainement aussi difficile à franchir que celle qui consiste à résoudre un problème mathématique déjà formulé de manière abstraite, tout au moins pour un débutant.

Comment coder un étudiant mathématiquement ? Quelle information le concernant doit-on garder dans notre modèle ? Comment va-t-on représenter une date d'anniversaire ? Si l'on calque di­rec­te­ment l'expérience dans une salle de classe, on conserverait le nom, et éventuellement le prénom en cas d'homonymie*(*) deux per­son­nes dis­tinc­tes doivent avoir des identifiants dis­tincts, on veut donc une injection., des étudiants. Autrement dit, un étudiant serait naturellement codé par un couple \((p,n)\) constitué par son prénom et son nom, ces mots étant eux-mêmes codés par deux mots (des séquences) de lettres, i.e. d'éléments de l'alphabet (un ensemble fini) latin \({\mathscr A}=\{a,b,\ldots,z\}\). Une date de naissance serait représentée par le quantième du jour et le quantième du mois de naissance, autrement dit un couple \((j,m)\in\llbracket 1,\,31\rrbracket\times\llbracket 1,\,12\rrbracket.\)

C'est un modèle tout à fait convenable, mais il est bien trop riche pour nos besoins. En effet, le problème ne demande pas d'identifier les étudiants qui sont potentiellement nés le même jour, ni les autres d'ailleurs. D'autre part, les dates de naissance de ces éventuelles coïncidences ne sont pas exigées non plus. C'est le nombre d'étudiants dans la classe et le nombre de jours dans l'année qui sont déterminants. Il est donc plus pertinent de coder la classe par un ensemble fini à \(n\) éléments, l'entier naturel \(n\) désignant le nombre d'étudiants, et d'encoder la date de naissance par un entier naturel compris entre \(1\) et \(365\) en faisant abstraction du jour et du mois.

On a donc, d'un côté l'ensemble des étudiants \(X\) et de l'autre l'ensemble des dates de naissance \(Y\:=\ab{1}{365}\). Si l'ensemble des étudiants est de cardinal \(n\), par définition il est équipotent à l'ensemble \(\ab{1}{n}\), autant supposer que \(X=\ab{1}{n}\). Notons que si le problème demandait également d'identifier les étu­diants, nous pourrions malgré tout continuer à utiliser l'intervalle \(\ab{1}{n}\) pour les représenter. Il suffirait de conserver la bijection qui lie \(\ab{1}{n}\) à \(X\) pour retrouver le couple \((p,n)\). C'est exactement ce que fait l'administration avec le numéro qui vous identifie sur votre carte d'étudiant.

Une relation lie les éléments de ces deux ensembles, chaque numéro \(x\) d'étudiant est associé à un quan­tième \(y\) de l'année codant la date de naissance de l'étudiant. Il s'agit bien sûr d'une application \(f:\ab{1}{n}\rightarrow \ab{1}{365}\). Avec ce modèle, dire qu'il n'existe pas d'étudiants nés le même jour se traduit par deux étudiants distincts ont des dates de naissances distinctes qui est la propriété caractérise des injections.

Résumons la situation. Un amphi particulier contenant \(n\) étudiants définit une instance du problème, à savoir une ap­pli­ca­tion \(f:\ab{1}{n}\rightarrow\ab{1}{365}\). Nous savons que si cette application est injective, tous les étudiants sont nés un jour différent. Sans même introduire le langage du calcul des pro­ba­bi­li­tés, qui sera étudié au prochain chapitre, si l'on se donne la taille \(n\) d'une classe et que l'on est capable de calculer le nombre d'ap­pli­ca­tions injectives possibles (c'est-à-dire le nombre de façons d'attribuer \(n\) dates de naissance de manière à ce que tous les étudiants soient nés un jour différent), et le nombre total d'applications, le ratio \(R_n\) de ces deux nombres nous fournira la probabilité qu'un amphi de \(n\) étudiants ne contiennent jamais deux étudiants nés le même jour. Comme nous cherchons la probabilité de l'évènement complémentaire, à savoir la probabilité qu'il existe au moins deux étudiants nés le même jour, il ne restera qu'à trouver la plus petite valeur de \(n\) telle que \(1-R_n>1/2\), soit \(R_n<1/2\).

Si l'on note \(X\hookrightarrow Y\) l'ensemble des injections d'un ensemble \(X\) dans un ensemble \(Y\), l'entier en question est défini formellement de la manière suivante : \begin{equation} \min{\left\{{\color{white}n\in\N\mid \frac{{\color{#FF8}\#(\ab{1}{n}\hookrightarrow\ab{1}{365})}}{{\color{blue}\#\ab{1}{365}^{\ab{1}{n}}}}<\frac{1}{2}}\right\}}. \end{equation} Ce minimum existe puisque cet ensemble est une partie non-vide de \(\N\), elle contient au moins les entiers strictement supérieurs à \(365\), et admet donc un plus petit élément d'après la 3ème propriété caractéristique d'un ensemble naturel.

Revenons au calcul. La formule \((\ref{eq:nbapplications})\) nous fournit le nombre d'applications et la formule \((\ref{eq:nbinjections})\) le nombre d'injections entre deux ensembles finis. Il suffit de les appliquer pour obtenir le ratio attendu :

On cherche donc la plus petite valeur entière \(n\leq 365\) telle que

Il ne semble pas facile d'isoler la variable \(n\) dans cette inégalité. On peut bien sûr éviter de se triturer les méninges en faisant travailler une machine qui calcule les différentes valeurs de \(R_n\) jusqu'à ce que le seuil soit atteint. Par exemple avec ce petit script en Python :

def R(n):
   P = 1
   for i in range(n):
      P = P * ((365 - i) / 365)
   return P

n = 2
while R(n) >= 0.5:
   n = n + 1
print("R(" + str(n) + ") = " + str(R(n)))

On pourrait se contenter de ce programme pour répondre à la question, mais il faut réaliser dès à présent que nombre de problèmes ne peuvent être résolus à l'aide d'un programme informatique, parfois parce qu'un tel programme n'existe pas ou parce que le temps qu'il faudrait à ce programme pour nous fournir la réponse attendue est démesuré (Ces questions seront abordées en théorie de la calculabilité, en algorithmique et en théorie de la complexité). Il est donc important d'être en mesure d'analyser un problème, soit pour y répondre directement ou à défaut pour écrire des programmes plus efficaces.

On repart de l'expression de \(R_n\) à gauche dans \((\ref{ineq:anniv})\) pour obtenir

Nous allons exploiter quelques résultats vus dans le cours d'analyse du premier semestre pour évaluer ce produit. On rappelle que l'exponentielle réelle \(\text{exp}:\R\rg\R\) est définie par la somme de la série convergente de terme général \(\frac{x^n}{n!}\) :

On en déduit que \({\color{#88F}1-x} \approx \text{exp}\;(-x)\) si \(x\) est proche de \(0\), puisque dans ce cas les termes de degré supérieur ou égal à 2 deviennent négligeables comparés à \(x\). On réécrit \((\ref{eq:RNBIS})\) : \begin{align*} R_n&\approx \prod_{i=1}^{n-1}\text{exp}\,(-\frac{i}{365})\\ &\approx \text{exp}\,(-\frac{1}{365}{\sum_{i=1}^{n-1}i})\\ &\approx \text{exp}\,(-\frac{n(n-1)}{730})\\ \end{align*}

On doit finalement trouver la plus petite valeur de \(n\) telle que

Comme la fonction réciproque de la fonction exponentielle est la fonction logarithme et que cette dernière est croissante, on obtient

Ce qui nous amène à étudier le signe du polynôme \(P(x)=x^2-x-730\,\ln(2)\). On calcule le discriminant \(\Delta=1+2920\;\text{ln}\,(2)\) qui est strictement positif puisque \(\text{ln} > 0\). Pour que \(P(n)\) soit positif, donc du même signe que le coefficient de son monôme de degré 2, il faut que \(x\) soit à l'extérieur de l'intervalle \([x_1,x_2]\) formé par les deux racines de \(P(x)\). On peut passer au calcul effectif : \[ \Delta\approx 2\,025=(9\times 5)^2 \] et on en tire les deux racines \(x_1\approx -22\) et \(x_2\approx \mathbf{23}\) ce qui permet de retrouver le résultat numérique obtenu à l'aide de notre script Python.

Il ne faut pas limiter la portée de cette étude à la résolution d'un problème ludique. Nous allons voir que le paradoxe des anniversaires intervient en cryptographie. De la même manière qu'une signature manuelle ou une empreinte digitale est une très petite quantité qui résume et caractérise un individu, on peut construire l'empreinte numérique d'un document. Le calcul de cette empreinte est généralement réalisé par une fonction de hachage.

Il n'est pas question d'étudier ici les fonctions de hachage, nous n'en donnerons qu'une vision in­for­mel­le et intuitive. Une fonction de hachage \(h:X\rightarrow Y\) relie deux ensembles de tailles très dif­fé­ren­tes, l'ensemble de départ \(X\) est très grand et contient tous les documents possibles (n'importe quel texte, lettre, mode d'emploi, journal, encyclopédies, ce cours, etc.). L'ensemble d'arrivée est quant à lui très petit comparativement à l'ensemble \(X\), et contient donc les empreintes de ces documents.

Pour donner un ordre d'idée des cardinaux mis en jeu dans cette problématique, imaginons que les documents ne soient constitués qu'avec des symboles d'un alphabet minimaliste \(\mathscr A\) constitué des 26 lettres de l'alphabet et de l'espace. C'est nettement insuffisant pour représenter les documents qui nous entourent, puisque ni les majuscules, ni les chiffres, ni les symboles diacritiques (accents, cédille, etc.), ni une multitude de signes très communs ne sont disponibles, néanmoins contentons nous de cet alphabet. Un simple courrier manuscrit d'une page comporte environ \(1000\) symboles, le contenu d'un tel courrier peut donc être codé par un \(1000\)-uplet de \({\mathscr A}^{1000}\) et la formule \((\ref{eq:cardprodcart})\) sur le cardinal d'un produit cartésien nous donne immédiatement le nombre possible de courriers différents, il y en a

ce qui dépasse de très loin tout nombre représentant une quantité réelle puisque les physiciens estiment que le nombre d'atomes contenus dans l'univers observable est de l'ordre de \(10^{81}\)…

Nous savons d'après cet exercice que si l'ensemble des empreintes \(Y\) est petit par rapport à l'en­semb­le des documents, la fonction \(h\) ne peut certainement pas être injective. On souhaite ce­pen­dant que la fonction \(h\) satisfasse des conditions extrêmement contraignantes :

1. Calculer l'empreinte \(h(x)\) d'un document \(x\) donné est rapide,
2. Calculer l'image réciproque \(h^{-1}(y)\) d'une empreinte \(y\) donnée est infaisable,
3. Calculer deux documents \(x_1\) et \(x_2\) de même empreinte est infaisable,
4. Calculer un document \(x_2\) de même empreinte qu'un document \(x_1\) donné est infaisable.

Le terme infaisable signifie ici que le temps et/ou l'espace nécessaires pour obtenir le résultat dé­pas­sent de très loin les capacités des machines. Ces conditions permettent de vérifier l'intégrité d'un document ou d'assurer qu'un document est bien celui qu'on croit. En effet, toute modification d'un document se décèle facilement en calculant son empreinte et en la comprarant à l'empreinte ori­gi­na­le, les deux seront nécessairement différentes. D'autre part, si l'on connaît l'empreinte d'un do­cu­ment \(x_1\), et que quelqu'un présente un document \(x_2\) et prétend qu'il s'agit du document \(x_1\), il suffit de com­pa­rer leurs deux empreintes, si elles sont égales, c'est qu'il s'agissait bien du même document \(x_2=x_1\).

Les conditions 3 et 4 demandées aux fonctions de hachage nécessitent de s'intéresser au paradoxe des anniversaires. Si l'ensemble \(X\) des documents jouent le rôle de l'ensemble des étudiants et l'ensemble \(Y\) des empreintes le rôle de l'ensemble des dates d'anniversaire, nous savons déjà qu'il est certain qu'il existe deux documents qui ont la même empreinte puisqu'ici \(\count{X} > \count{Y}\), mais cette fois il s'agit de les trouver. Combien de documents doit-on tirer au hasard dans \(X\) pour que la probabilité d'en trouver qui ont la même empreinte soit supérieure à \(\frac{1}{2}\) ? Il nous faut donc déterminer le cardinal \(n\leq\count{Y}\) d'un sous-ensemble \(E\subset X\) d'échantillons qui assure que la probabilité que la restriction \(h|_E\) de la fonction de hachage à la partie \(E\) soit injective est inférieure à \(\frac{1}{2}\).

Comme ce sont des ordinateurs qui calculent des empreintes, elles sont vues comme des séquences binaires de longueur \(b\), i.e. \(Y:=\{0,1\}^b\), et on parle d'empreintes de \(b\) bits.*(*) binary digit.

À la lumière de cet exercice, il apparaît que la taille des échantillons à prélever est de l'ordre de la racine carrée de la taille de l'espace des empreintes, ce qui est considérablement plus faible et au­to­ri­se une attaque si la taille des empreintes n'est pas assez grande.

Compléments

Le corollaire suivant est immédiat :

À partir de cette proposition, on peut établir une formule explicite pour les nombres de Stirling à l'aide du principe d'inclusion/exclusion. Nous admettrons ce résultat.

Pour conclure, nous admettrons également le théorème suivant qui permet de mesurer la croissance de la fonction fac­to­riel­le.

Autrement dit, la fonction factorielle se comporte asymptotiquement comme la fonction \[n\mapsto\sqrt {2\pi n}\;\left(\frac{n}{e}\right)^n\] ce qui permet aisément de déduire que la fonction factorielle croît plus vite que la fonction ex­po­nen­tiel­le mais moins vite que la fonction \(n\mapsto n^n.\) : \begin{align*} \lim_{n\to+\infty}\frac{e^n}{n!}&=0\\ \lim_{n\to+\infty}\frac{n!}{n^n}&=0\\ \end{align*}

Travaux pratiques

En séance

Compléments hors séance

On peut créer un script Python qui soit directement exécutable comme une commande unix et également récupérer les arguments éventuels de la commande. Pour cela :

1. Écrivez #!/usr/bin/python3 sur la première ligne du script.
2. Importez le module système : import sys.
3. Les arguments de la ligne de commande sont rangés dans la liste prédéfinie sys.argv sous forme de chaînes de caractères (sys.argv[0] contient le nom de votre script).
4. Exécutez la commande unix chmod +x monscript si votre script s'appelle monscript (l'extension .py n'est plus nécessaire).
5. Pour exécuter le script, il suffit de lancer ./monscript suivi éventuellement de paramètres.

#!/usr/bin/python3
import sys

def plusun(n):
   return n + 1

if len(sys.argv) > 0:
   n = int(sys.argv[1])
   print(plusun(n))
else:
   print("Syntaxe: ",argv[0]," entier")

Une fois transformé en fichier exécutable avec la commande chmod +x increment, la commande

$ ./increment 13

$ 14

$ ./increment

$ Syntaxe: increment entier