Insiemi: il minimo garantito e le formule per contare

Quante persone devono necessariamente avere tutte le caratteristiche richieste? Non sempre i dati permettono di sapere il numero esatto: spesso permettono di trovare il minimo garantito. Partiamo da un indovinello, ricaviamo una formula per un numero qualsiasi di insiemi e distinguiamo questa domanda dai problemi di conteggio esatto.

Laboratorio: contare con gli insiemi · Laboratorio visuale di Venn

1. L’indovinello dei 100 medici

In un ospedale lavorano 100 medici: 75 parlano inglese, 80 spagnolo, 85 francese e 90 tedesco. Qual è il numero minimo garantito di medici che parlano tutte e quattro le lingue? Gli stessi medici possono comparire in più gruppi.

La risposta non è «sono esattamente 30»: è «sono almeno 30, e 30 è possibile».

Calcola e spiega

2. Contare le mancanze invece delle presenze

Fissiamo un universo U con N elementi e k sottoinsiemi A₁,…,Aₖ. Scriviamo aᵢ=|Aᵢ|, cioè il numero di elementi del gruppo i. La somma S=a₁+⋯+aₖ conta appartenenze, non persone distinte: può superare N. Chi appartiene a tutti i gruppi non ha alcuna mancanza.

Nel gruppo i mancano N−aᵢ elementi. La somma delle mancanze è M=(N−a₁)+⋯+(N−aₖ)=kN−S. Una persona può mancare da più gruppi; quindi il numero di persone con almeno una mancanza è al massimo M, e comunque non supera N. Il complementare dell’intersezione è l’unione dei complementari: U∖(A₁∩⋯∩Aₖ)=(U∖A₁)∪⋯∪(U∖Aₖ).

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

3. La formula generale e la dimostrazione per conteggio

Indichiamo con x=|A₁∩⋯∩Aₖ| il numero comune a tutti. Le x persone comuni producono kx appartenenze. Ciascuna delle altre N−x persone appartiene al massimo a k−1 gruppi. Perciò:

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

Poiché x≥0, otteniamo la formula cercata, valida quando sono note soltanto N e le dimensioni dei gruppi, con 0≤aᵢ≤N:

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

Con due gruppi sottrai N; con tre 2N; con quattro 3N. Per i medici: max(0,75+80+85+90−3×100)=max(0,330−300)=30. Il massimo con 0 evita un risultato negativo: «minimo zero» significa che non è garantita una persona comune, non che l’intersezione sia certamente vuota.

4. Perché il limite si può raggiungere

Una disuguaglianza da sola non dimostra che un minimo sia raggiungibile. Se M≤N, distribuiamo le N−aᵢ mancanze di ciascun gruppo su persone tutte diverse. Otteniamo esattamente M persone con una mancanza e N−M persone senza mancanze: il minimo della formula.

Se M≥N, immaginiamo le N persone disposte in cerchio. Assegniamo le mancanze del primo gruppo a persone consecutive; continuiamo con quelle del secondo da dove eravamo arrivati, poi con le successive, ricominciando il giro quando serve. Ogni blocco ha al massimo N persone, quindi nessuna persona manca due volte dallo stesso gruppo. Avendo assegnato almeno N mancanze consecutive, ogni persona ne ha almeno una: l’intersezione di tutti i gruppi è vuota. La formula dà proprio zero.

Questa costruzione rispetta ogni dimensione iniziale. Vale senza altri vincoli: se fossero imposte anche particolari intersezioni, bisognerebbe verificarle a parte. Il laboratorio costruisce e controlla una configurazione anche nel caso M≥N.

Calcola e spiega

5. Il massimo e la differenza fra certo e possibile

L’intersezione non può contenere più elementi del gruppo più piccolo. Il massimo si raggiunge mettendo gli insiemi uno dentro l’altro, dal più piccolo al più grande.

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

Nei medici il massimo è 75. Possiamo mettere i 75 anglofoni dentro gli 80 ispanofoni, questi dentro gli 85 francofoni e questi dentro i 90 germanofoni; 10 medici restano fuori da tutti. I dati sono gli stessi del caso con minimo 30, ma ora 75 persone parlano tutte le lingue. Dunque dai soli quattro totali non possiamo scegliere un numero esatto tra 30 e 75.

Se minimo e massimo coincidono, invece, il numero è determinato. Se un gruppo è vuoto, il numero comune è zero; se tutti i gruppi coincidono con U, è N. Un dato aᵢ>N o negativo non è un caso difficile: è un dato impossibile.

Calcola e spiega

6. Un’altra classe: conteggi esatti con due insiemi

Su N elementi conosciamo a=|A|, b=|B| e i=|A∩B|. La somma a+b conta due volte i membri comuni: sottraiamo una copia. A differenza del minimo garantito, qui conosciamo l’intersezione.

|A∪B| = a+b−i
solo A = a−i; solo B = b−i
esattamente uno = a+b−2i
nessuno = N−a−b+i

In una classe di 30 studenti, 18 fanno sport, 16 musica e 7 entrambe le attività. Quanti fanno almeno un’attività, una sola e nessuna?

I dati sono compatibili se e solo se max(0,a+b−N)≤i≤min(a,b). Questo equivale a chiedere che tutte le quattro regioni abbiano conteggi non negativi.

Calcola e spiega

7. Problemi inversi: trovare chi appartiene a entrambi

Se conosciamo il numero z di elementi che non appartengono a nessuno dei due insiemi, l’unione è N−z. Dalla relazione N−z=a+b−i isoliamo i, senza inventare una nuova regola:

i = a+b−N+z

Su 40 persone, 25 leggono una rivista A, 22 una rivista B e 5 nessuna delle due. Quante le leggono entrambe?

Controlla sempre 0≤i≤min(a,b). Per esempio N=20, a=8, b=7, z=0 darebbe i=−5: i dati sono incompatibili, perché i due gruppi non possono coprire tutte le 20 persone. Non si sostituisce −5 con zero: si segnala l’errore nei dati.

Calcola e spiega

8. Tre insiemi: unione, solo uno, esattamente due

Scriviamo a=|A|, b=|B|, c=|C|, p=|A∩B|, q=|A∩C|, r=|B∩C| e t=|A∩B∩C|. Le intersezioni a coppie comprendono anche t: p non significa «A e B ma non C». Poniamo S₁=a+b+c e S₂=p+q+r.

|A∪B∪C| = S₁−S₂+t
nessuno = N−S₁+S₂−t
esattamente uno = S₁−2S₂+3t
esattamente due = S₂−3t
almeno due = S₂−2t

Nella prima formula un elemento comune ai tre gruppi viene contato 3−3+1=1 volta. Le regioni «solo A», «solo B», «solo C» sono rispettivamente a−p−q+t, b−p−r+t, c−q−r+t. Le regioni «solo AB», «solo AC», «solo BC» valgono p−t, q−t, r−t. Tutte queste quantità, la tripla e la regione esterna devono essere non negative.

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

Calcola e spiega

9. Percentuali e controlli: la base deve essere la stessa

Le formule valgono anche per proporzioni riferite allo stesso universo. Se le percentuali sono p₁,…,pₖ, la percentuale minima comune è max(0,p₁+⋯+pₖ−100(k−1))%. Il 75%, 80%, 85%, 90% dei medici garantisce almeno il 30%. Per ottenere un conteggio da una percentuale esatta si calcola N×p/100; con conteggi interi si controlla la compatibilità. Percentuali arrotondate non sono dati esatti.

Non sommare, invece, il 70% degli studenti di una scuola con il 60% dei soli studenti sportivi: hanno denominatori diversi. Prima rendi omogenei gli universi. Il laboratorio accetta conteggi interi, non percentuali: trasformale in conteggi prima dell’inserimento.

10. Quale formula scegliere?

• Solo dimensioni dei gruppi, domanda «almeno quanti in tutti»? Usa il minimo garantito.
• Dimensioni e intersezione note per due insiemi? Usa inclusione–esclusione per il conteggio esatto.
• Noto chi è fuori da entrambi? Ricava prima l’unione e poi l’intersezione.
• Tre insiemi con tutte le intersezioni necessarie? Parti dalla tripla e ricostruisci le otto regioni.

In ogni caso: identifica l’universo; traduci «tutti», «almeno uno», «esattamente uno»; controlla i dati; applica la formula; verifica ricostruendo regioni disgiunte. Non sostituire una garanzia con un dato esatto e non applicare max(0,…) per nascondere un’incompatibilità nei problemi esatti.

Dieci esercizi: prova prima di aprire la soluzione

1. Su 50 persone, 35 appartengono ad A e 40 a B. Minimo e massimo comuni?

2. Tre gruppi hanno 20, 18, 17 membri su 30 persone: quanti sono garantiti in tutti?

3. Cinque competenze: 95, 94, 93, 92, 91 persone su 100. Minimo comune?

4. Nei 100 medici, una distribuzione con 75 quadrilingui contraddice il minimo 30?

5. N=25, |A|=16, |B|=14, |A∩B|=8. Trova unione, esattamente uno, nessuno.

6. N=60, |A|=35, |B|=30; 10 sono fuori da entrambi. Trova l’intersezione.

7. N=20, |A|=15, |B|=12, intersezione=3. Dati possibili?

8. N=100; a=60, b=50, c=40; p=30, q=25, r=20, t=15. Quanti sono in almeno due gruppi?

9. Il 90% e l’85% della stessa popolazione hanno due requisiti. Percentuale minima con entrambi?

10. N=10 e dimensioni 10, 10, 7. Servono altre informazioni per sapere quanti sono in tutti?

Ripassa elementi e operazioni · Dieci problemi avanzati sugli insiemi · Laboratorio: contare con gli insiemi

Fonti per approfondire

MIT · Mathematics for Computer Science, Cardinality Rules