Posti prenotati

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Posti prenotati

Messaggio da moebius » 26 set 2007, 18:08

Al cinema c'è la prima visione di un nuovo, attesissimo film!
Purtoppo la porta della sala rimane bloccata sino a pochi minuti prima dell'inizio e la maschera, per evitare problemi, decide di far entrare una persona alla volta.
Purtoppo il primo ad entrare, nella ressa precedente alle porte ha perduto il suo biglietto, quindi non sa dove adare a sedersi.
Decide quindi di occupare un posto a caso per non perdere tempo.
Gli altri che entrano, avendo paura che il film inizi a secondi, se trovano il loro posto libero si siedono al loro posto, altrimenti in un posto a caso.
La sala da 500 posti è tutta prenotata.
Il film sta per iniziare, entra la 500-esima persona e si dirige di corsa alla sua poltrona sperando di trovarla libera. Non ha il tempo di cercare altrimenti un altro posto.
Qual'è la probabilità che riesca ad occupare il suo posto?
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Alex89
Messaggi: 366
Iscritto il: 29 gen 2006, 16:57

Messaggio da Alex89 » 28 set 2007, 17:18

Abbiniamo i vari posti con gli spettatori per ordine di arrivo...

Prima di tutto, se il primo occupa il posto 500 la probabilità che il 500° trovi il suo posto libero sarà 0. Se il primo occupa il posto 499 il 499° spettatore andrà o nel posto 1 o nel posto 500 e la probabilità sarà 1/2.
Ora se il primo occupa il posto x tutti gli spettatori fino allo spettatore x vanno al loro posto; lo spettatore x può occupare o il posto del 1°, così la probabilità sarà 1, o il posto del 500°, e la probabilità sarà 0, oppure potrà occupare un posto a caso nei posti tra x+1 e 499, lasciando lo spettatore del posto che andrà a occupare nella sua stessa situazione. Ora facciamo un'induzione "al contrario": se per ogni valore tra x e 499 la probabilità è 1/2, allora anche per x-1 sarà 1/2. Infatti per quanto detto prima avremo che la probabilità P sarà pari a:
$ P=0+1+(499-x)*(1/2)=[499-(x-1)]*(1/2) $
Ora poichè per il caso x=499 P è uguale ad 1/2, per induzione per ogni x tra 2 e 499 la probabilità sarà pari a 1/2. Poichè per x=1 la probabilità è 1 e per x=500 la probabilità è 0, la probabilità generale (uguale alla somma di tutti i possibili valori di x tra 1 e 500) è:

$ P=(498*1/2+1+0)/500=250/500=1/2 $

P.s: sapreste un modo x scrivere meglio le frazioni?

albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K » 28 set 2007, 17:53

Questo giochino è carino (e simpaticamente formulato :) ) e piuttosto sorprendente, infatti l'ultimo tizio ha esattamente il 50% di possibilità di trovare il suo posto libero, nonostante il casino infernale causato dalla maschera...e lo stesso capiterebbe in un cinema con un milione di posti!

Il primo spettatore ha probabilità $ $ \frac{1}{n}$ $ di mettersi al posto giusto; negli altri casi si aprono le varie possibilità. La chiave della soluzione è osservare che se il primo spettatore si mette al posto del $ $k-$ $esimo spettatore, allora tutto andrà bene finchè non entra quest'ultimo; esso avrà probabilità $ $\frac{1}{n-k+1}$ $ di mettersi al proprio posto, se invece si mette al posto dello spettatore $ $j$ $ tutto andrà bene finchè non entra quest'altro, il quale a sua voltà si siederà al proprio posto con probabilità $ $\frac{1}{n-k-j+1}$ $ e così via.
Nel diagramma ad albero dobbiamo quindi considerare tutti i casi e viene fuori questa formula:

$ \displaystyle F = \frac{1}{n} \sum_{\delta = 0,1} \prod_{k=2}^{n-1}k^{-\delta} = \frac{1}{2} $

cioè, se indichiamo $ $ a_i = \frac{1}{i}, i=1,\dots n-1$ $ allora
$ \displaystyle F = \frac{1}{n}\overbrace{\left(a_2a_3\dots a_{n-1} + a_2a_4\dots a_{n-1} + \dots a_3 + a_2 + 1\right)}^{\mbox{tutti i possibili prodotti}} = $
$ \displaystyle \frac{1}{n}(1 + a_{n-1})(1 + a_{n-2})\cdots (1 + a_2) = \frac{1}{n} \cdot \frac{n}{n-1} \cdot \frac{n-1}{n-2} \cdots \frac{4}{3} \cdot \frac{3}{2} = \frac{1}{2} $
[tex] wHy \matchal{ALBERT}_K ? [/tex]

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 29 set 2007, 01:20

Ok ad entrambi, ma secondo me esiste un modo più facile per farlo :D
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Avatar utente
RedII
Messaggi: 32
Iscritto il: 08 mag 2006, 16:45

Messaggio da RedII » 29 set 2007, 11:46

Sbaglio o questo problema è quasi identico a uno di quelli che abbiamo fatto al Senior? XD

Comunque, vediamo se mi ricordo la soluzione bella...
Uno dei concetti chiave era che dopo che lo spettatore n è andato a sedersi, il posto n sarà sicuramente occupato.
Proviamo a partire dall'inizio: lo spettatore 1 va a sedersi in un posto a caso. Poi arriva lo spettatore 2 che, nel caso il suo posto sia occupato, va in un posto libero a caso, altrimenti si siede sul suo. Consideriamo ora i due casi: se trova il posto occupato e va a sedersi in un altro posto, possiamo dire con certezza che il posto di 2 è occupato, e tra tutti gli altri posti ci sarà un posto qualsiasi occupato, e il posto di ciascun n ha la stessa probabilità di essere quel posto (1/499). Nel caso trovi il posto libero e vada lì a sedersi, cosa possiamo dire? La stessa identica cosa: il posto 2 è occupato e uno qualsiasi degli altri anche, con uguale probabilità (1/499). Quando arriverà 3 e si siederà, in uno dei diversi due modi, potremo sempre dire che i posti 2, 3 sono occupati, ed è occupato anche uno degli altri posti con uguale probabilità (1/498). Essendo questa situazione sempre identica, possiamo dire che quando arriva n, tutti i posti 2, 3, ... , n saranno occupati, uno dei restanti sarà occupato e ciascuno di essi ha la probabilità di $ \frac1{501-n} $ di esserlo. Ne consegue allora che possiamo considerare direttamente la situazione dopo che si siede lo spettatore 499: i posti da 2 a 499 saranno occupati, uno dei restanti (1 e 500) sarà occupato e ciascuno di essi avrà una probabilità di 1/2 di esserlo. A questo punto arriva 500 che ha esattamente 1/2 di probabilità di trovare il suo posto libero.

Scusatemi se è contorta. :P
Membro dell'EATO.

Ci sono 10 tipi di persone: c'è chi sa leggere il codice binario e chi no.
I nemici dell'italiano sono miei nemici.

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 02 ott 2007, 10:41

Qualcuno ha provato a far vedere che i casi buoni sono esattamente quanti quelli cattivi? :P
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Esmeralda
Messaggi: 15
Iscritto il: 05 set 2007, 21:44

Messaggio da Esmeralda » 02 ott 2007, 11:22

Se una persona ruba il posto alla prima allora tutto si aggiusta.
Quindi se il 500 esimo non ha trovato posto (perchè un tale che chiamo Febo gli ha rubato la sedia) nessuno ha rubato il posto alla prima.
Ora facciamo che Febo ruba il posto alla prima persona e non alla 500 esima e ottengo la corrispondenza biunivoca e la tesi :wink:
Membro dell'associazione "Non uno di meno", per lo sterminio massiccio dei nani e affini.

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 02 ott 2007, 11:34

Questa era la soluzione di un rigo che volevo :D
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Rispondi