[Prawdopodobieństwo] Babcia w samolocie

[allure]

Sytuacja wygląda następująco: mamy samolot, w którym jest n miejsc i mamy n pasażerów.
Każdy z pasażerów ma bilet, na którym jest wydrukowane konkretne miejsce (miejsca nie mogą się powtarzać). Pierwszym pasażerem, który wsiada do samolotu jest niedowidząca babcia, która nie widzie swojego miejsca na bilecie, dlatego też siada na losowo wybranym przez siebie miejscu, następny pasażer wsiada patrzy na bilet i jeżeli jego miejsce jest wolne to siada na nim, jeżeli jest zajęte to w losowo wybiera wolne miejsce, wchodzi następny pasażer i działa na podobnych zasadach - jeżeli jest jego wolne miejsce to siada na nim, jeżeli nie, to losowo wybiera i tak robi cała reszta pasażerów.

Jakie jest prawdopodobieństwo że ostatnia osoba usiądzie na swoim miejscu?

[Sylwek]

Hm, mam pomysł na zależność rekurencyjną, ale wiadomo, że to nie jest pełne rozwiązanie.

No więc jeśli babcia siądzie na swoim miejscu, to jest OK, prawdopodobieństwo to \(\displaystyle{ \frac{1}{n}}\). Jeśli babcia siądzie na miejscu ostatniego pasażera, to wiadomo

Jeśli babcia siądzie na miejscu pasażera, który wchodzi na k-tym miejscu do samolotu (\(\displaystyle{ 2 \le k \le n-1}\)), to pasażerowie wchodzący pomiędzy babcią a tym k-tym pasażerem usiedli na swoich miejscach. Więc tak jakby ten k-ty pasażer staje się nową "babcią" dla samolotu liczącego \(\displaystyle{ n-k+1}\) pasażerów (gdyż jedyne wolne miejsca to miejsce babci i miejsca od k+1 do n, a pasażer siada na losowym miejscu, przez co spełnia "warunki nałożone na babcię" ).

Zatem prawdopodobieństwo wynosi (\(\displaystyle{ P_n}\) - prawdopodobieństwo zdarzenia zachodzącego w zadaniu przy n-osobowym samolocie, \(\displaystyle{ n \geqslant 3}\)):

\(\displaystyle{ P_n = \frac{1}{n} + \frac{1}{n} \cdot P_{n-1} + \ldots + \frac{1}{n} \cdot P_2}\)

Łatwo sprawdzić warunek początkowy: \(\displaystyle{ P_2=\frac{1}{2}}\)

--

Aha, no i jak napisałem powyższe szybko wpadłem na pomysł, że tą rekurencję banalnie rozwiązać przy tak dobranym warunku początkowym. Wystarczy indukcyjnie udowodnić, że \(\displaystyle{ P_n=\frac{1}{2}}\), więc pewnie istnieje rozwiązanie "na dwie linijki", skoro szansa jest zawsze połowiczna, chociaż nie ukrywam, że nawet podoba mi się moje rozwiązanie

[allure]

Doskonale rozumiem twoje rozwiązanie Sylwek bo sam właśnie tak robiłem ...chciałem właśnie aby użytkownicy tego forum skonfrontowali się z tym zadaniem i chciałem zobaczyć jaki jest ich sposób na to zadanie, bo własnie mnie ta 1/2 spokoju nie dawała i myślałem że może to jakoś od razu widać.

A tak apropos dziś tłumaczyłem rozwiązanie tego zadania klasie i nikt mnie chyba nie zrozumiał ;P, słaby ze mnie nauczyciel.

[Sylwek]

Przedstawię jeszcze rozwiązanie bez rekurencji ani indukcji.

Nazwijmy ostatniego pasażera dziadkiem

Zauważmy najpierw, że po usadzeniu się \(\displaystyle{ k}\)-tego pasażera, gdzie \(\displaystyle{ k \in \lbrace 2,3,\ldots,n-1 \rbrace}\), miejsce znajdujące się na bilecie tego to \(\displaystyle{ k}\)-tego pasażera będzie zajęte (gdyż albo siądzie tam pasażer o numerze \(\displaystyle{ k}\), albo to miejsce zostało już zajęte przez kogoś, kto miał możliwość zajęcia dowolnego miejsca). Zatem po usadzeniu się \(\displaystyle{ n-1}\) pasażerów miejsca przyporządkowane pasażerom \(\displaystyle{ 2,3,\ldots,n-1}\) będą zajęte. Stąd wniosek, że dziadek może usiąść albo na swoim miejscu, albo na miejscu babci.

Rozpatrzmy więc pierwszą osobę, która zajęła miejsce przyporządkowane babci lub dziadkowi (oczywiście taka osoba istnieje i nie będzie to dziadek, bo inaczej miałby on do wyboru dwa miejsca). Zauważmy, że w.w. osoba musiała zająć to miejsce w wyniku losowania, gdyż w przeciwnym przypadku siadłaby na swoim miejscu. Jedyną osobą, która mogłaby to zrobić, jest babcia, ale z treści zadania wiemy, że ona zajęła swoje miejsce przypadkowo.

Ta wyróżniona osoba zajęła więc z prawdopodobieństwem \(\displaystyle{ \frac{1}{2}}\) miejsce babci i z prawdopodobieństwem \(\displaystyle{ \frac{1}{2}}\) miejsce dziadka. Z wcześniejszych rozważań wiemy, że w pierwszym przypadku dziadek siadł na swoim miejscu, w drugim siadł na miejscu babci. Stąd odpowiedzią jest \(\displaystyle{ \frac{1}{2}}\).

[Kartezjusz]

Czemu Sylwek masz cały czas\(\displaystyle{ \frac{1}{n}}\) w swojej rekurencji?

[Sylwek]

Po 4 latach możesz mnie nie zastać tu zaglądającego

Chodzi o wzór na prawdopodobieństwo całkowite. Inny zapis tego samego: ... 1422/?hs=1