Matematica Discreta I
Lezione del giorno 23 novembre 2007 Principio dei cassetti.
Si basa sul seguente risultato di insiemistica: se A,B sono insiemi finiti, con A=n, B=m, e se n>m , comunque data una funzione f: A → B, esistono sempre almeno 2 elementi diversi in A che hanno in B lo stesso corrispondente mediante f (tale risultato è ovvio perché sappiamo che, se n>m, la funzione f certamente non è iniettiva).
Se pensiamo ad A come un insieme di n “oggetti”, a B come un insieme di m “cassetti”, e alla funzione f come un modo di inserire ogni oggetto in un cassetto, il principio afferma semplicemente che se il numero di oggetti è maggiore di quello dei cassetti, certamente esistono almeno 2 oggetti diversi che saranno inseriti nello stesso cassetto.
Applicazioni del principio dei cassetti:
1) Il paradosso delle “strette di mano”.
Supponiamo che A sia un insieme di n persone che si riuniscono, e che ognuna stringa la mano ad alcune altre (al limite anche a nessuna o a tutte le altre). Si può allora concludere con certezza che esistono almeno 2 persone diverse che hanno stretto la mano allo stesso numero di persone.
Infatti se B è l’insieme dei numeri interi da 0 ad (n.-1), possiamo definire una funzione f: A → B, associando ad ogni persona il numero di strette di mano. Ovviamente però non può avvenire contemporaneamente che i valori 0 e (n-1) siano corrispondenti di elementi di A (se esiste una persona che ha stretto le mani a tutte le altre, non ne esiste una che non ha stretto le mani a nessuno). Quindi possiamo restringere il codominio B, sostituendolo con un insieme C ottenuto togliendo da B quel numero (0 oppure (n-1)) che non è corrispondente di nessun elemento di A.
Otteniamo così una funzione f: A → C, dove A=n, C=n-1<n: applicando il principio dei cassetti si ha la tesi.
2) Il problema del “bersaglio”.
Si supponga di colpire con 101 colpi (tutti a segno) un bersaglio quadrato con il lato di lunghezza 70 cm. Allora certamente esistono almeno 2 colpi sul bersaglio che distano meno di 10 cm.
Infatti basta suddividere il bersaglio in 100 quadrati, ognuno con il lato di lunghezza 7 cm., considerare l’insieme A dei 101 colpi e l’insieme B dei 100 quadrati, e definire poi la funzione f: A→ B che associa ad ogni colpo di A il quadrato in cui esso cade. Per il principio dei cassetti esistono almeno 2 colpi che cadono nello stesso quadrato, e geometricamente la loro distanza non è superiore alla lunghezza della diagonale che è uguale a
7 2cioè circa 9,9 cm.
Principio di inclusione-esclusione
Siano A,B insiemi finiti con A=n, B=m.
Se A,B non hanno elementi comuni, cioè se A∩B=, è ovvio che la cardinalità dell’unione AB coincide con la somma delle singole cardinalità dei 2 insiemi:
AB = n + m = A +B (è il cosiddetto principio della somma).
Se però A,B hanno qualche elemento in comune, tale formula non è più valida, perché, sommando
le singole cardinalità, gli elementi comuni sarebbero contati 2 volte nell’unione.
Quindi, in generale, vale invece la seguente formula:
AB = A +B- A∩B (è il cosiddetto principio di inclusione-esclusione per 2 insiemi) E’ ovvio che il principio della somma diventa un caso particolare del principio di inclusione- esclusione nel caso che sia A∩B=.
Tale principio di inclusione-esclusione si può estendere facilmente a più di 2 insiemi.
Se per esempio sono dati 3 insiemi finiti A,B,C, per calcolare la cardinalità della loro unione, usando le proprietà insiemistiche dell’unione e dell’intersezione e usando il principio di inclusione- esclusione nel caso di 2 insiemi, si ha:
ABC=A(BC)=A+BC-A∩(BC)=A+BC-(A∩B)(A∩C)=
A+B+C-B∩C- [A∩B+A∩C-A∩B∩C]=
=A+B+C-[A∩B+A∩C+B∩C]+A∩B∩C
e si ottiene quindi la formula del principio di inclusione-esclusione nel caso di 3 insiemi:
ABC = A+B+C-[A∩B+A∩C+B∩C]+A∩B∩C
Esiste una formula generale per il caso di n insiemi (che si dimostra con il principio di induzione, ma della quale omettiamo la dimostrazione): se sono dati n insiemi finiti A
1,A
2,…,A
n, la cardinalità della loro unione si calcola con la formula
A
1A
2…A
n=α
1- α
2+ α
3- α
4+……. ± α
ndove α
1è la somma delle cardinalità dei singoli insiemi; α
2è la somma delle cardinalità di tutte le possibili intersezioni a 2 a 2 degli insiemi; α
3è la somma delle cardinalità di tutte le possibili intersezioni a 3 a 3 degli insiemi; …….. …….; α
nè la cardinalità dell’intersezione di tutti gli insiemi: l’ultimo addendo é preceduto da un segno + se n è dispari, da un segno – se n è pari.
Esistono un uso positivo e un uso negativo del principio di inclusione-esclusione.
Uso positivo del principio di inclusione-esclusione.
Sia dato un insieme finito A ed n diverse condizioni P
1, P
2,….,P
nsugli elementi di A. Se vogliamo contare il numero degli elementi di A che soddisfano almeno una delle n proprietà, ciò equivale a costruire per ogni i=1,2,…,n l’insieme A
idegli elementi di A che soddisfano la proprietà P
i, e calcolare la cardinalità dell’unione A
1A
2…A
n, servendosi della formula del principio di inclusione-esclusione.
Esempio: Sia A l’insieme di tutte le parole di lunghezza 7 sull’alfabeto {a,b,c,d}. Risolviamo il problema di contare il numero della parole di A che soddisfano almeno una delle seguenti 3 proprietà: 1) la prima lettera della parola è c ; 2) la seconda lettera della parola è b ; 3) l’ultima lettera della parola è a.
A tale scopo dobbiamo costruire gli insiemi degli elementi di A che soddisfano singolarmente le 3 proprietà:
A
1= { xA / la prima lettera della parola x è c } A
2= { xA / la seconda lettera della parola x è b } A3 = { xA / l’ultima lettera della parola x è a }
e calcolare, con la formula del principio di inclusione-esclusione:
A
1A
2A
3=(A
1+A
2+A
3)-(A
1∩A
2+A
1∩A
3+A
2∩A
3)+A
1∩A
2∩A
3.
Servendoci del principio delle scelte multiple si ottengono i valori:
A
1=A
2=A
3=4
6, A
1∩A
2=A
1∩A
3=A
2∩A
3=4
5, A
1∩A
2∩A
3=4
4. Quindi la risposta al problema è:
A
1A
2A
3=3•4
6-3•4
5+3•4
4.
Uso negativo del principio di inclusione-esclusione.
Sia dato un insieme finito A ed n diverse condizioni P
1, P
2,….,P
nsugli elementi di A. Se vogliamo contare il numero degli elementi di A che non soddisfano nessuna delle n proprietà, ciò equivale a costruire per ogni i=1,2,…n l’insieme A
idegli elementi di A che soddisfano la proprietà P
i, e calcolare la cardinalità del complementare dell’unione A
1A
2…A
n, cioè calcolare la differenza A-A
1A
2…A
s, usando la formula del principio di inclusione-esclusione.
Daremo 2 esempi importanti di applicazione dell’uso negativo del principio di inclusione- esclusione: il problema della “segretaria distratta” e il calcolo della funzione di Eulero.
Il problema della “segretaria distratta”.
Supponiamo di avere n lettere (per n destinatari diversi) e le n buste corrispondenti, e di effettuare un “imbustamento” mettendo ogni lettera in una busta (lettere diverse in buste diverse).
Quesito: in quanti modi diversi si può effettuare un imbustamento totalmente errato, cioè in cui nessuna lettera va nella busta corretta corrispondente ?
Possiamo numerare la lettere e le buste da 1 ad n (lettera e busta corrispondente con lo stesso numero) e rappresentare ogni imbustamento come una funzione biunivoca
f : {1,2,…,n} → {1,2,…,n}
L’insieme A di tutti gli imbustamenti coincide con l’insieme di tutte le suddette funzioni biunivoche, di cardinalità n!.
Ogni imbustamento totalmente errato è una funzione fA che non soddisfi nessuna delle seguenti n proprietà:
f(1)=1; f(2)=2; … … ; f(n)=n
Possiamo allora usare la forma negativa del principio di inclusione-esclusione. Costruiamo quindi gli n insiemi:
A
1= { fA / f(1)=1 }; A
2= { fA / f(2)=2 } …. ….; A
n= { fA / f(n)=n } La risposta al quesito sarà: A-A
1A
2…A
n.
Per il principio di inclusione-esclusione si ha:
A
1A
2…A
n=α
1-α
2+α
3-α
4+…….±α
ndove α
1è la somma delle cardinalità dei singoli insiemi; α
2è la somma delle cardinalità di tutte le possibili intersezioni a 2 a 2 degli insiemi; α
3è la somma delle cardinalità di tutte le possibili intersezioni a 3 a 3 degli insiemi; …….. …….; α
nè la cardinalità dell’intersezione di tutti gli insiemi, preceduta da un segno + se n è dispari, da un segno – se n è pari.
Si ha A
1=A
2=……=A
n=(n-1)!, dunque α
1=(n-1)!n=n!.
Inoltre A
1∩A
2=(n-2)!, e ciò vale per cardinalità dell’intersezione di 2 qualunque degli insiemi.
Le possibili intersezioni a 2 a 2 corrispondono alle combinazioni semplici di n insiemi presi a 2 a 2, quindi sono in numero di
2 n
.
Si ha allora: α
2=(n-2)!
2
n
= (n-2)!
2!(nn!2)!=
2!n!
. Con ragionamenti analoghi si ha: α
3=
3!
n!
, α
4=
4!n!
, ... , α
n=
n!n!
=1 .
Dunque il numero di imbustamenti totalmente errati é:
A-A
1A
2…A
n=n!-(n!-
2!n!
