Matematica Discreta
Lezione del giorno 15 novembre 2011 Il problema della “segretaria distratta”.
Supponiamo di avere n lettere (per n destinatari diversi) e le n buste corrispondenti (con il nome del destinatario già stampato), 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 vada nella busta 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 soddisfa 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 }; etc …. ….; 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.
Calcoliamo la cardinalità di A
1: esso contiene le funzioni biunivoche f : {1,2,…,n} → {1,2,…,n}
tali che f(1)=1. Con il principio delle scelte multiple si ottiene cheA
1=(n-1)!.
Con ragionamenti analoghi si ottiene:
A
2=A
3=……=A
n=(n-1)!
dunque α
1è la somma di n addendi tutti uguali ad (n-1)!, ossia α
1= (n-1)!n = n!.
Ragionando in modo simile si ottiene che A
1∩A
2=(n-2)!, e ciò vale per la 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
. Dunque α
2è la
somma di
2
n
addendi tutti uguali ad (n-2)! .
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-X
1X
2…X
n=n!-(n!-
2!n!
+
3!n!
-
4!n!
+....±
n!
n!
) =
2!n!
-
3!n!
+
4!n!