Więźniowie i lampa: rozwiązanie zagadki

https://xpil.eu/urs 📋

Poprawne rozwiązanie podał już Butter (w komentarzach), niemniej jednak ponieważ niektórzy komentarzy nie czytują, podam rozwiązanie również tutaj.

Jeżeli ktoś nie wie o co chodzi, niech najpierw kliknie poniżej i przeczyta treść zagadki:

Zagadka: 10 więźniów i lampa

Rozwiązanie jest następujące:

Więźniowie muszą najpierw ustalić który z nich będzie odpowiedzialny za zliczanie więźniów, którzy już odwiedzili pokój. Dla ułatwienia nazwijmy tę osobę Szefem.

Każdego dnia wylosowany zostaje numer celi i więzień z tej celi trafia do pokoju z lampą.

Jeżeli wylosowany nie jest Szefem, wówczas jego algorytm postępowania powinien być następujący:

• Jeżeli dotychczas nie włączał lampy, a lampa jest wyłączona, powinien włączyć lampę i wrócić do celi.
• W przeciwnym razie (tzn. albo już kiedyś włączał lampę, albo lampa jest już włączona) powinien wrócić do celi.

Jeżeli wylosowano Szefa, Szef po wejściu do pokoju z lampą postępuje tak:

• Jeżeli lampa jest wyłączona, nie robi nic i wraca do celi.
• Jeżeli lampa jest włączona, wyłącza ją i zapamiętuje ile razy do tej pory wyłączył lampę.
• Jeżeli wyłączył ją już dziewięć razy (włączając dzisiejszy), wówczas deklaruje koniec gry.
• Jeżeli mniej niż dziewięć, wraca do celi.

W ten sposób tworzymy najprostszy możliwy licznik: żaden z więźniów nie będzie policzony więcej niż raz, żaden z więźniów nie będzie pominięty w liczeniu, gra zawsze kończy się wygraną więźniów w najkrótszym możliwym czasie.

Sprawdźmy teraz ile czasu zajmie gra.

Wariant najbardziej optymistyczny zakłada, że w dni nieparzyste losowani będą więźniowie inni niż Szef (i to za każdym razem inny), a w parzyste - szef. Wówczas gra kończy się po osiemnastu dniach i jest to najkrótszy możliwy czas na zakończenie gry. Oczywiście szanse na to, że tak się stanie są astronomicznie małe.

Wariant najbardziej pesymistyczny zakłada, że przez kolejnych X lat maszyna losująca nie wylosuje któregoś z więźniów w ogóle, jeden z nich umrze ze starości, o czym reszta nie będzie wiedzieć i gra będzie się toczyć aż wszyscy umrą ze starości. Tu szanse też są znikome.

Gdyby zacząć liczyć prawdopodobieństwa... to pewnie uzyskałoby się jakiś konkretny wynik wartości oczekiwanej ilości dni do zakończenia gry. Jednak ponieważ jestem osobnikiem obrzydliwie leniwym, zamiast tego zbudowałem sobie symulację w Excelu, którą uruchomiłem kilkadziesiąt razy i najdłuższy czas oczekiwania wyszedł mi około 186 dni, a najkrótszy - 55 dni. Najczęściej gra kończyła się po upływie 110 - 130 dni.

Można więc z dużą dozą prawdopodobieństwa przyjąć, że więźniowie wyjdą na wolność po spędzeniu na grze od dwóch do sześciu miesięcy, a najpewniej po mniej więcej czterech miesiącach.

Na zakończenie dodam ciekawostkę: jeżeli ilość więźniów zwiększyć do stu, wówczas średni (oczekiwany) czas zakończenia gry wyniesie mniej więcej trzydzieści lat.

https://xpil.eu/urs 📋