PytonZCatanu pisze: ↑15 kwie 2023, 13:23
Ale jak tam wychodzi 1/2?
Generalnie dla każdej liczby żetonów n>1 mamy 50%. Można to udowodnić "rekurencyjnie", analizując kolejne liczby od 2 wzwyż.
Dla n=2 wynik jest oczywisty.
Dla n=3 mamy 3 możliwości ulokowania żetonu numer 1. Jeżeli trafi na pozycję 1, to drugi i trzeci zajmą swoje miejsca. Czyli dla ostatniego mamy 100% szans na właściwe położenie. Jeżeli żeton 1 trafi na pozycję 3, to żeton 3 ma zero szans, żeby tam się znaleźć. (Tak jest zresztą dla każdego n - gdy pierwszy żeton trafia na pozycję 1, n-ty żeton ma 100% szans na właściwą pozycję, a gdy pierwszy zajmie miejsce n-tego, to 0%.) A co będzie, gdy żeton 1 trafi na pozycję 2? Wtedy żeton 2 ma do wyboru dwa miejsca: 1 i 3, z prawdopodobieństwem 50% dla każdego z nich. Mamy zatem 1/3 * 100% + 1/3 * 50% + 1/3 * 0% co daje 50%.
Dla n=4 przypadki trafienia żetonu 1 na miejsce 1 i ostatnie dają efekt analogiczny jak dla n=3 z tą tylko różnicą, że teraz każdy z tych przypadków ma po 1/4 szans na zaistnienie. Jeżeli żeton 1 trafi na pozycję 3, to żeton 2 zajmie swoje miejsce i mamy opisana wyżej sytuację z trzema żetonami. Jeżeli żeton 1 trafi na pozycję 2, to od tej chwili żeton 2 przejmuje rolę żetonu 1 i znowu możemy sprowadzić to do układu trzech żetonów. A zatem w obu tych "pośrednich" sytuacjach mamy po 50% szans na to, by ostatni żeton zajął właściwe miejsce.
To samo rozumowanie możemy przeprowadzić dla każdej kolejnej wartości n.
Można też przeprowadzić rekurencję od końca. Załóżmy, że żeton 1 trafił na pozycję n-1 czyli w podstawowej wersji 99. Wtedy wszystkie żetony od 2 do 98 trafiają na swoje miejsca. A żeton 99 może z prawdopodobieństwem 50% trafić na miejsce 1 (i wtedy żeton 100 zajmuje swoja pozycję) albo z prawdopodobieństwem 50% na miejsce 100 i wtedy ostatni żeton nie może tam się znaleźć. A teraz załóżmy, że żeton 1 trafia na miejsce n-2 czyli 98. Żetony 2-97 zajmują oczywiście swoje pozycje, a żeton 98 może zając miejsca 1, 99 i 100. Dwa skrajne przypadki dają oczywisty rezultat, a zajęcie przez żeton 98 miejsca 99 sprowadza problem do sytuacji, gdy miejsce 99 zajął żeton 1.
Możesz znaleźć inne rozwiązania zadania (w oryginalnej formie z pasażerami samolotu, a nie żetonami) wpisując w wyszukiwarkę:
One hundred people line up to board an airplane. Each has a boarding pass with assigned seat. However, the first person to board has lost his boarding pass and takes a random seat.
.