Newsgroup: it.hobby.enigmi
Titolo: Segretaria Sbadata

Una segretaria ha il compito di convocare tutti e 24 i lavoratori di una
azienda. Inizia a scrivere le lettere tutte personalizzate tra loro. Poi, in
un secondo momento, scrive gli indirizzi delle buste. Stanca va a prendersi
un caffč e una pasta. Ad un certo punto si accorge che č tardissimo e per
far presto mette le lettere a caso nelle buste, senza badare che
l'intestazione della lettera si riferisca all'indirizzo scritto nella busta.
Sapreste dirmi la probabilitą che almeno una lettera si trovi nella  busta
appropriata? E quanto ha speso la segretaria al bar?
fatemi sapere ;)
-lorino

 
 E' un famoso problema proposto da Niclaus Bernouilli (1687-1759).
 Eulero si interesso' del problema che chiamo' "Quaestio curiosa ex
 doctrina combinationis"
 
 In generale si tratta di determinare il numero di permutazioni di n
 elementi in cui nessun elemento occupa il suo posto naturale. Gli
 anglosassoni chiamano queste disposizioni DERANGEMENTS. 
 
 In generale se n= numero di lettere, nei testi troviamo:
 
 n!(1/2!-1/3!+1/4!-1/5!+......1/n!)
 non semplice da trovare, oppure
[n!/e]
Le parentesi quadre indicano l'arrotondamento all'intero piu' vicino.
e = base dei log. naturali.
E se non avessimo a disposizione queste formule ? 
 
 Ho trovato un metodo ricorsivo molto semplice.
 Consideriamo per ogni n i due casi:
 x = il numero di modi in cui nessuna lettera e' nella propria busta.
 y = il numero di modi in cui esattamente una sola lettera e' nella
 propria busta.
 
 Conoscendo questi 2 valori, allora sara' facile ricavare gli stessi 2
 valori per n+1.
 Ad es. per n=4 si ha x=9, y=8 
 
 Per n=5 posso ottenere x con questo ragionamento. 
 La quinta lettera puo' essere scambiata con una delle  4 buste
 precedenti in 9 modi 4*9=36.
 Oppure puo' essere scambiata con il contenuto della busta esatta negli
8
 casi precedenti.
 totale 36+8 = 44 casi x per n=5
 
 Per n=5 posso ottenere y con questo ragionamento.
 Una fra 5 buste ha la lettera giusta, le altre quattro buste devono
 contenere una lettera sbagliata, ma questo si puo' fare in 9 modi,
 (l'abbiamo appena visto, e' x per n=4) 
 totale 5*9 = 45.
 
 A questo punto abbiamo il modo di riempire una semplice tabella:
 
 n= numero di lettere
 x= casi in cui nessuna busta contiene la lettera giusta
 y= casi in cui una sola busta contiene la lettera giusta
 
 
 n       x       y
 ------------------
 2       1       0
 3       2       3
 4       9       8
 5      44      45
 6     256     264
 7    1854    1855
 
 
 Proseguendo per n=8 come abbiamo visto basta fare:
 x = 7*1854+1855 = 14833
 y = 8*1854      = 14832.......
 
 Arrivando alle tue 24 lettere (potevi scegliere una azienda con meno
 dipendenti)   
 troviamo per x il valore di 228250311305338670497693.
La prob. cercata e' (24!-x)/24!
ciao :)dario

 -lorino
Vediamo. Per mandare le buste la segretaria ha bisogno dei numeri civici di tutti
gli impiegati. La brava donna li aveva scritti su dei fogliettini. Dopo la pausa
si accorge che manca il numero di uno dei lavoratori, che curiosamente e' il
discendente di uno dei maggiori geni matematici di tutti i tempi, del quale porta
il cognome. Per cercarlo perde tempo e quindi irritata compie l'insano gesto in
oggetto. Il fatto e' che il fogliettino durante l'assenza della segretaria e'
svolazzato fin sulla sedia di un suo collega, che ora se ne sta ignaro seduto alla
sua scrivania. Secondo me quell'impiegato approssima con molta precisione la
probabilita' richiesta.
Ciao, Silv;o)

 probabilita' richiesta.
Ho calcolato la probabilita' che NESSUNA busta contenga la lettera giusta :(
L'ultima parte del contro-indovinello andrebbe corretta di conseguenza, ma intanto
Dario ha reso quasi inutile la modifica, grrrrrrrr.....
Ciao, Silv;o)


Purtroppo quando le risposte ti sembrano troppo semplici spesso sono
sbagliate, ma non me ne viene una migliore.
Una su 24?

Una segretaria ha il compito di convocare tutti gli n  lavoratori di una
azienda. Inizia a scrivere le lettere tutte personalizzate tra loro.
Poi, in
un secondo momento, scrive gli indirizzi delle buste. Stanca va a
prendersi
un caffč e una pasta. Ad un certo punto si accorge che č tardissimo e
per
far presto mette le lettere a caso nelle buste, senza badare che
l'intestazione della lettera si riferisca all'indirizzo scritto nella
busta.
Sapreste dirmi la probabilitą che k lettere si trovino nella  busta
appropriata? 
:)dario

Dario Uri dice

Sappiamo contare gli x modi possibili di non azzeccare neanche una lettera su t,
lo hai spiegato bene nella tua risposta.
Una forma comoda da usare per la tua relazione ricorsiva e' la seguente:
x(t)=(t-1)*(x(t-1)+x(t-2)) con x(0)=1 e x(1)=0 (zero su zero lo fai sicuramente ma
se hai una sola busta non riesci proprio a sbagliare :)
Facilmente si ricava la successione 1,0,1,2,9,44,256,...
Ora, se k lettere sono al posto giusto, le altre n-k sono fuori posto. Le k
lettere le posso mettere in C(n,k) modi, ognuno dei quali puo' essere associato
agli a(n-k) modi di sbagliare le altre. Quindi la probabilita' richiesta e' uguale
al numero dei modi di azzeccare k lettere per i modi di sbagliarne n-k fratto i
modi di mettere le buste a caso.
p(n,k)=C(n,k)*x(n-k)/n!=x(n-k)/(k!*(n-k)!)
Se la differenza tra n e k e' abbastanza marcata, diciamo da 6 o 7 in poi,
x(n-k)~=1/e*(n-k)!, per cui la probabilita' diventa
p(n,k)=1/(e*k!)
che e' una formula pratica per k piccoli ed n grandi (il problema dal quale siamo
partiti, per esempio aveva n=24 e k=0, per cui la probabilita' era praticamente
1/e)
Ciao, Silv:o)

Caro Lorino, ecco le risposte.
Quanto ha speso al bar? Nulla, perchè è troppo bella ed ha trovato
un giovanotto che le ha offerto tutto.
Probabilità di corrispondenza tra indirizzo in busta ed indirizzo
in lettera : praticamente nulla se la segretaria utilizza Word
con la testa che si ritrova

 ed il numero medio di lettere che arriveranno al giusto
destinatario?
1

 1
OK.
Pero' dovresti dire come ci sei arrivato.
Perche' ci si puo' arrivare attraverso la distribuzione di probabilita'
E(X)=Sum(x*P(x)) dove i termini P(x) sonno abbastanza complessi (sono quelli
trovati nei post precedenti), oppure, e questo e' meno intuitivo ma molto piu'
furbo, utilizzando la linearità della media (la media di una somma e' la somma
delle medie).
Se X_i=1 se la busta i e' al posto giusto, zero altrimenti, allora
X=X_1+X_2+..+X_n e' il numero di buste che stanno al loro posto.
Le probabilita' che una busta qualsiasi stia al suo posto dipendono in generale
dalle altre buste (variabili aleatorie NON indipendenti), pero' MEDIAMENTE, ogni
busta capita al proprio posto una volta su n (e' facilmente vero per la prima
busta, quindi lo è anche per le successive, per simmetria).
E qui entra in gioco l'additivita' della media.
E(X)=E(X_1)+E(X_2)+..+E(X_n)=n*E(X_1)=n*1/n=1
indipendentemente da n!
Questo strumento si rivela molto potente in problemi altrimente difficilmente
trattabili.
Personalmente feci questa scoperta (dell'acqua calda...) affrontando un problema
con le carte: Quante sono mediamente le coppie dello stesso colore che si
ottengono mischiando un mazzo da 52 e girando le carte due alla volta? Dopo una
serie di tentativi ed utilizzando formuloni di calcolo combinatorio, catene di
Markov ed altre tecniche, arrivammo al risultato giusto. A posteriori, vista la
semplicita' di quanto ottenuto, si capi' che doveva per forza scaturire da un
ragionamento molto semplice, come questo delle lettere.
Chi non ha seguito a suo tempo il tema puo' provare a dare la soluzione.
C'e' molto materiale in rete sull'argomento.
Per esempio, si puo' vedere il sito - da bookmarcare assolutamente - di Torsten
Sillke
http://www.mathematik.uni-bielefeld.de/~sillke/NEWS/expectation-linear
Ciao, Silv:o)