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 📋