Exercices corrigés : dénombrement et probabilités (201-N11)

$\frac{11!}{8!}=\frac{11\times 10\times 9\times 8!}{8!}=11\times 10\times 9=990$. Piège : simplifier les nombres eux-mêmes, comme si $\frac{11!}{8!}$ valait $\left(\frac{11}{8}\right)!$, ce qui n'a aucun sens.

$A(9,4)=\frac{9!}{(9-4)!}=\frac{9!}{5!}=9\times 8\times 7\times 6=3\,024$ : quatre facteurs décroissants à partir de $9$.

$\binom{12}{4}=\frac{12\times 11\times 10\times 9}{4\times 3\times 2\times 1}$. On simplifie avant de multiplier : $\frac{12}{4\times 3}=1$ et $\frac{10}{2}=5$, d'où $11\times 5\times 9=495$.

Par symétrie, $\binom{20}{17}=\binom{20}{3}=\frac{20\times 19\times 18}{3\times 2\times 1}=20\times 19\times 3=1\,140$. Piège : appliquer la formule avec $k=17$, dix-sept facteurs au numérateur et au dénominateur, pour le même résultat au prix de beaucoup d'erreurs possibles.

Ordonné avec remise : chacune des $5$ positions a $6$ choix, donc $6^{5}=7\,776$. Piège : prendre $5^{6}=15\,625$, en échangeant le nombre de positions et le nombre de choix.

Non ordonné avec remise : $\binom{n+k-1}{k}=\binom{5+3-1}{3}=\binom{7}{3}=\frac{7\times 6\times 5}{6}=35$. Piège : $\binom{5}{3}=10$, qui interdit la répétition.

COCORICO a $8$ lettres : C trois fois, O trois fois, R et I une fois chacune. $\frac{8!}{3!\,3!}=\frac{40\,320}{36}=1\,120$. Piège : $8!=40\,320$, qui compte comme différents des mots obtenus en échangeant deux C ou deux O.

La ligne complète vaut $\sum_{k=0}^{10}\binom{10}{k}=2^{10}=1\,024$ ; il lui manque ici le terme $\binom{10}{0}=1$, donc la somme vaut $1\,023$. Piège : répondre $1\,024$ sans voir que la somme commence à $k=1$.

Binôme : le terme en $x^{4}$ est $\binom{7}{4}(2x)^{4}(-1)^{3}=35\times 16x^{4}\times(-1)=-560x^{4}$. Le coefficient vaut $-560$. Piège : oublier la puissance de $2$, ce qui donne $-35$, ou le signe de $(-1)^{3}$, ce qui donne $560$.

Par le complément : un ensemble à $8$ éléments a $2^{8}=256$ sous-ensembles ; on retire le vide, $\binom{8}{0}=1$, et les huit singletons, $\binom{8}{1}=8$. Il en reste $256-1-8=247$. Piège : retirer seulement les singletons, ce qui donne $248$.

Si une opération se décompose en $k$ étapes successives offrant respectivement $n_{1},n_{2},\dots,n_{k}$ choix, et si le nombre de choix à chaque étape ne dépend pas des choix précédents, alors le nombre total de résultats est le PRODUIT $n_{1}\times n_{2}\times\dots\times n_{k}$. Sur la figure, trois entrées ouvrent chacune deux plats, et chacun de ces six chemins ouvre deux desserts : on lit $3\times 2\times 2=12$ feuilles. L'arbre rend visible la condition d'application, chaque nœud d'un même niveau porte le même nombre de branches.

Quatre positions, 26 choix chacune, indépendants : $26^{4}=456\,976$ mots. On écrit le résultat avec ses séparateurs de milliers, parce que l'ordre de grandeur est l'information utile : un demi-million, ce qu'un programme énumère en une fraction de seconde.

IPv4 : $2^{32}=4\,294\,967\,296$, soit environ 4,3 milliards, moins que la population mondiale, ce qui explique l'épuisement du stock. IPv6 : $2^{128}\approx 3{,}4\times 10^{38}$, un nombre sans commune mesure, de l'ordre de $10^{28}$ adresses par habitant. Quadrupler le nombre de bits ne quadruple pas le nombre d'adresses, il l'élève à la puissance quatre : c'est le point que le principe multiplicatif rend évident.

$2^{24}=16\,777\,216$ teintes, environ 16,7 millions. On peut aussi le voir comme $256^{3}$, chaque composante prenant 256 valeurs : les deux écritures donnent le même nombre, puisque $256=2^{8}$ et $\left(2^{8}\right)^{3}=2^{24}$.

Sans contrainte : $26\times 26\times 10^{4}=676\times 10\,000=6\,760\,000$ identifiants. Avec deux lettres DISTINCTES, le second choix n'offre plus que 25 possibilités : $26\times 25\times 10^{4}=6\,500\,000$. La perte est de $260\,000$ identifiants, soit environ 3,8 pour cent. Notez que le principe multiplicatif s'applique encore, bien que le nombre de choix de la deuxième étape dépende de la première : ce qui compte est que ce NOMBRE soit toujours le même, ici 25, quelle que soit la lettre déjà prise.

ORDONNÉ SANS REMISE, les arrangements : $\frac{n!}{(n-k)!}$, pour « combien de podiums ». ORDONNÉ AVEC REMISE, les listes : $n^{k}$, pour « combien de mots de passe ». NON ORDONNÉ SANS REMISE, les combinaisons : $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$, pour « combien de comités ». NON ORDONNÉ AVEC REMISE : $\binom{n+k-1}{k}$, pour « combien de façons de répartir des objets identiques ». La quatrième est la seule qu'on n'invente pas de tête, les trois autres se retrouvent par le principe multiplicatif.

Un classement complet de 5 candidats est une PERMUTATION : $5!=120$. C'est le cas particulier $k=n$ des arrangements, où $\frac{5!}{0!}=5!$ puisque $0!=1$ par convention. Cette convention n'est pas arbitraire, elle est ce qui rend la formule des arrangements valable jusqu'au bout.

DISTINCTS : c'est un arrangement de 3 lettres parmi 26, soit $26\times 25\times 24=15\,600$. AVEC RÉPÉTITIONS : c'est une liste, soit $26^{3}=17\,576$. L'écart est faible ici, 11,2 pour cent, mais interdire les répétitions RÉDUIT toujours le nombre de mots de passe : une règle qui interdit deux lettres identiques affaiblit donc le mot de passe au lieu de le renforcer, ce qui est le contraire de l'intuition.

L'ordre des numéros ne compte pas et l'on ne peut pas répéter : c'est une combinaison. $\binom{49}{6}=\frac{49\times 48\times 47\times 46\times 45\times 44}{720}=13\,983\,816$, soit près de 14 millions de grilles. La probabilité de gagner avec une grille est donc d'environ $7{,}15\times 10^{-8}$.

Quatre options booléennes indépendantes : chacune vaut vrai ou faux, donc $2^{4}=16$ configurations. Si l'on doit en activer EXACTEMENT 2, on choisit lesquelles sans se soucier de l'ordre : $\binom{4}{2}=6$. On peut vérifier la cohérence en sommant sur toutes les tailles : $\binom{4}{0}+\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4}=1+4+6+4+1=16$ ✓, ce qui est exactement la propriété du triangle de Pascal étudiée à l'exercice suivant.

On compte les parties à $k$ éléments d'un ensemble de $n$ éléments, en isolant un élément particulier $x$. Ces parties se répartissent en deux catégories sans recouvrement. Celles qui CONTIENNENT $x$ : il reste à choisir $k-1$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k-1}$. Celles qui ne le contiennent PAS : il faut choisir les $k$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k}$. Toute partie relève d'exactement un des deux cas, d'où l'égalité. Aucun calcul, seulement un partage en deux.

Sur la figure, $\binom{4}{2}=6$ est bien la somme des deux nombres qui le surplombent à la ligne précédente, $\binom{3}{1}=3$ et $\binom{3}{2}=3$, ce que marquent les deux traits. C'est la règle de construction du triangle : chaque nombre est la somme des deux du dessus, les bords valant 1 parce qu'il n'y a qu'une partie vide et qu'une partie pleine.

DÉNOMBREMENT : la somme $\sum_{k=0}^{n}\binom{n}{k}$ compte toutes les parties de l'ensemble, classées par taille ; or on peut aussi compter une partie en décidant pour CHAQUE élément s'il y appartient ou non, ce qui donne $2^{n}$ par le principe multiplicatif. Les deux comptages portent sur le même ensemble, donc ils sont égaux. BINÔME : la formule $(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{k}b^{n-k}$, appliquée avec $a=b=1$, donne directement $2^{n}=\sum_{k=0}^{n}\binom{n}{k}$. La figure affiche ces sommes ligne par ligne : 1, 2, 4, 8, 16, 32, 64.

PAR LA FORMULE : $\binom{10}{3}=\frac{10\times 9\times 8}{3\times 2\times 1}=\frac{720}{6}=120$. PAR PASCAL : $\binom{10}{3}=\binom{9}{2}+\binom{9}{3}=36+84=120$ ✓. La première méthode est celle à employer à la main, en simplifiant AVANT de multiplier ; la seconde sert quand on construit une table complète.

Il rencontre exactement le problème de Fibonacci naïf : les appels se RECOUVRENT massivement, car $\binom{n-1}{k-1}$ et $\binom{n-1}{k}$ redescendent vers les mêmes sous-problèmes. Le nombre d'appels devient de l'ordre de $\binom{n}{k}$ lui-même, donc astronomique. Le remède est le même : la MÉMOÏSATION, ou la construction itérative du triangle ligne par ligne, qui coûte $O(nk)$ opérations. C'est l'exemple canonique de programmation dynamique, et il n'est pas anodin que la relation combinatoire et la relation algorithmique soient la même égalité.

VERSION SIMPLE : si l'on range $n+1$ objets ou plus dans $n$ tiroirs, au moins un tiroir contient au moins deux objets. VERSION QUANTITATIVE : en rangeant $m$ objets dans $n$ tiroirs, au moins un tiroir contient au moins $\left\lceil\frac{m}{n}\right\rceil$ objets. La démonstration est par l'absurde : si chaque tiroir en contenait strictement moins, le total serait strictement inférieur à $m$, contradiction.

Les tiroirs sont les 12 mois, les objets sont les 13 personnes. Comme $13>12$, un mois au moins contient deux personnes ✓. Remarquez ce que l'énoncé ne dit PAS : il ne dit pas lequel, ni combien de paires. C'est un énoncé d'existence pur, du même genre que ceux du chapitre des théorèmes des valeurs moyennes.

$\left\lceil\frac{1000}{100}\right\rceil=10$ : au moins une case contient au moins 10 clés. C'est une garantie de PIRE CAS, indépendante de la fonction de hachage employée, si bonne soit-elle. Elle explique pourquoi une table de hachage doit prévoir une gestion des collisions, listes chaînées ou sondage, et pourquoi son coût d'accès n'est constant qu'en moyenne, jamais dans le pire cas.

Une fonction de hachage sur 256 bits a exactement $2^{256}$ valeurs possibles, un nombre fini. L'ensemble des fichiers, lui, est infini : on peut fabriquer des fichiers aussi longs qu'on veut. On range donc une infinité d'objets dans un nombre fini de tiroirs, et le principe garantit non seulement qu'une collision existe, mais qu'une infinité de fichiers partagent le même condensat. La sécurité d'une fonction de hachage ne repose donc PAS sur l'absence de collisions, qui est impossible, mais sur la difficulté d'en EXHIBER une.

Prenons une personne $A$. Elle a 5 relations, chacune de deux types, connue ou inconnue : par les tiroirs, l'un des deux types apparaît au moins $\left\lceil\frac{5}{2}\right\rceil=3$ fois. Supposons que $A$ connaisse trois personnes $B$, $C$ et $D$. Si deux d'entre elles se connaissent, disons $B$ et $C$, alors $A$, $B$ et $C$ se connaissent tous les trois ✓. Sinon, $B$, $C$ et $D$ sont mutuellement inconnues ✓. Le cas où $A$ ignore trois personnes se traite symétriquement. C'est le premier théorème de la théorie de Ramsey, et il tient entièrement dans deux applications du principe des tiroirs.

$P(A)=\frac{\text{nombre de cas favorables}}{\text{nombre de cas possibles}}$. La condition est que tous les cas élémentaires soient ÉQUIPROBABLES, ce qui n'est pas automatique et doit se justifier : un tirage au hasard, un dé équilibré, un générateur uniforme. Sur un univers non uniforme, la formule est fausse, et l'erreur classique consiste à l'appliquer à des événements composés plutôt qu'à des cas élémentaires.

L'univers est l'ensemble des mains de 5 cartes, soit $\binom{52}{5}=2\,598\,960$ mains équiprobables. Les mains favorables se construisent en deux étapes indépendantes : choisir 2 as parmi 4, soit $\binom{4}{2}=6$, et choisir les 3 autres cartes parmi les 48 non-as, soit $\binom{48}{3}=17\,296$. Total : $6\times 17\,296=103\,776$. Probabilité : $\frac{103\,776}{2\,598\,960}\approx 0{,}0399$, soit environ 4 pour cent.

Un octet a $2^{8}=256$ valeurs équiprobables. Celles qui contiennent exactement trois bits à 1 correspondent au choix des trois positions parmi huit : $\binom{8}{3}=56$. Probabilité : $\frac{56}{256}=0{,}21875$, soit environ 22 pour cent. C'est le maximum atteint pour 3 ou 4 bits à 1, ce qui traduit le fait qu'un octet aléatoire a rarement très peu ou très beaucoup de bits allumés.

Les 62 caractères se répartissent en 52 lettres et 10 chiffres. Aucun chiffre signifie que les 8 positions sont prises parmi les 52 lettres : $52^{8}$ cas favorables sur $62^{8}$ possibles. Probabilité : $\left(\frac{52}{62}\right)^{8}=0{,}8387^{8}\approx 0{,}2448$, soit environ 24 pour cent. Près d'un mot de passe aléatoire sur quatre ne contient aucun chiffre, ce qui explique pourquoi les politiques de sécurité l'imposent explicitement.

Parce que compter « au moins un » demande de distinguer les cas à un, deux, trois chiffres et ainsi de suite, alors que le contraire, « aucun », se compte d'un coup. La règle est $P(\text{au moins un})=1-P(\text{aucun})$. Ici : $1-0{,}2448=0{,}7552$, soit environ 76 pour cent. Le réflexe vaut pour tous les énoncés commençant par « au moins », et il sera décisif au problème des anniversaires de l'exercice 10.

$P(A\mid B)=\frac{P(A\cap B)}{P(B)}$ pour $P(B)\neq 0$ : c'est la probabilité de $A$ une fois que l'on SAIT que $B$ est réalisé, autrement dit on remplace l'univers par $B$. PROBABILITÉS TOTALES : si $B_{1},\dots,B_{n}$ forment une partition de l'univers, alors $P(A)=\sum_{i}P(A\mid B_{i})P(B_{i})$. C'est la formule qui permet de descendre l'arbre pondéré de la figure en multipliant le long des branches, puis en additionnant les feuilles favorables.

Notons $M$ malade et $T$ test positif. $P(M)=0{,}01$, $P(T\mid M)=0{,}99$, $P(T\mid\overline{M})=0{,}05$. Probabilités totales : $P(T)=0{,}01\times 0{,}99+0{,}99\times 0{,}05=0{,}0099+0{,}0495=0{,}0594$. Bayes : $P(M\mid T)=\frac{0{,}0099}{0{,}0594}=\frac{1}{6}\approx 0{,}1667$. Seulement UNE personne positive sur six est réellement malade.

L'intuition répond spontanément « environ 99 pour cent », en confondant $P(T\mid M)$ avec $P(M\mid T)$. L'écart vient de la RARETÉ de la maladie : sur 10 000 personnes, 100 sont malades et 99 seront détectées, mais 9900 sont saines et 495 d'entre elles seront positives à tort. Les faux positifs sont cinq fois plus nombreux que les vrais, non parce que le test est mauvais, mais parce qu'il s'applique à une population immense de gens sains. C'est la raison pour laquelle on ne dépiste pas systématiquement les maladies rares.

Notons $S$ pourriel et $G$ le mot présent. $P(G)=0{,}6\times 0{,}3+0{,}4\times 0{,}02=0{,}18+0{,}008=0{,}188$. Bayes : $P(S\mid G)=\frac{0{,}18}{0{,}188}\approx 0{,}9574$, soit environ 96 pour cent. Le résultat est cette fois très proche de la certitude, et le contraste avec la question b mérite d'être noté : la même formule donne 17 pour cent ici et 96 pour cent là. Ce qui change n'est pas la qualité de l'indice, c'est la probabilité A PRIORI, 1 pour cent contre 60 pour cent.

NON, c'est impossible. Incompatibles signifie $A\cap B=\varnothing$, donc $P(A\cap B)=0$. Indépendants signifie $P(A\cap B)=P(A)P(B)$, qui est strictement positif puisque les deux probabilités le sont. Les deux conditions se contredisent. Intuitivement : si $A$ et $B$ ne peuvent pas se produire ensemble, alors savoir que $A$ est réalisé apprend quelque chose de très fort sur $B$, à savoir qu'il ne l'est pas. Incompatible est donc le contraire d'indépendant, pas un synonyme, et cette confusion est l'une des plus coûteuses du chapitre.

Si $X$ prend les valeurs $x_{1},\dots,x_{m}$ avec les probabilités $p_{1},\dots,p_{m}$, alors $E(X)=\sum_{i}x_{i}p_{i}$. C'est la moyenne PONDÉRÉE des valeurs, et son interprétation est celle de la loi des grands nombres : en répétant l'expérience un grand nombre de fois, la moyenne des résultats observés se rapproche de $E(X)$. Une espérance n'est donc pas une prédiction pour un essai, c'est une prédiction pour un grand nombre d'essais.

L'élément est en position $k$ avec la probabilité $\frac{1}{n}$, et la recherche coûte alors $k$ comparaisons. Donc $E=\sum_{k=1}^{n}k\times\frac{1}{n}=\frac{1}{n}\times\frac{n(n+1)}{2}=\frac{n+1}{2}$. On retrouve la somme des premiers entiers démontrée par récurrence au chapitre précédent : les deux chapitres se rejoignent ici.

$E=\frac{1001}{2}=500{,}5$ comparaisons en moyenne, contre 1000 dans le PIRE CAS, celui où l'élément est en dernière position. Le rapport n'est que de 2 : l'analyse en moyenne ne change pas l'ordre de grandeur, la recherche séquentielle reste linéaire. C'est justement ce qui la distingue du tri rapide de la question e, où l'écart est d'un facteur des milliers.

Notons $X$ le nombre de lancers. On a $P(X=k)=\left(\frac{1}{2}\right)^{k}$, puisqu'il faut $k-1$ piles suivis d'une face. Donc $E=\sum_{k\geq 1}k\left(\frac{1}{2}\right)^{k}=2$. Une manière plus rapide de l'obtenir : le premier lancer coûte 1 ; avec la probabilité $\frac{1}{2}$ c'est fini, sinon on recommence à zéro. D'où $E=1+\frac{1}{2}E$, soit $E=2$. Ce raisonnement par conditionnement sur le premier pas est celui qu'on emploie pour analyser les algorithmes aléatoires.

EN MOYENNE : $2\times 10^{6}\times\ln\left(10^{6}\right)=2\times 10^{6}\times 13{,}8155\approx 2{,}76\times 10^{7}$ comparaisons, environ 28 millions. PIRE CAS : $\frac{\left(10^{6}\right)^{2}}{2}=5\times 10^{11}$, soit 500 milliards, dix-huit mille fois plus. On l'utilise quand même pour deux raisons. D'abord parce que le pire cas correspond à un tableau déjà trié avec un choix de pivot naïf, situation qu'un pivot ALÉATOIRE rend d'une improbabilité extrême. Ensuite parce que sa constante cachée est petite et qu'il travaille sur place, ce qui le rend en pratique plus rapide que le tri fusion, pourtant meilleur dans le pire cas. Choisir un algorithme demande donc de regarder les DEUX mesures et de savoir laquelle décrit l'usage réel.

FAUX, c'est exactement l'inverse. Interdire les répétitions RÉDUIT l'ensemble des mots de passe possibles : sur 3 caractères parmi 26, on passe de $26^{3}=17\,576$ à $26\times 25\times 24=15\,600$, soit 11 pour cent de moins. Toute règle qui interdit quelque chose réduit l'espace de recherche et facilite donc l'attaque par force brute. Ce qui renforce un mot de passe est d'AUGMENTER sa longueur et la taille de son alphabet, jamais d'ajouter des contraintes.

FAUX, et l'affirmation confond $P(T\mid M)$ avec $P(M\mid T)$. Avec une prévalence de 1 pour cent et 5 pour cent de faux positifs, la formule de Bayes donne $P(M\mid T)=\frac{1}{6}\approx 17$ pour cent. La raison est que les personnes saines sont 99 fois plus nombreuses, si bien que leurs 5 pour cent de faux positifs écrasent en nombre les vrais positifs. Une probabilité conditionnelle et sa réciproque n'ont aucune raison d'être proches.

FAUX, et les deux notions sont même contradictoires pour des événements de probabilité non nulle. Incompatibles donne $P(A\cap B)=0$ ; indépendants donne $P(A\cap B)=P(A)P(B)>0$. Savoir que $A$ s'est produit apprend au contraire que $B$ ne s'est pas produit, ce qui est le comble de la dépendance. Retenez la formulation : incompatible parle des ENSEMBLES, indépendant parle de l'INFORMATION.

FAUX, et c'est impossible par le principe des tiroirs. Une fonction de hachage sur 256 bits ne dispose que de $2^{256}$ valeurs alors que les fichiers possibles sont en nombre infini : une infinité de fichiers partagent donc chaque condensat. Ce qu'on demande à une bonne fonction de hachage n'est pas l'absence de collisions mais la difficulté d'en EXHIBER une, ce qui est une propriété calculatoire et non ensembliste.

FAUX. Une main de cartes est un ENSEMBLE : recevoir l'as puis le roi ou le roi puis l'as donne la même main. On utilise donc les COMBINAISONS, $\binom{52}{5}=2\,598\,960$. L'utilisation des arrangements donnerait $52\times 51\times 50\times 49\times 48=311\,875\,200$, soit 120 fois trop, exactement le facteur $5!$ qui compte les ordres d'une même main. Le test à faire systématiquement : deux résultats qui diffèrent seulement par l'ordre sont-ils le même résultat ?

Huit positions, 95 choix chacune : $95^{8}=6\,634\,204\,312\,890\,625$, soit environ $6{,}63\times 10^{15}$, un peu plus de six millions de milliards.

$\frac{6{,}63\times 10^{15}}{10^{10}}\approx 663\,420$ secondes, soit environ $7{,}68$ jours. Un mot de passe de huit caractères, même avec tous les symboles du clavier, tombe donc en une semaine face à du matériel dédié. Notez que ce chiffre est un PIRE cas, la moyenne étant deux fois plus courte, autour de quatre jours.

$95^{12}\approx 5{,}40\times 10^{23}$, donc $\frac{5{,}40\times 10^{23}}{10^{10}}=5{,}40\times 10^{13}$ secondes, c'est-à-dire environ $1{,}71\times 10^{6}$ années, soit près de 1,7 million d'années. Quatre caractères de plus font passer d'une semaine à un million d'années : le facteur est $95^{4}\approx 81{,}5$ millions.

$26^{8}=208\,827\,064\,576\approx 2{,}09\times 10^{11}$, donc $\frac{2{,}09\times 10^{11}}{10^{10}}\approx 21$ secondes. Conclusion : un mot de passe de huit lettres minuscules ne résiste pas une demi-minute. Le passage de 26 à 95 caractères multiplie la durée par 31 000, ce qui est considérable, mais reste dérisoire à côté de l'effet de la longueur.

$8\log_{2}95=8\times 6{,}570=52{,}6$ bits ; $12\log_{2}95=78{,}8$ bits ; $8\log_{2}26=8\times 4{,}700=37{,}6$ bits. L'entropie est PROPORTIONNELLE à la longueur et seulement LOGARITHMIQUE en la taille de l'alphabet : ajouter 4 caractères vaut $4\times 6{,}57=26{,}3$ bits, alors que passer de 26 à 95 caractères sur 8 positions n'en vaut que 15. La longueur pèse donc bien davantage, et c'est pourquoi les recommandations récentes préconisent des PHRASES de passe longues plutôt que des suites courtes de symboles exotiques, plus difficiles à retenir pour un gain moindre.