Niedawno opublikowałem tu zagadkę o wrednym naczelniku więzienia, trzech monetach i kostce do gry.
Niezorientowanym przypomnę: mamy za zadanie umieścić na trzech z tysiąca kolejnych pól trzy monety; następnie stajemy na pierwszym polu i rzucamy kostką i przemieszczamy się po każdym rzucie o tyle pól, ile wypadło na kostce. Jeżeli uda nam się stanąć na polu z monetą - wygrywamy. Jeżeli nie (tzn. jeżeli przekroczymy pole z ostatnią monetą bez zatrzymywania się na nim), przegrywamy.
Pytanie było o najlepszą strategię wygrywającą, a dodatkowo również o najlepszą strategię przegrywającą.
Podobnie jak w przypadku innych zagadek, tu również zaczniemy "od dupy strony", czyli uprościmy sobie zagadnienie do jednej monety.
A więc spróbujemy na dzień dobry rozwiązać identyczną zagadkę, ale z tylko jedną monetą.
Dla uproszenia dalszych rozważań wprowadzę teraz jedno oznaczenie: Pk to prawdopodobieństwo wygranej po umieszczeniu money na polu numer k>=1.
Położenie monety na pierwszym polu daje nam:
P1=1/6 ≈ 16.7%
Czemu tak?
Szansa, że wypadnie jedynka wynosi 1/6. Jeżeli wypadnie cokolwiek innego, przegrywamy.
Jeżeli położymy monetę na polu numer 2, dostaniemy:
P2=1/6 + (1/6*1/6) ≈ 19.4%
Wyjaśnienie: szansa, że wypadnie dwójka, wynosi 1/6. Szansa, że wypadnie jedynka, a zaraz po niej druga jedynka, wynosi 1/6*1/6. Innej możliwości na wygraną nie ma.
Trzecie pole:
P3=1/6 + (2 * 1/6 * 1/6) + (1/6 * 1/6 * 1/6) ≈ 22.7%
Jak widać szanse na wygraną rosną z każdym polem. W przypadku pola numer 3 wygrywamy w trzech przypadkach:
- Wyrzucając w pierwszym rzucie trójkę
lub - Wyrzucając (w dowolnej kolejności) jedynkę i dwójkę
lub - Wyrzucając trzy jedynki pod rząd
Pole numer 4:
P4 = ...
Nie chce mi się dalej kombinować, bo ilość opcji robi się zbyt duża.
Widać tu jednak pewną prawidłowość: prawdopodobieństwo wygrania w n-tym rzucie kostką zależy od tego, jak blisko do monety "dotarliśmy" w poprzednim rzucie.
Gdzie leży optimum?
Spróbujmy to sobie zasymulować w Excelu. A właściwie nawet nie zasymulować, tylko policzyć. Na początek - dla ułatwienia - weźmy pod uwagę trzy kolejne rzuty:
Wyjaśnienie: w kolumnach A, B, C wygenerowałem wszystkie możliwe kombinacje trzech kolejnych rzutów kością. W kolumnach D-U natomiast sprawdzam, czy udało się wylosować numer pola (wiersz 3) jako wynik pierwszego rzutu bądź sumy pierwszego z drugim bądź też sumy wszystkich trzech. Jeżeli się udało, wstawiam jedynkę, jeżeli nie - zero. Na koniec sumuję (w górnym wierszu) wszystkie jedynki z danej kolumny i dzielę wynik przez 216 (bo tyle jest łącznie kombinacji z trzech kości). Jak widać po pierwsze prawdopodobieństwa uzyskane dla pierwszych trzech pól zgadzają się z tym, co pokazałem powyżej, a po drugie widać też, że optymalnym polem jest szóstka, potem prawdopodobieństwo spada.
Pewnie dzieje się tak, bo rzuciliśmy tylko trzy razy! Spróbujmy dołożyć czwartą kość:
Jak widać dołożenie czwartej kości tylko umocniło pozycję szóstki: z 35.2% na 36%.
Podpowiem, że kolejne rzuty dodatkowo zwiększają przewagę szóstki, aż do rzutu numer sześć; więcej rzutów nie wpływa na szanse wygrania na polu numer 6.
Co jednak ciekawsze, szanse wygrania na kolejnych polach oscylują coraz mniej, żeby docelowo wylądować w okolicach 28.6% A więc czym dalej od startu położymy naszą pojedynczą monetę, tym mniejsze znaczenie ma wybór konkretnego pola. Warto położyć na szóstce!
No dobra. Tyle pisaniny, a my jeszcze daleko w polu. Co stanie się, jeżeli dołożymy do tego drugą monetę?
Druga moneta
Tu sprawa z liczeniem prawdopodobieństw się nieco komplikuje. Pozornie zagadnienie jest proste: skoro z poprzedniej części wiadomo, jakie są prawdopodobieństwa dla poszczególnych pól dla jednej monety, to wystarczy je pododawać i wyjdzie.
Prawda?
Nieprawda. Jeżeli po prostu dodamy prawdopodobieństwa, otrzymamy wynik zawyżony. Zbyt optymistyczny.
Czemu?
Bo statystyka jest nieintuicyjna!
Załóżmy, że położyliśmy monety na polach k i n (n>k).
Prawdopodobieństwo, że trafimy na pole k lub na pole n równa się sumie prawdopodobieństw trafienia na poszczególne pola MINUS prawdopodobieństwo trafienia na obydwa te pola na raz. Przecież nigdy nie trafimy na dwa pola z monetami, ponieważ gra kończy się po pierwszym trafieniu na pole z monetą. Ale to niekoniecznie musi być pierwsza moneta.
(więcej na ten temat można znaleźć na Wikipedii, poda hasłem "Zasada włączeń i wyłączeń")
Stąd też Pk,n = Pk + Pn - Pn-k
Moglibyśmy teraz skonstruować analogiczną tabelkę w Excelu, ale jesteśmy za leniwi. Powiem więc krótko, że największe szanse przy dwóch monetach uzyskujemy przy polach numer 5 i 6. Mamy wówczas 57.3% szans na wygraną.
Trzecia moneta
Analogicznie przy trzech monetach sprawa komplikuje się jeszcze bardziej, ponieważ (zgodnie z ww. zasadą włączeń i wyłączeń) musimy w obliczeniach uwzględnić więcej kombinacji prawdopodobieństw do odjęcia.
Okazuje się, że najbezpieczniej jest położyć monety na polach 4, 5 i 6. Szansa na wygraną wyniesie wówczas aż 79.3%.
A co z męczennikami? A co, jeżeli ktoś chce przegrać?
Przy jednej monecie to proste: trzeba położyć na pierwszym polu i - tu przeżywalność wynosi tylko 16.7%.
Przy dwóch monetach mamy pola 1, 2 i przeżywalność na poziomie 36%
A przy trzech - pola 1, 2 i 7, z przeżywalnością w okolicach 47%.
Ciężki jest los męczennika.
Na zakończenie dodam jeszcze, że "1000 pól" podanych w treści zagadki to jak widać zwykła zmyłka, dzięki której zagadka wydaje się trudniejsza, niż jest w rzeczywistości.
Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]
Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.