Posti prenotati

[moebius]

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?

[Alex89]

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]

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} $

[moebius]

Ok ad entrambi, ma secondo me esiste un modo più facile per farlo

[RedII]

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.

[moebius]

Qualcuno ha provato a far vedere che i casi buoni sono esattamente quanti quelli cattivi?

[Esmeralda]

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

[moebius]

Questa era la soluzione di un rigo che volevo