Alle poste

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Alle poste

Messaggio da Mist »

Un postino imbusta a caso $n$ lettere in $n$ buste. Su ogni busta è già segnato il destinatario e ovviamente anche ad ogni lettera corrisponde un solo destinatario possibile.
Qual'è la probabilità che il postino metta ogni lettera nella busta sbagliata ? Se il numero di lettere e buste tende ad infinito, a quanto tende la probabilità ?
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Alle poste

Messaggio da jordan »

Stai leggendo enumerative combinatorics?
The only goal of science is the honor of the human spirit.
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Alle poste

Messaggio da Mist »

u.u No, solo ieri sera stavo cercando di prendere sonno e mi sono ricordato di quando in seconda liceo guardai un video di Gobbino in cui veniva posto questo problema, l'ho risolto, è uscita una cosa carina e mi sono addormentato.

Ne approfitto per chiedere ai novizi di farsi avanti perchè è un problema davvero carino ed istruttivo :)
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Alle poste

Messaggio da jordan »

Mist ha scritto:Ne approfitto per chiedere ai novizi di farsi avanti perchè è un problema davvero carino ed istruttivo :)
Si', anche abbastanza facile, data la definizione di qualche "vocale" ;)
The only goal of science is the honor of the human spirit.
toti96
Messaggi: 53
Iscritto il: 02 nov 2012, 20:17

Re: Alle poste

Messaggio da toti96 »

mi sembra troppo semplice e non capisco nulla di combinatoria ma non dovrebbe essere $ \frac {(n-1)!}{n!} $ cioè praticamente $ \frac {1}{n} $ ??quindi con $ n $ tendente a infinito la probabilità dovrebbe tendere a zero..
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Alle poste

Messaggio da jordan »

toti96 ha scritto:dovrebbe essere $ \frac {(n-1)!}{n!} $ ..
Perchè?
The only goal of science is the honor of the human spirit.
toti96
Messaggi: 53
Iscritto il: 02 nov 2012, 20:17

Re: Alle poste

Messaggio da toti96 »

per la prima lettera che imbuca ha $ \frac{n-1}{n} $ di sbagliare,per la seconda lettera ha $ \frac{n-2}{n-1} $ e così via fino all'ultima il che ci porta a $ \frac {(n-1)!}{n!} $...sicuramente sto facendo qualche errore quindi illuminatemi su dove sbaglio XD
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: Alle poste

Messaggio da Troleito br00tal »

Ma se nella prima buca mette la seconda lettera è vera quella cosa che hai scritto?
toti96
Messaggi: 53
Iscritto il: 02 nov 2012, 20:17

Re: Alle poste

Messaggio da toti96 »

giusto ho fatto un errore più che cretino ed ho considerato solo una parte delle combinazioni credo
Gi.
Messaggi: 154
Iscritto il: 18 dic 2012, 16:45

Re: Alle poste

Messaggio da Gi. »

Ci provo:
Testo nascosto:
Provo prima un caso semplice: n=3

Probabilità=$ \frac {Casi-favorevoli}{Casi-possibili} $

I casi possibili sono ovviamente 3!=6 (laprima lettera la imbusto in tre modi, la seconda in due e la terza in uno).
I casi favorevoli sono più difficili da contare; essi sono ovviamente i casi possibili a cui sottraggo tutti i casi in cui la busta viene imbustata correttamente, per calcolare questi ultimi possiamo ricorrere aduna rappresentazione di tipo insiemistico: chiamiamo P(A), P(B) e P(C) le possibilità di imbucare le tre lettere correttamente, se io calcolassi |P(A)| + |P(B)| + |P(C)| non avrei calcolato comunque il numero effettivo di modi di imbucare le lettere correttamente, in quanto avrei calcolato più volte le varie intersezioni, è necessario dunque "levare" da |P(A)| + |P(B)| + |P(C)| le varie intersezioni a due a due dei tre insiemi, per cui:

|P(A)| + |P(B)| + |P(C)| - (|P(A)∩P(B)|+|P(A)∩P(C)|+|P(B)∩P(C)|)

Facendo ciò, però, ho tolto l' intersezione dei tre insiemi, che vado dunque a riaggiungere:

|P(A)| + |P(B)| + |P(C)| - (|P(A)∩P(B)|+|P(A)∩P(C)|+|P(B)∩P(C)|) +|P(A)∩P(B)∩P(C)|

Le possibilità di imbustare correttamente una qualsiasi delle tre lettere è 2!, infatti se imbusto correttamente la prima poi ho altre due possibilità per la seconda ed una per la terza.
La possibilità di imbustare correttamente due lettere è una sola, infatti imbustare le prime due correttamente la terza è obbligata.
Infine, la possibilità di imbustare correttamente tutte e tre le lettere è una sola.

Per cui: 6-3+1= 4 Probabilità=$ 1-\frac {2}{3}=\frac {1}{3} $


Spero di non aver preso un granchio.
Per n che tende ad infinito o per un n generico non riesco ad ampliare il ragionamento, se mi date un hint tento.
Ultima modifica di Gi. il 21 dic 2012, 15:29, modificato 4 volte in totale.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Alle poste

Messaggio da jordan »

Gi. ha scritto:..se mi date un hint tento.
Le vocali non sono molte ;)
The only goal of science is the honor of the human spirit.
Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Alle poste

Messaggio da Mist »

Prova prima a generalizzare in una formula per un generico $n$ le cose che hai scritto per quel caso particolare !
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Gi.
Messaggi: 154
Iscritto il: 18 dic 2012, 16:45

Re: Alle poste

Messaggio da Gi. »

Allora: Chiaramente per prima cosa ho la somma di tutte le cardinalità degli insiemi fino a N:

|P(A)|+|P(B)|+|P(C)|+|P(D)|+...+|P(N)|

come prima tolgo le intersezioni a due a due, scrivendo gli n insiemi in ordine P(A), P(B), P(C),...,P(N) si vede che il primo insieme ha n-1 intersezioni a due a due con gli altri, il secondo ne ha n-2, il terzo n-3,..., il penultimo una sola, ossia $ \frac{n!}{2!(n-2)!} $; adesso riaggiungo le intersezioni a tre a tre che ho tolto, che dovrebbero essere $ \frac{n!}{3!(n-3)!} $,..., infine aggiungo, se n è dipari, o tolgo, se n è pari, l' intersezione di tutti gli insiemi.
Quindi:

(|P(A)|+|P(B)|+|P(C)|+|P(D)|+...+|P(N)|) - [|P(N)| -[(P(A)∩P(B))+(P(A)∩P(B)+...+(P(N-1)∩P(N))}+...+ $ (-1)^{n+1} $*[|P(A)∩P(B)∩P(C)∩...∩P(N)]

Però, sempre che sia giusto, non riesco proprio a capire come possa utilizzarla per calcolare i casi favorevoli per un n generico (a meno che io non mi debba limitare a dire che le probabilità sono: $ \frac{n!-("MOSTRO-DI-SOPRA")}{n!} $) :oops:
Ultima modifica di Gi. il 18 dic 2012, 21:27, modificato 3 volte in totale.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: Alle poste

Messaggio da jordan »

Scrivi in forma di sommatoria la roba sopra. Poi ricordati com'è definita $e^x$..
The only goal of science is the honor of the human spirit.
Gi.
Messaggi: 154
Iscritto il: 18 dic 2012, 16:45

Re: Alle poste

Messaggio da Gi. »

Direi, e spero di dire bene:

Indico con $ P_{i,j,k,...,n} $ gli insiemi che ho precedentemente indicato con P(A), P(B),P(C),...,P(N),

$ \displaystyle \sum_{i=1}^{N}{P_{i}} -\displaystyle \sum_{1\le i\le j} {(P_{i}\cap P_{j})} +\displaystyle \sum_{1\le i\le j\le k} {(P_{i}\cap P_{j}\cap P_{k})} -...+(-1)^{n+1}\displaystyle \sum_{1\le i\le j\le k\le ...\le n} {(P_{i}\cap P_{j}\cap P_{k}\cap ...\cap P_{n})} $

Per ogni argomento della sommatoria sottintendo che prendo in considerazione la cardinalità degli insiemi.

Detto A,B,C,D,F,...,N i vari termini della somma algebrica qui sopra, stavo pensando che posso scrivere la probabilità come:

$ 1 -(\frac {A}{n!} - \frac {B}{n!} +\frac {C}{n!}-...+\frac {(-1)^{n+1}*N}{n!}) $

Quindi per n che tende ad infinito il denominatore di ogni frazione tende ad infinito e le frazioni a 0, quindi tutta l' espressione dovrebbe tendere ad 1.
Giusto :?:
Rispondi