Rozwiązanie zagadki wigilijnej

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:

  1. 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
  2. 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!

Zapisz się
Powiadom o
guest
5 komentarzy
Inline Feedbacks
Zobacz wszystkie komentarze
5
0
Zapraszam do skomentowania wpisu.x
()
x