|

Exercices corrigés MPSI-PCSI : dénombrement et probabilités

↩ Chapitre : Dénombrement et probabilités (MPSI-MP) · Probabilités (PCSI-PSI)

Introduction

Douze exercices corrigés de dénombrement et de probabilités sur un univers fini, classés par difficulté croissante : anagrammes et tirages, formule de Bayes, indépendance, paradoxe des anniversaires, espérance et variance par les indicatrices, Bienaymé-Tchebychev, formule du crible, dérangements, chemins et nombres de Catalan. Tous restent dans le cadre du programme officiel de MPSI et de PCSI.

Avant de commencer

Ces exercices s’appuient sur les résumés de cours (MPSI, PCSI). Cherchez chaque exercice avant d’ouvrir le corrigé.

Exercices

Exercice 1 · Anagrammes ★★★

Combien d’anagrammes (mots de 11 lettres, ayant un sens ou non) peut-on former avec les lettres du mot MISSISSIPPI ?

Corrigé

Le mot comporte 1 M, 4 I, 4 S et 2 P. On choisit les 4 places des I parmi 11, puis les 4 places des S parmi les 7 restantes, puis les 2 places des P parmi 3, le M occupant la dernière place :

    \[\binom{11}{4}\binom74\binom32=330\times35\times3=34\,650=\frac{11!}{4!\,4!\,2!\,1!}.\]

Exercice 2 · Au moins un as ★★★

On tire au hasard une main de 5 cartes dans un jeu de 32 cartes (qui contient 4 as). Quelle est la probabilité d’obtenir au moins un as ?

Corrigé

L’univers est l’ensemble des parties à 5 éléments, muni de la probabilité uniforme : |\Omega|=\binom{32}{5}=201\,376. L’événement contraire « aucun as » correspond aux mains formées avec les 28 autres cartes : \binom{28}{5}=98\,280. La probabilité cherchée vaut 1-\dfrac{98\,280}{201\,376}\approx0{,}512.

Exercice 3 · Un test de dépistage ★★★

Une maladie touche 1\,\% d’une population. Un test est positif chez 99\,\% des malades et chez 2\,\% des personnes saines. Une personne a un test positif : quelle est la probabilité qu’elle soit malade ?

Corrigé

Notons M « être malade » et T « test positif ». (M,\overline M) est un système complet d’événements ; par la formule des probabilités totales, P(T)=0{,}99\times0{,}01+0{,}02\times0{,}99=0{,}0297. Par la formule de Bayes :

    \[P(M\mid T)=\frac{P(T\mid M)P(M)}{P(T)}=\frac{0{,}0099}{0{,}0297}=\frac13.\]

Malgré la fiabilité apparente du test, deux tests positifs sur trois sont de « faux positifs », parce que la maladie est rare.

Exercice 4 · Indépendance deux à deux, indépendance mutuelle ★★★

On lance deux dés équilibrés. On note A : « le premier dé donne un nombre pair », B : « le second dé donne un nombre pair », C : « la somme est paire ». Les événements A,B,C sont-ils indépendants deux à deux ? Mutuellement indépendants ?

Corrigé

L’univers \{1,\dots,6\}^2 est muni de la probabilité uniforme. P(A)=P(B)=\frac12, et C signifie que les deux dés ont la même parité : P(C)=\frac12. Or A\cap B, A\cap C et B\cap C sont tous égaux à l’événement « les deux dés sont pairs », de probabilité \frac14=\frac12\times\frac12 : indépendance deux à deux. Mais P(A\cap B\cap C)=\frac14\neq\frac18=P(A)P(B)P(C) : les trois événements ne sont pas mutuellement indépendants.

Exercice 5 · Le paradoxe des anniversaires ★★★

Dans un groupe de n\leqslant365 personnes (années de 365 jours, naissances uniformes et indépendantes), on note p_n la probabilité que les anniversaires soient tous distincts.

  1. Montrer que p_n=\displaystyle\prod_{k=0}^{n-1}\Big(1-\frac{k}{365}\Big).
  2. En utilisant 1-x\leqslant e^{-x}, montrer que p_n\leqslant\exp\Big(-\dfrac{n(n-1)}{730}\Big), puis que p_{23}<\frac12.
Corrigé

1. L’univers est l’ensemble des 365^n n-listes de jours, et l’événement correspond aux n-listes d’éléments distincts : p_n=\dfrac{365\times364\times\cdots\times(365-n+1)}{365^n}, qui est le produit annoncé.

2. p_n\leqslant\displaystyle\prod_{k=0}^{n-1}e^{-k/365}=\exp\Big(-\frac{1}{365}\cdot\frac{n(n-1)}{2}\Big). Pour n=23, \frac{23\times22}{730}=\frac{506}{730}\approx0{,}69315>\ln2\approx0{,}69314, donc p_{23}<e^{-\ln2}=\frac12 : dans un groupe de 23 personnes, il y a plus d’une chance sur deux que deux personnes aient le même anniversaire.

Exercice 6 · Espérances par les indicatrices ★★★

  1. Soit X\sim\mathcal{B}(n,p). Retrouver E(X)=np et V(X)=np(1-p) en écrivant X comme une somme de variables de Bernoulli indépendantes.
  2. Une urne contient N boules dont K blanches. On tire n\leqslant N boules sans remise et l’on note X le nombre de boules blanches obtenues. Montrer que E(X)=\dfrac{nK}{N}.
Corrigé

1. X a même loi que X_1+\dots+X_n, où les X_i sont indépendantes de loi \mathcal{B}(p). Par linéarité, E(X)=np ; les X_i étant indépendantes, les variances s’ajoutent : V(X)=np(1-p).

2. Numérotons les tirages et posons Y_i=1 si la i-ème boule tirée est blanche, 0 sinon. Par symétrie, chaque boule a la même probabilité \frac1N d’être tirée en i-ème position, donc P(Y_i=1)=\frac KN. Comme X=\sum_{i=1}^{n}Y_i, la linéarité de l’espérance (qui ne demande pas l’indépendance) donne E(X)=\frac{nK}{N}.

Exercice 7 · Points fixes d’une permutation aléatoire ★★★

Soit n\geqslant2 et \sigma une permutation de [\![1,n]\!] choisie uniformément. On note X le nombre de points fixes de \sigma. Calculer E(X) et V(X).

Corrigé

X=\sum_{i=1}^{n}X_i avec X_i=\mathbf 1_{\{\sigma(i)=i\}}. Il y a (n-1)! permutations fixant i, donc P(X_i=1)=\frac1n et E(X)=1. Pour i\neq j, P(X_iX_j=1)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}. Alors

    \[E(X^2)=\sum_iE(X_i^2)+\sum_{i\neq j}E(X_iX_j)=n\cdot\frac1n+n(n-1)\cdot\frac{1}{n(n-1)}=2,\]

et V(X)=E(X^2)-E(X)^2=1.

Exercice 8 · Bienaymé-Tchebychev ★★★

On lance 1000 fois une pièce équilibrée et l’on note S le nombre de « pile ». Montrer que P(400<S<600)\geqslant0{,}975.

Corrigé

S\sim\mathcal{B}\big(1000,\frac12\big) : E(S)=500 et V(S)=250. L’inégalité de Bienaymé-Tchebychev donne P(|S-500|\geqslant100)\leqslant\dfrac{250}{100^2}=0{,}025. Or l’événement contraire de \{|S-500|\geqslant100\} est \{400<S<600\}, d’où le résultat.

Exercice 9 · Nombre de surjections ★★★

Soient E et F deux ensembles finis de cardinaux n et p. À l’aide de la formule du crible, montrer que le nombre de surjections de E sur F vaut \displaystyle\sum_{k=0}^{p}(-1)^k\binom pk(p-k)^n. Que vaut cette somme si n<p ? si n=p ?

Corrigé

Notons F=\{y_1,\dots,y_p\} et B_j l’ensemble des applications de E dans F qui n’atteignent pas y_j. Une application est surjective si et seulement si elle n’est dans aucun B_j. Pour j_1<\dots<j_k, B_{j_1}\cap\dots\cap B_{j_k} est l’ensemble des applications à valeurs dans un ensemble à p-k éléments : il a (p-k)^n éléments. Par la formule du crible, \big|\bigcup B_j\big|=\displaystyle\sum_{k=1}^{p}(-1)^{k-1}\binom pk(p-k)^n, et le nombre de surjections vaut p^n-\big|\bigcup B_j\big|, ce qui donne la formule. Si n<p, il n’y a pas de surjection : la somme est nulle. Si n=p, les surjections sont les bijections : la somme vaut p!.

Exercice 10 · Dérangements ★★★

Un dérangement de [\![1,n]\!] est une permutation sans point fixe. On note D_n leur nombre.

  1. À l’aide de la formule du crible, montrer que D_n=n!\displaystyle\sum_{k=0}^{n}\frac{(-1)^k}{k!}.
  2. Quelle est la limite de la probabilité qu’une permutation aléatoire uniforme soit un dérangement ?
Corrigé

1. Soit A_i l’ensemble des permutations fixant i. Une intersection de k de ces ensembles a (n-k)! éléments (les k points fixés, les autres permutés librement). Par le crible :

    \[\Big|\bigcup_{i=1}^{n}A_i\Big|=\sum_{k=1}^{n}(-1)^{k-1}\binom nk(n-k)!=n!\sum_{k=1}^{n}\frac{(-1)^{k-1}}{k!},\]

et D_n=n!-\big|\bigcup A_i\big|=n!\displaystyle\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

2. La probabilité vaut \frac{D_n}{n!}=\displaystyle\sum_{k=0}^{n}\frac{(-1)^k}{k!}\to e^{-1}\approx0{,}368.

Exercice 11 · Chemins et nombres de Catalan ★★★

Un chemin est une suite de pas « droite » (1,0) et « haut » (0,1) partant de (0,0).

  1. Combien y a-t-il de chemins de (0,0) à (n,n) ?
  2. Montrer, par un argument de réflexion par rapport à la droite y=x+1, que le nombre de chemins de (0,0) à (n,n) qui touchent cette droite est \binom{2n}{n+1}.
  3. En déduire que le nombre de chemins de (0,0) à (n,n) restant sous la diagonale (y\leqslant x) est \dfrac{1}{n+1}\dbinom{2n}{n}.
Corrigé

1. Un chemin compte 2n pas dont n vers la droite : il y en a \binom{2n}{n}.

2. À un chemin qui touche la droite y=x+1, on associe le chemin obtenu en réfléchissant par rapport à cette droite la partie située avant le premier point de contact. On obtient un chemin de (-1,1) à (n,n), et l’on définit ainsi une bijection (l’opération inverse est la même réflexion, tout chemin de (-1,1) à (n,n) coupant la droite). Un chemin de (-1,1) à (n,n) compte n+1 pas à droite et n-1 vers le haut : il y en a \binom{2n}{n+1}.

3. Un chemin reste sous la diagonale si et seulement s’il ne touche pas la droite y=x+1. Leur nombre vaut \binom{2n}{n}-\binom{2n}{n+1}=\binom{2n}{n}\Big(1-\frac{n}{n+1}\Big)=\dfrac{1}{n+1}\binom{2n}{n} : c’est le n-ième nombre de Catalan.

Exercice 12 · Un long cycle dans une permutation aléatoire ★★★

Soit \sigma une permutation uniforme de [\![1,n]\!] et k un entier tel que \frac n2<k\leqslant n.

  1. Montrer que le nombre de permutations ayant un cycle de longueur k est \dfrac{n!}{k}.
  2. En déduire la probabilité q_n que \sigma possède un cycle de longueur strictement supérieure à \frac n2, puis sa limite.
Corrigé

1. Comme k>\frac n2, une permutation possède au plus un cycle de longueur k. On choisit son support (\binom nk façons), le cycle sur ce support ((k-1)! façons), puis une permutation quelconque des n-k autres éléments ((n-k)! façons) : \binom nk(k-1)!(n-k)!=\dfrac{n!}{k}.

2. Une permutation a au plus un cycle de longueur >\frac n2 : les événements correspondant aux différentes valeurs de k sont deux à deux incompatibles, et q_n=\displaystyle\sum_{\frac n2<k\leqslant n}\frac1k. D’après la fiche sur les suites numériques (sommes \sum_{k=m+1}^{2m}\frac1k\to\ln2), q_n\to\ln2\approx0{,}69 : une permutation « au hasard » a très souvent un cycle de longueur supérieure à la moitié de n.


Pour aller plus loin

Besoin d’aide sur ce chapitre ?

Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir ou un concours à préparer : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 20 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca ou en ligne.

Publications similaires