Problème ECG1 maths appliquées : trouver le circuit défectueux par tests de paquets

↩ Chapitre : Probabilités finies · Sommes et dénombrement (ECG1-ECG2)

Introduction

Un ordinateur contient n circuits dont un seul est en panne. On ne sait tester que des paquets : un test dit seulement si le circuit défectueux est dans le paquet. En testant des paquets tirés au hasard, combien de tests faut-il pour l’isoler ?

Le problème mobilise le dénombrement des parties d’un ensemble, l’indépendance mutuelle d’événements et la loi binomiale.

Le sujet

Problème d’après HEC 1986 (partie I), adapté au programme ECG 2021. Durée indicative : 1 h 30. Programme : ensemble des parties d’un ensemble fini, dénombrement, probabilités finies, indépendance, loi binomiale, Python.

Option : maths appliquées (le problème est aussi accessible en maths approfondies). Niveau : ★★. Faisable : dès le premier semestre, après les probabilités finies et la loi binomiale.

Énoncé et corrigé

Soit n\geqslant2 et C=\lbrace c_1,\dots,c_n\rbrace un ensemble de n circuits, dont un seul, c_n, est défectueux. On note \mathcal P(C) l’ensemble des parties de C (partie vide comprise) et, pour G\subset C, \overline G le complémentaire de G dans C.

Partie I – Une partie de C tirée au hasard

1 ▷ Soit A une partie de C de cardinal r (0\leqslant r\leqslant n). Combien y a-t-il de parties de C qui ne rencontrent pas A ? qui contiennent A ?

Indication

Une partie qui ne rencontre pas A est une partie de \overline A ; une partie qui contient A s’écrit A\cup H avec H\subset\overline A.

Corrigé

Les parties qui ne rencontrent pas A sont les parties de \overline A, qui a n-r éléments : il y en a 2^{n-r}.

G\mapsto G\cap\overline A est une bijection de l’ensemble des parties contenant A sur \mathcal P(\overline A) (réciproque H\mapsto A\cup H) : il y en a aussi 2^{n-r}.

2 ▷ On tire une partie G de C au hasard, de façon équiprobable parmi les 2^n parties. (a) Calculer la probabilité que G contienne une partie donnée A de cardinal r. (b) Soit j\neq n. Calculer la probabilité que c_j\in G sachant que c_n\in G.

Indication

(a) Utiliser la question 1. (b) P(c_j\in G\text{ et }c_n\in G) est le cas A=\lbrace c_j,c_n\rbrace.

Corrigé

(a) P(A\subset G)=\dfrac{2^{n-r}}{2^n}=\dfrac1{2^r}. En particulier, chaque circuit appartient à G avec la probabilité \frac12.

(b) P_{(c_n\in G)}(c_j\in G)=\dfrac{1/4}{1/2}=\dfrac12=P(c_j\in G) : les événements (c_j\in G) et (c_n\in G) sont indépendants.

Partie II – Tests successifs

Soit h\geqslant1. On tire successivement et avec remise h parties B_1,\dots,B_h de C, chacune de façon équiprobable. On teste chaque paquet B_i : on pose G_i=B_i si B_i contient le circuit défectueux et G_i=\overline{B_i} sinon. Ainsi c_n\in G_i dans tous les cas. On note D_h=G_1\cap\cdots\cap G_h l’ensemble des circuits encore suspects après h tests.

3 ▷ Soit S une partie de C contenant c_n. Montrer que P(G_1=S)=\dfrac1{2^{n-1}}. En déduire que, pour j\neq n, P(c_j\in G_1)=\frac12.

Indication

G_1=S se produit si et seulement si B_1=S ou B_1=\overline S.

Corrigé

Comme c_n\in S et c_n\notin\overline S, on a (G_1=S)=(B_1=S)\cup(B_1=\overline S), réunion de deux événements incompatibles de probabilité \frac1{2^n} chacun : P(G_1=S)=\dfrac2{2^n}=\dfrac1{2^{n-1}}. Ainsi G_1 suit la loi uniforme sur les 2^{n-1} parties contenant c_n.

Parmi ces 2^{n-1} parties, celles qui contiennent c_j sont au nombre de 2^{n-2} (question 1 avec A=\lbrace c_j,c_n\rbrace) : P(c_j\in G_1)=\dfrac{2^{n-2}}{2^{n-1}}=\dfrac12.

4 ▷ (a) Soit E une partie de cardinal r ne contenant pas c_n. Montrer que P(E\subset D_h)=\dfrac1{2^{rh}}. (b) En déduire que les événements (c_j\in D_h), 1\leqslant j\leqslant n-1, sont mutuellement indépendants, de probabilité \frac1{2^h}.

Indication

(a) Commencer par h=1 : P(E\subset G_1)=\frac1{2^r} (dénombrer les parties contenant E\cup\lbrace c_n\rbrace). Les tirages étant avec remise, les G_i sont indépendantes.

Corrigé

(a) Les parties contenant c_n et E sont au nombre de 2^{n-r-1}, donc P(E\subset G_1)=\dfrac{2^{n-r-1}}{2^{n-1}}=\dfrac1{2^r}. Comme E\subset D_h\iff E\subset G_i pour tout i, et que les tirages sont indépendants : P(E\subset D_h)=\left(\dfrac1{2^r}\right)^h=\dfrac1{2^{rh}}.

(b) Avec r=1 : P(c_j\in D_h)=\frac1{2^h}. Pour toute famille d’indices distincts j_1,\dots,j_r de [\![1,n-1]\!], (a) appliqué à E=\lbrace c_{j_1},\dots,c_{j_r}\rbrace donne P\big(\bigcap_k(c_{j_k}\in D_h)\big)=\frac1{2^{rh}}=\prod_kP(c_{j_k}\in D_h) : les événements sont mutuellement indépendants.

5 ▷ On note N_h le nombre de circuits sains encore suspects après h tests, c’est-à-dire N_h=\mathrm{card}(D_h)-1. (a) Quelle est la loi de N_h ? Donner son espérance. (b) En déduire P(D_h=\lbrace c_n\rbrace)=\left(1-\dfrac1{2^h}\right)^{n-1}.

Indication

N_h compte les succès dans n-1 épreuves de Bernoulli indépendantes (« c_j est encore suspect »).

Corrigé

(a) N_h=\displaystyle\sum_{j=1}^{n-1}\mathbf 1_{(c_j\in D_h)} est la somme de n-1 variables de Bernoulli mutuellement indépendantes de paramètre \frac1{2^h} : N_h\sim\mathcal B\left(n-1,\frac1{2^h}\right) et E(N_h)=\dfrac{n-1}{2^h}.

(b) D_h=\lbrace c_n\rbrace\iff N_h=0, d’où P(D_h=\lbrace c_n\rbrace)=\left(1-\dfrac1{2^h}\right)^{n-1}. Chaque test divise en moyenne par deux le nombre de circuits sains suspects.

6 ▷ (Python) On prend n=100. Écrire un programme qui détermine le plus petit h tel que la panne soit isolée avec une probabilité au moins égale à 0{,}95. Comparer avec \log_2(100)\approx6{,}6.

Indication

Boucle while sur h tant que (1-2^{-h})^{99}<0{,}95.

Corrigé
n, h = 100, 1
while (1 - 2**(-h))**(n - 1) < 0.95:
    h = h + 1
print(h)

On obtient h=11 : \left(1-2^{-10}\right)^{99}\approx0{,}908 et \left(1-2^{-11}\right)^{99}\approx0{,}953. Il faut à peine plus de tests qu’avec une recherche dichotomique (7 tests, mais en choisissant soi-même les paquets) : le hasard coûte seulement quelques tests.


Pour aller plus loin

Besoin d’aide sur ce chapitre, ou un concours à viser ?

Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir surveillé — ou l’ambition d’intégrer une grande école : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 25 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca, ou à distance, partout au Maroc et en France.

🎯 Prépas commerciales : réussir les écrits BCE et Ecricome et intégrer les meilleures écoles de commerce (HEC, ESSEC, ESCP…).

Publications similaires