Postawiona niedawno zagadka o sosie żurawinowym cioci Beaty ma haczyk: jest bardzo nieintuicyjna. Intuicja bowiem podpowiada nam, że osoby siedzące najbliżej osoby numer 0 (a więc 1 i 19) mają największą szansę dostania sosjerki, ich sąsiedzi (czyli 2 i 18) nieco mniejszą i tak dalej, a więc statystycznie najdłużej będzie czekać ten, kto siedzi dokładnie naprzeciwko nas.
Spróbujmy sobie jednak bardzo precyzyjnie zdefiniować co to znaczy, że gość X dostanie sosjerkę jako ostatni:
- Jego sąsiad po lewej stronie dostał sosjerkę od swojego lewego sąsiada, po czym przekazał ją w lewo, sosjerka obeszła cały stół dookoła i trafiła do X z prawej strony, lub
- Jego sąsiad po prawej stronie dostał dostał sosjerkę od swojego prawego sąsiada, po czym przekazał ją w prawo, sosjerka obeszła cały stół dookoła i trafiła do X z lewej strony.
Widzimy wyraźnie, że szansa na to, że tak się stanie jest całkowicie niezależna od tego, gdzie w danym momencie znajduje się sosjerka! Tym samym każdy z gości ma jednakową szansę na bycie ostatnim; szansa ta wynosi 1/19.
Jeżeli ktoś nie wierzy, oto prościutka symulacja w Pythonie:
from random import random
proby = [0 for x in range(20)]
for i in range(1000000):
goscie = [0 for x in range(20)] # od 0 do 19
goscie[0] = 1 # mam sosjerkę na początku
sosjerka = 0 # numer gościa z sosjerką
while 0 in goscie:
sosjerka = (sosjerka + (1 if random() < 0.50 else -1)) % 20
goscie[sosjerka] = 1
proby[sosjerka] += 1
print(proby)Po około minucie czekania dostałem:
[0, 52496, 52781, 52621, 52408, 52575, 52655, 52478, 52948, 52454, 52677, 52166, 52332, 52754, 52538, 52648, 52784, 53161, 52722, 52802]
Jak widać po milionie wigilii każdy z gości (oprócz nas samych) załapał się na ostatniego do sosjerki około 52.5 tysiąca razy. 1000000/19 to okolice 52.6 tysiąca, czyli wszystko się zgadza.
Oczywiście wystarczy nawet niewielkie odchylenie w losowaniu (dajmy na to, o 1%), żeby szanse przechyliły się na jedną lub drugą stronę:
from random import random
proby = [0 for x in range(20)]
for i in range(1000000):
goscie = [0 for x in range(20)] # od 0 do 19
goscie[0] = 1 # mam sosjerkę na początku
sosjerka = 0 # numer gościa z sosjerką
while 0 in goscie:
sosjerka = (sosjerka + (1 if random() < 0.51 else -1)) % 20
goscie[sosjerka] = 1
proby[sosjerka] += 1
print(proby)[0, 36052, 37393, 38844, 40499, 42302, 43795, 45477, 47347, 49531, 51182, 53769, 55685, 57917, 60354, 62504, 65141, 67618, 70995, 73595]
A jak Wam poszło?
1Pierwszy nadesłał swoją odpowiedź Cichy Fragles, stały bywalec blogu oraz częsty rozwiązywacz lokalnych łamigłówek. Cichy zaufał intuicji, co jak już wiemy okazało się błędem - postawił on na osobę naprzeciwko, czyli tę o numerze 10. Nie zaliczam.
2Drugi odezwał się Waldek, również jeden z Naczelnych Rozwiązywaczy Zagadek. Waldkowa intuicja podpowiedziała mu to samo, co Fraglesowi, ale postanowił on sprawdzić swoje rozwiązanie za pomocą symulacji i wyszło mu, że albo ósemka, albo dwunastka.
Fascynująca kolacja! (o ile się nie pomyliłem)...
Po pierwszych siedmiu czytaniach zadania byłem nadal pewien, że chodzi o nr 10. Potem mnie tknęło, że nr 20 (czyli ty) burzy symetrię, gdyż od początku trzyma sosjerkę, co trochę przeszkadza w późniejszej zmianie kierunku. Od twojego pierwszego rzutu monetą powinna więc zależeć przewaga jednego z kierunków i zasięg sosjerki.
Szybki program, 19000000 pętli i:
https://s6.ifotos.pl/img/Wykresjpg_qqspsap.jpg
Zaskakujące. Wygrywają ex aequo nr 8 i 12.
Co ciekawe, jeśli to nie ty, ale lokaj rzuci monetą i poda sosjerkę, to wszystko się zmienia:
https://s6.ifotos.pl/img/Wykres20j_qqspsaa.jpg
Tego wyjaśnić już nie potrafię. Trzeba spytać lokaja.
Pochwal się, Waldku, swoim kodem, może znajdziemy błąd - przy 19000000 prób powinieneś dostać wyniki podobne do moich. Zresztą patrząc na skalę Twojego pierwszego wykresu różnica między "zwycięzcą" a "przegranym" jest rzędu 0.1%, więc może trzeba było powtórzyć eksperyment kilka razy żeby zauważyć, że na "wygraną" mają taką samą szansę wszyscy? Tak czy siak, nie zaliczam.
3Trzeci (i ostatni) dał głos Rozie, który już, już miał napisać, że 10, ale potem sobie napisał symulator i mu wyszło, że wszyscy mają jednakowe szanse (Rozie wysłał nawet kod symulatora w Pythonie, ale po drodze formatowanie poszło w diabły więc go tu nie wkleję). To pierwsza poprawna nadesłana odpowiedź - zaliczam!
Spróbujmy powalczyć z formatowaniem:
import random results = {} count = 0 for x in range(0, 100000): visited = set() visited.add(0) guest = 0 while len(visited) < 20: count += 1 choice = random.randint(0, 1) if choice: guest += 1 else: guest -= 1 if guest < 0: guest = 19 elif guest > 19: guest = 0 visited.add(guest) if results.get(guest): results[guest] += 1 else: results[guest] = 1 for x in results: print("{} {}".format(x, results[x])) print(count)Poprawiłem przy okazji zliczanie ilości przekazań sosjerki. Funkcjonalność zaginęła przy przejściu z symulacji pojedynczego przebiegu, na wersję statystyczną. Jak widać dowiadujemy się tu, że średnia liczba przekazań to 190. Zmienną count trzeba podzielić przez ilość prób. Oj, namachają się tą sosjerką przy stole…
Przy okazji, spróbuję odtworzyć pierwotną, błędną odpowiedź. A nawet dwie!
Stawiałem na 10, bo jest to osoba najdalej od zaczynającej. I ma niewielkie szanse na to, że sosjerka do niej dotrze, szczególnie tak szybko jak to możliwe. Odpowiednik 10 orłów (albo reszek) z rzędu.
Miałem też odpowiedź hackerską.
Wszystkie osoby, poza 10 występują parami o równej odległości od zaczynającego. 1 i 19, 2 i 18 itd. Tylko osoba nr 10 nie ma pary, a pytanie jest o jedną osobę, stąd musi to być właśnie ona.
Tyle, że nie.
TBH uratowała mnie zabawa w adventofcode.com połączona z ciekawością ile będzie podań. Wiedziałem, że będzie ich dużo, ale te 10 orłów z rzędu nie dawało mi spokoju, więc chciałem zasymulować. Tknęło mnie, jak przy paru przebiegach otrzymałem wyniki podejrzanie blisko startującego…
“Pochwal się, Waldku, swoim kodem, może znajdziemy błąd”
Nie ma potrzeby, moje rozwiązanie, szalone i nieoczekiwane – jest poprawne. Błąd jest w twoim programie. Szkolny. Nie powiem gdzie, ale widać od razu, że sytuacja 1-19, 2- 18 … 9-11 musi być symetryczna (lewo-prawo). W twoim rozwiązaniu 1=36052, a 19=73595. Szewski błąd (tak, jak szewski mat) – zgaduj zgadula.
Ja natomiast pomyliłem się w rozwiązaniu w wersji z lokajem. Nie spojrzałem na skalę osi Y. Nieważne. Ten wariant jest ‘invalid’.
Chyba przeoczyłeś pierwsze rozwiązanie i patrzysz na wariant drugi, asymetryczny.
Nie rozumiem.
Napisałem, że rozwiązanie musi być symetryczne…
Proponuję przeczytać jeszcze cały wpis z odpowiedzią, uważnie. Najpierw podaję rozwiązanie zagadki, a potem pokazuję co dzieje się w przypadku nieuczciwej monety (51% vs 49%).