Inclusione—esclusione, parte 3: con quattro è difficile anche fare i disegni

«Non vorrai fare i conti con quattro insiemi, adesso?».

«Sì, ma non è un problema fare i conti. È più complicato fare il disegno».

«Uh, davvero?».

«Davvero. Quante zone si possono avere intersecando quattro insiemi?».

«Compresa la zona esterna, 2⁴, cioè 16».

«Bene, se provi a disegnarle nella maniera che ti verrebbe naturale, non ce la fai a farle tutte».

«Davvero?».

«Prova».

«No, no, mi fido… Ma quindi come si fa il disegno?».

«Ci sono varie possibilità; quella proposta da Venn è la seguente:».

«Venn? Quello dei diagrammi di Eulero-Venn?».

«Lui. Del resto, questi disegnini che stiamo facendo sono proprio quei diagrammi».

«Ah, ecco. Comunque quel disegno è proprio brutto, eh».

«Sono d'accordo. Se ne vuoi uno più bello devi passare in tre dimensioni e intersecare quattro sfere».

«Brr, no, no, va bene così».

«Facciamo i conti, allora?».

«Facciamoli. Con 16 zone mi sa che si complicheranno un po'».

«Un pochino, ma non tanto se capiamo come funziona il meccanismo. Ripensiamo al sistema dei gettoni che abbiamo utilizzato con due e tre insiemi».

«Ok».

«Allora, quando mi dicono che gli elementi di A sono tot, io conto tante zone: riesci a elencarle tutte?».

«Credo di sì, sono tutte le combinazioni in cui compare A e non il suo complementare. Eccole qua:».

A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D.

«Bene, sono loro. Metterai dunque un gettone in ognuna di queste; quando dovrai tener conto di B metterai altri 8 gettoni in altrettante zone, tutte quelle che corrispondono a combinazioni in cui compare B e non il suo complementare».

«Stessa cosa per C e per D».

«Esatto. Ora prendo una combinazione a caso, per esempio questa: A∩B∩C∩D. Sai dirmi quanti gettoni avrà?».

«Uhm, direi due: uno che viene messo quando conto gli elementi di A, e uno per gli elementi di D».

«Benissimo. Due gettoni sono però troppi, ne dovremo poi togliere uno».

«Come abbiamo fatto l'altra volta».

«Sì, e come l'altra volta, però, dobbiamo stare attenti. Se sottraiamo gli elementi di A∩D, perché li abbiamo contati due volte, sottraiamo un gettone a tutte queste zone:».

A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D,
A∩B∩C∩D.

«Giusto. E allora come si fa?».

«E allora si ripresenta il problema di prima: se sottraiamo troppo, dobbiamo tornare ad aggiungere».

«Ah-ha! Ogni volta ci riconduciamo al caso precedente».

«Esatto. Prima sommiamo gli elementi dei quattro insiemi, poi sottraiamo gli elementi che stanno nelle intersezioni di due insiemi, poi riaggiungiamo gli elementi che stanno nelle intersezioni di tre insiemi, e infine sottraiamo gli elementi che stanno nell'intersezione di tutti e quattro».

«Ho capito, provo a scrivere la formula:».

|A∪B∪C∪D| =
  = |A| + |B| + |C| + |D|
   -|A∩B| - |A∩C| - |A∩D| - |B∩C| - |B∩D| - |C∩D|
  +|A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D|
  -|A∩B∩C∩D|.

«Benissimo. Ora hai anche capito come si generalizza a un numero qualsiasi di elementi: si ripete il procedimento sempre alla stessa maniera. Questa regola viene detta principio di inclusione-esclusione, e viene utilizzata per risolvere molti problemi».

«Per esempio?».

«Per esempio questo: sapendo che ci sono 168 numeri primi minori di 1000, quanti sono i numeri primi da ingegnere minori di 1000?».

«Cosa sono i numeri primi da ingegnere?».

«Sono numeri compositi ma non divisibili per 2, per 3 e per 5. Tipo 49».