Jeden rzut: rozwiązanie zagadki

https://xpil.eu/f5c

Przypomnę zagadkę: cztery osoby siedzą odizolowane od reszty świata (i od siebie nawzajem). Każda ma monetę, generator rzeczywistych liczb losowych 0-1 i musi zdecydować czy rzucić monetą, czy nie. Jeżeli nikt nie rzuci, lub jeżeli komuś wypadnie reszka, przegrywają. Jeżeli przynajmniej jeden rzuci i nikomu nie wypadnie reszka, wygrywają. Co zrobić żeby zmaksymalizować szanse wygranej? Jakie to szanse?

Zaczniemy od tego, że jedyna decyzja, jaką możemy podjąć, to: rzucić czy nie rzucić?

Na jakiej podstawie możemy tę decyzję podjąć?

Jedyne urządzenie "decyzyjne" jakie mamy pod ręką to generator liczb losowych. Możemy teraz założyć, że losujemy liczbę x między 0 a 1 i jeżeli dostaniemy więcej niż pewna wartość progowa p, odkładamy monetę (bez rzutu), a jeżeli wylosujemy x=p lub mniej - rzucamy i liczymy na orzełka. To samo robi pozostała trójka.

Trzeba więc wykombinować jaką przyjąć wartość progową p, aby zmaksymalizować szanse na wygraną.

W sposób oczywisty nie możemy przyjąć p=0, bo wtedy nikt nie rzuci. Nie możemy też przyjąć p=1, bo wtedy rzucą wszyscy a szansa wyrzucenia czterech orłów jest jak jeden do szesnastu. Można lepiej.

Jest pięć możliwych kombinacji kto rzuci monetę a kto nie; każda z nich daje jakieś prawdopodobieństwo wygranej. Sumując te prawdopodobieństwa dostajemy ostateczną odpowiedź, czyli prawdopodobieństwo, że cała czwórka opuści mury więzienia. Naszym zadaniem będzie znalezienie najkorzystniejszego p tj. takiego, dla którego szansa wygranej jest możliwie największa.

Niezależnie od tego jakie p przyjmiemy mamy następujące możliwości (w nawiasach podałem prawdopodobieństwo wygranej dla każdego wariantu):

(1) nikt nie rzuci: (0)

(2) jeden gracz rzuci, trzech nie: (\(4p(1-p)^3\)) - szansa, że wyrzuci on orzełka to 1/2

(3) dwóch graczy rzuci, dwóch nie: (\(6p^2(1-p)^2\)) - szansa na dwa orzełki to 1/4

(4) trzech graczy rzuci, jeden nie: (\(4p^3(1-p)\)) - trzy orzełki wypadną średnio raz na osiem prób czyli 1/8

(5) wszyscy rzucą: (\(p^4\)), 1/16 żeby wyrzucić cztery orły.

O ile jeszcze (1), (2), (4) i (5) są w miarę proste do wyjaśnienia, to skąd się do diaska wzięła ta szóstka w (3)?

A no stąd, że jeżeli mamy czterech więźniów A,B,C,D to możemy dwóch z nich wybrać na sześć różnych sposobów: AB, AC, AD, BC, BD, CD - i każdą z tych sześciu kombinacji traktujemy niezależnie od pozostałych.

Mnożąc prawdopodobieństwa poszczególnych wariantów przez szanse wyrzucenia samych orzełków w każdym z nich dostajemy:

\( 2p(1-p)^3+3/2 p^2(1-p)^2 + 1/2 p^3 (1-p) + 1/16 p^4 \)

Ze szkoły średniej pamiętamy, że aby znaleźć maksimum funkcji trzeba wyznaczyć miejsca zerowe pierwszej pochodnej. Tu pochodną liczy się łatwo, bo to zwykły wielomian jest (i w więzieniu pewnie tak byśmy właśnie zrobili z braku dostępu do komputera), ale ponieważ jesteśmy leniwi, wrzucamy to w Wolframa.

Wynik:

Widzimy, że funkcja przyjmuje maksimum dla p równego mniej więcej 0.342. Prawdopodobieństwo wyjścia z pierdla wynosi w tym przypadku około 28.484%

Szału nie ma... Ale lepszy rydz niż nic.

Do zagadki podszedł Borys - i to aż trzykrotnie.

Jego pierwszy pomysł to:

Każdy więzień wybiera sobie przedział o szerokości 0,333 (np. od 0,666 do 1,000) i naciska generator. Jeżeli generator wylosuje mu coś z tego przedziału, rzuca monetą. Jeżeli nie, nie rzuca.

Tłumacząc na nasze: zamiast dzielić przedział 0-1 na dwie nierówne połowy, dzielimy go na trzy połowy, z czego jedna ma zawsze długość 1/3 a dwie pozostałe sumują się do 2/3 (jak to połowy).

Przy takim podejściu prawdopodobieństwo wyjścia całej czwórki na wolność wynosi 28.472%, czyli zaledwie jedną setną procenta mniej niż opisałem powyżej. Gdyby się uprzeć i zaokrąglić (tak jak zrobił to Borys), wynik jest praktycznie taki sam.

Różnica między wynikami jest niewielka, bo punkt p=0.34204 z oryginalnego rozwiązania leży bardzo blisko punktu 0.333... proponowanego przez Borysa, stąd też prawie identyczne rezultaty.

Drugi pomysł Borysa to:

Zbżan jlryvzvabjnć trarengbe yvpmo ybfbjlpu. Anpmryavx qnwr xnżqrzh jvęźavbjv glyxb zbargę v zójv pbś gnxvrtb: "Cemlwqę whgeb v jgrql cbjvrfm zv, pml ceóohwrfm jlemhpvć bełn, pml cb cebfgh ermltahwrfm m emhgój". Jgrql sbegry cbyrtnłol an glz, żr jvęmvrń zhfvnłol fnz cbemhpnć fbovr zbargą wnxb fhofglghgrz trarengben yvpmo ybfbjlpu.

... co po przepuszczeniu przez ROT13 daje:

Można wyeliminować generator liczb losowych. Naczelnik daje każdemu więźniowi tylko monetę i mówi coś takiego: "Przyjdę jutro i wtedy powiesz mi, czy próbujesz wyrzucić orła, czy po prostu rezygnujesz z rzutów". Wtedy fortel polegałby na tym, że więzień musiałby sam porzucać sobie monetą jako substytutem generatora liczb losowych.

Idea jest zacna, ale ma zbyt wiele niewiadomych. Skąd wiadomo ile razy każdy z więźniów ma rzucić, żeby dostać "porządnie" losową liczbę? Powiedzmy, że jeden rzuci 5000 razy a drugi "tylko" 3000 - ciężko tu policzyć konkretne prawdopodobieństwa (chociaż przy ilości rzutów idącej w tysiące pewnie dałoby się to pozaokrąglać jakoś). Niemniej jednak napomykam o tym tutaj, bo pokazuje niesztampowe podejście do zagadnienia, a to zawsze w cenie!

Nazajutrz Borys wpadł w końcu na poprawne rozwiązanie, napisał bowiem:

Policzyłem głębiej i chciałem zgłosić poprawkę do swojego rozwiązania. Pożądany przedział na generatorze liczb losowych powinien wynosić 0,342. Wydaje mi się, że zmaksymalizuje to szansę na uratowanie się więźniów do obłędnych 28,48 %. 🙂

Rozwiązanie nadesłał również Waldek:

Więzień losuje liczbę z generatora, jeśli jest większa od ok. 0,659 (wariant - mniejsza od 0,341), to rzuca monetą. Szansa na uwolnienie, to ok. 0,287.

Ale ja nie o tym. W innym więzieniu zdarzyło się to samo. Tylko tam strażnik nie dał więźniom generatora! Mimo to potrafili wykorzystać swoją szansę. Jak to możliwe?

Odpowiedź Waldka jest prawidłowa o ile liczył "ręcznie" i mu się zaokrągliło tu i ówdzie. Podane przez Waldka prawdopodobieństwo rozjeżdża się więc względem faktycznego o około trzy tysięczne, przymykam oko. Ponieważ Waldek podał to rozwiązanie jako pierwszy, może się teraz oficjalnie przechwalać z lewa na prawo a zaraz potem z prawa na lewo.

(Jeśli zaś chodzi o pytanie dodatkowe to przypuszczam, że chodzi o ten sam pomysł, co przedtem u Borysa, czyli wstępne wykorzystanie monety jako generatora losowego).

W ostatniej chwili, dosłownie na kilkanaście godzin przed publikacją tego wpisu, do zabawy dołączył też Zgadywacz Dyżurny czyli Cichy Fragles. Jednak z braku czasu nie podniósł on rękawicy na odpowiednią wysokość i skończyło się na:

Sytuacją idealną jest, żeby rzucał tylko jeden więzień, bo jeden orzeł wystarczy nam do szczęścia, a jedna reszka i tak nas załatwia. Na pierwszy rzut oka oczywistość: rzucamy jeśli generator pokaże mniej niż 0.25, co zdarzy się średnio jednemu więźniowi na czterech. Nie jest to jednak optymalne, bo mamy aż 31% szans, że monetą nie rzuci nikt - lepiej zatem ustawić próg trochę wyżej, bo jeśli rzuci dwóch więźniów, to nadal mamy 1/4 szansy, że obaj wyrzucą orła, podczas gdy opcja zerowa oznacza pewną porażkę. Jako żem zarobiony ostatnio po uszy i sił mi już na cokolwiek braknie, nie chciało mi się liczyć, gdzie dokładnie leży optimum - intuicyjnie zakładam, że w okolicach 1/3.

Jak widać wartość 1/3 działa na rozwiązujących jak magnes - w tym przypadku jednak określenie "w okolicach 1/3" chociaż pi x drzwi poprawne, jest jednak za mało dokładne abym mógł uznać tę odpowiedź.

Wszystkim, którzy wzięli się z zagadką za bary serdecznie dziękuję i zapraszam do kolejnych łamigłówek. Następna zagadka zaplanowana jest na okolice 16 czerwca, a w międzyczasie czeka nas recenzja książki oraz jedno całkowicie bezużyteczne, za to dość intrygujące spostrzeżenie szachowe. Stay tuned!

https://xpil.eu/f5c

4 komentarze

  1. Jeszcze raz pochwalę, że to bardzo fajna zagadka! Testowałem wczoraj na swoich uczniach (nie mam już z nimi co robić, program dawno przerobiony, koniec roku szkolnego za pasem, ale ponieważ odwołano matury z powodu korony, to zwyczajne lekcje muszą trwać aż do ostatniego tygodnia). Poradzili sobie nie najgorzej. Potem nawet urządziłem im znienacka małe show. Wybrałem czterech, wyprowadzałem ich pojedynczo z klasy, dawałem monetę i kalkulator Casio z ustawioną komendą Ran#. Dwóch zdecydowało się nie rzucać monetą; dwóch rzuciło i obu wypadły reszki. Bywa.
     
    Ale, ale. Wydaje mi się, że powinniśmy jeszcze raz pochylić się nad moim i Walkda dodatkowym pomysłem. Pytanie brzmi: W jaki sposób rzucać monetą, żeby „zasymulować” prawdopodobieństwo 0,34204…? Odpowiedź: Z pełną precyzją się oczywiście nie da (chyba…?), ale jeżeli na przykład więzień powie sobie: „Rzucam cztery razy i chcę, żeby wypadła najwyżej jedna reszka”, to prawdopodobieństwo sukcesu wynosi już 0,3125, czyli jesteśmy całkiem blisko optymalnej wartości.

    1. Tak naprawdę zamiast “chcę żeby wypadła najwyżej jedna reszka” wystarczy rzucić 10 albo 100 razy, zapisać wygenerowany w ten sposób ciąg zer i jedynek, a na koniec dopisać z przodu zero i kropkę. Da to lepszy rozkład, jednak bez wstępnego ustalenia ile razy rzucać dokładnie się tego nie policzy. No ale z braku laku chyba nie ma lepszej metody bez osobnego generatora.

      1. Twój wynik z Wolframa zawiera pięć cyfr znaczących, z czego cztery są pewne, a ostatnia już nie (rzeczywisty wynik może wyglądać np. tak: 0,342035…).
         
        Policzmy więc ile rzutów monetą X da co najmniej taką samą dokładność, czyli 0,00001:
         
        1/2^X < 0,00001
        2^X > 10000
        X >= 17
         
        Chciałem tu skończyć, ale niech tam, sprawdźmy:
         
        Na podstawie wyniku 0,34204 z Wolframa można stwierdzić, że rzeczywiste prawdopodobieństwo P:
         
        0,342035 <= P < 0,342045
         
        Stąd zakres dla losowanej liczby L:
         
        L >= 0,342035*2^17 = 0,342035*131072 = 44831,21
        L < 0,342045**2^17 = 0,342045*131072 = 44832,52
         
        czyli:
         
        L=44832
         
        co daje:
         
        P=44832/131072=0,3420410 +/-0,000007,
         
        z lepszym oszacowaniem, niż Wolfram. Rzeczywiście, wystarczy 17 rzutów.
         
         
         

Leave a Comment

Komentarze mile widziane.

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.