Ensembles : minimum garanti et formules de dénombrement

Combien de personnes doivent nécessairement avoir toutes les caractéristiques demandées ? Les données ne déterminent pas toujours un effectif exact : souvent, elles donnent un minimum garanti. Partons d’une énigme pour établir une formule valable pour un nombre quelconque d’ensembles et distinguer cette question du dénombrement exact.

Laboratoire : compter avec les ensembles · Laboratoire visuel de Venn

1. L’énigme des 100 médecins

Un hôpital emploie 100 médecins : 75 parlent anglais, 80 espagnol, 85 français et 90 allemand. Quel est le nombre minimum garanti de médecins parlant les quatre langues ? Une même personne peut appartenir à plusieurs groupes.

La réponse n’est pas « exactement 30 », mais « au moins 30, et 30 est possible ».

Calculer et expliquer

2. Compter les absences plutôt que les présences

Fixons un univers U de N éléments et k sous-ensembles A₁,…,Aₖ. Notons aᵢ=|Aᵢ| la taille du groupe i. S=a₁+⋯+aₖ compte des appartenances, pas des personnes distinctes, et peut dépasser N. Une personne présente dans tous les groupes n’a aucune absence.

Il manque N−aᵢ éléments au groupe i. Le total des absences est M=(N−a₁)+⋯+(N−aₖ)=kN−S. Une personne peut manquer dans plusieurs groupes : le nombre de personnes ayant au moins une absence est donc au plus M, sans dépasser N. Le complémentaire de l’intersection est l’union des complémentaires : U∖(A₁∩⋯∩Aₖ)=(U∖A₁)∪⋯∪(U∖Aₖ).

x ≥ N−min(N,M) = max(0,N−M) = max(0,S−(k−1)N)

3. Formule générale et preuve par comptage

Soit x=|A₁∩⋯∩Aₖ| l’effectif commun. Ces x personnes produisent kx appartenances. Chacune des N−x autres appartient au plus à k−1 groupes. Ainsi :

S ≤ kx+(k−1)(N−x)
S ≤ kx+(k−1)N−(k−1)x
S ≤ x+(k−1)N
x ≥ S−(k−1)N.

Puisque x≥0, on obtient la formule cherchée si seuls N et les tailles des groupes sont connus, avec 0≤aᵢ≤N :

x minimum = max(0, a₁+⋯+aₖ−(k−1)N)

Pour deux groupes on soustrait N ; pour trois, 2N ; pour quatre, 3N. Pour les médecins : max(0,75+80+85+90−3×100)=max(0,330−300)=30. Le maximum avec zéro évite une réponse négative. « Minimum zéro » signifie qu’aucune personne commune n’est garantie, pas que l’intersection est forcément vide.

4. Pourquoi la borne est réalisable

Une inégalité ne prouve pas à elle seule qu’un minimum est réalisable. Si M≤N, attribuons les N−aᵢ absences de chaque groupe à des personnes toutes différentes. Exactement M personnes ont une absence et N−M n’en ont aucune : le minimum annoncé.

Si M≥N, imaginons les N personnes en cercle. Attribuons les absences du premier groupe à des personnes consécutives ; poursuivons avec le deuxième là où nous nous sommes arrêtés, puis les suivants, en recommençant le tour au besoin. Chaque bloc compte au plus N personnes : personne ne manque deux fois dans le même groupe. Au moins N attributions consécutives couvrent tout le monde : aucune personne n’est commune à tous les groupes. La formule donne bien zéro.

Cette construction respecte chaque taille initiale. Elle suppose l’absence d’autres contraintes : des intersections imposées exigeraient une vérification distincte. Le laboratoire construit et vérifie une répartition même lorsque M≥N.

Calculer et expliquer

5. Le maximum : certain ou possible

L’intersection ne peut contenir plus d’éléments que le plus petit groupe. En emboîtant les ensembles du plus petit au plus grand, on atteint ce maximum.

x maximum = min(a₁,…,aₖ)

Pour les médecins, le maximum est 75. Plaçons les 75 anglophones dans les 80 hispanophones, ceux-ci dans les 85 francophones, puis dans les 90 germanophones ; 10 médecins restent hors de tous les groupes. Les totaux sont identiques au cas du minimum 30, mais 75 parlent maintenant toutes les langues. Ces quatre totaux ne déterminent donc pas un effectif exact entre 30 et 75.

Si minimum et maximum coïncident, l’effectif est déterminé. Un groupe vide impose zéro membre commun ; si tous les groupes sont U, l’effectif vaut N. Une taille négative ou aᵢ>N n’est pas un cas difficile : c’est une donnée impossible.

Calculer et expliquer

6. Autre classe : dénombrements exacts avec deux ensembles

Pour N éléments, on connaît a=|A|, b=|B| et i=|A∩B|. La somme a+b compte les membres communs deux fois : on soustrait une copie. Contrairement au minimum garanti, l’intersection est connue.

|A∪B| = a+b−i
seulement A = a−i; seulement B = b−i
exactement un = a+b−2i
aucun = N−a−b+i

Sur 30 élèves, 18 font du sport, 16 de la musique et 7 les deux. Combien pratiquent au moins une activité, une seule, ou aucune ?

Les données sont compatibles si et seulement si max(0,a+b−N)≤i≤min(a,b). Cela revient à demander que les effectifs des quatre régions soient non négatifs.

Calculer et expliquer

7. Problèmes inverses : retrouver l’intersection

Si z éléments n’appartiennent à aucun des deux ensembles, l’union vaut N−z. À partir de N−z=a+b−i, on isole i sans inventer de nouvelle règle :

i = a+b−N+z

Sur 40 personnes, 25 lisent la revue A, 22 la revue B et 5 aucune des deux. Combien lisent les deux ?

Vérifiez toujours 0≤i≤min(a,b). Par exemple N=20, a=8, b=7, z=0 donne i=−5 : données incompatibles, car les groupes ne peuvent couvrir les 20 personnes. On ne remplace pas −5 par zéro ; on signale l’incohérence.

Calculer et expliquer

8. Trois ensembles : union, exactement un, exactement deux

Notons a=|A|, b=|B|, c=|C|, p=|A∩B|, q=|A∩C|, r=|B∩C| et t=|A∩B∩C|. Les intersections par paires incluent t : p ne signifie pas « A et B sans C ». Posons S₁=a+b+c et S₂=p+q+r.

|A∪B∪C| = S₁−S₂+t
aucun = N−S₁+S₂−t
exactement un = S₁−2S₂+3t
exactement deux = S₂−3t
au moins deux = S₂−2t

Dans la première formule, un membre des trois groupes est compté 3−3+1=1 fois. Les effectifs « seulement A », « seulement B », « seulement C » valent a−p−q+t, b−p−r+t, c−q−r+t. « Seulement AB », « seulement AC », « seulement BC » valent p−t, q−t, r−t. Tous ces nombres, l’intersection triple et la région extérieure doivent être non négatifs.

Exemple : N=100, a=60, b=50, c=40, p=30, q=25, r=20, t=15.

Calculer et expliquer

9. Pourcentages et contrôles : une même base

Les formules s’appliquent aussi aux proportions sur un même univers. Pour des pourcentages p₁,…,pₖ, le pourcentage commun minimal est max(0,p₁+⋯+pₖ−100(k−1))%. Les 75%, 80%, 85%, 90% des médecins garantissent au moins 30%. Un pourcentage exact devient un effectif par N×p/100, en vérifiant la compatibilité avec des entiers. Des pourcentages arrondis ne sont pas des données exactes.

Ne combinez pas 70% des élèves d’une école avec 60% des seuls élèves sportifs : les dénominateurs diffèrent. Il faut d’abord un même univers. Le laboratoire accepte des effectifs entiers, pas des pourcentages : convertissez-les avant la saisie.

10. Quelle formule choisir ?

• Seulement les tailles, et la question « au moins combien dans tous » ? Utilisez le minimum garanti.
• Deux ensembles avec tailles et intersection connues ? Utilisez l’inclusion–exclusion pour le dénombrement exact.
• L’effectif extérieur est connu ? Retrouvez l’union, puis l’intersection.
• Trois ensembles avec toutes les intersections nécessaires ? Partez de la triple et reconstruisez huit régions.

Identifiez l’univers ; traduisez « tous », « au moins un », « exactement un » ; contrôlez les données ; appliquez la formule ; vérifiez par les régions disjointes. Ne confondez pas garantie et effectif exact, et n’utilisez pas max(0,…) pour masquer une incompatibilité dans un calcul exact.

Dix exercices : cherchez avant d’ouvrir la solution

1. Sur 50 personnes, 35 sont dans A et 40 dans B. Minimum et maximum communs ?

2. Trois groupes ont 20, 18, 17 membres sur 30 personnes : combien sont garantis dans tous ?

3. Cinq compétences : 95, 94, 93, 92, 91 personnes sur 100. Minimum commun ?

4. Pour les 100 médecins, une répartition avec 75 quadrilingues contredit-elle le minimum 30 ?

5. N=25, |A|=16, |B|=14, |A∩B|=8. Trouvez union, exactement un, aucun.

6. N=60, |A|=35, |B|=30 ; 10 sont hors des deux. Trouvez l’intersection.

7. N=20, |A|=15, |B|=12, intersection=3. Données possibles ?

8. N=100 ; a=60, b=50, c=40 ; p=30, q=25, r=20, t=15. Combien appartiennent à au moins deux groupes ?

9. 90% et 85% d’une même population ont deux caractéristiques. Pourcentage minimal avec les deux ?

10. N=10 et tailles 10, 10, 7. Faut-il d’autres informations pour connaître l’effectif commun ?

Revoir éléments et opérations · Dix problèmes avancés sur les ensembles · Laboratoire : compter avec les ensembles

Pour approfondir

MIT · Mathematics for Computer Science, Cardinality Rules