Śmiertelna zagadka – rozwiązanie

https://xpil.eu/azhs

Zagadka numer 1 jest faktycznie banalna i można ją rozwiązać w dwie minuty za pomocą kartki i ołówka, i w zasadzie bez żadnego pomyślunku. Przeżyje więzień z plakietką numer 9.

Dla pewności jednak - mój kod symulujący pierwszą zagadkę:

n = 20  # Liczba uczestników
k = 2  # Krotność (co drugi)
więźniowie = list(range(1, n+1)) # plakietki ponumerowane od 1, lista poindeksowana od 0
bieżący = 0  # Zaczynamy od pierwszego więźnia
while len(więźniowie) > 1: # Dopóki żyje więcej niż jeden więzień
    bieżący = (bieżący + k - 1) % len(więźniowie)
    del więźniowie[bieżący]
print(f"Przeżył więzień numer {więźniowie[0]}")

Wynik: Przeżył więzień numer 9

Oryginalnie problem znany jest jako permutacja Flawiusza. Jeżeli zajrzymy tam do sekcji "Przypadek ogólny", to z prezentowanego tam wzoru na J(n) można napisać całkiem interesującą funkcję znajdującą zwycięzcę rekurencyjnie:

def flawiusz(n, k):
    return 1 if n == 1 else (flawiusz(n - 1, k) + k - 1) % n + 1

print(f"Przeżył więzień numer {flawiusz(20, 2)}")

Nie będę kłamał, że rozumiem tę rekurencję, ale rozwiązanie podoba mi się ze względu na swoją uniwersalność i zwartość.

Zagadka numer 2 jest nieco bardziej skomplikowana, jeżeli chcielibyśmy rozwiązać ją w sposób formalny. Teoretycznie można próbować bawić się w modelowanie procesów Markowa, jednak w rzeczywistości liczba możliwych stanów przy dwudziestu uczestnikach jest astronomicznie duża. Dla czterech czy pięciu więźniów jeszcze miałoby to sens. Dla dwudziestu - nie za bardzo. Dlatego uciekamy się do symulacji.

Kod będzie bardzo podobny jak przy zagadce numer 1, tylko musimy za każdym razem losować wartość k a także przeprowadzić odpowiednio dużo eksperymentów, żeby wynik był jak najbardziej zbliżony do rzeczywistości.

import random
from collections import Counter

def symulacja(n):
    więźniowie = list(range(1, n+1))
    bieżący = 0  # Zaczynamy liczyć od gościa z plakietką 1
    while len(więźniowie) > 1:
        k = random.choice([2, 3])  # losujemy długość kroku - 2 lub 3
        bieżący = (bieżący + k - 1) % len(więźniowie)  # wyliczamy pozycję kolejnego więźnia do ubicia
        del więźniowie[bieżący]  # szczelamy
    return więźniowie[0]  # ostatni będą piersiami czy coś

liczba_więźniów = 20
liczba_symulacji = 100000

wyniki = Counter(symulacja(liczba_więźniów) for _ in range(liczba_symulacji))

print("Szanse i numery pierwszej trójki na przeżycie:", [f"{x[0]}:{round(x[1]/liczba_symulacji*100,1)}%" for x in wyniki.most_common(3)])

Po stu tysiącach symulacji wyszło mi:

Szanse i numery pierwszej trójki na przeżycie: ['18:6.8%', '19:6.7%', '17:6.7%']

Oczywiście the more, the merrier, proszę sobie zrobić milion albo i dziesięć milionów symulacji jak ktoś ma cierpliwość.

Wychodzi więc na to, że wybierając plakietkę 17, 18 lub 19 mamy około 6.7% szans na przeżycie. Szału nie ma.

Ponieważ formularz odpowiedzi dopuszcza wyłącznie liczby całkowite (moje niedopatrzenie), postanowiłem uznać za poprawne odpowiedzi 6%, 7% lub 8%.

A jak Wam poszło?

1Jeszcze tego samego dnia pierwsze zgłoszenie nadesłał Cichy Fragles i chociaż numery plakietek wyszły mu całkiem błędne (a więc znalazłszy się w tej konkretnej sytuacji, prawdopodobnie wybrałby złą plakietkę), to formalnie muszę mu tę odpowiedź uznać, bo podał prawdopodobieństwo 7%, a w treści zadania pytałem właśnie o tę liczbę.

2Nazajutrz prawidłową odpowiedź nadesłał Waldek. Jego odpowiedź na drugą zagadkę jest nieco zagadkowa, bo bez żadnych objaśnień a także z dwoma miejscami po przecinku (6.73), co zgadza się z symulacją. Pochwal się, Waldku, w wolnej chwili, jaką metodą dotarłeś do wyniku.

3W niedzielę nadeszło połowiczne rozwiązanie Buttera. Połowiczne, bo Butter pokusił się tylko o rozwiązanie pierwszej zagadki. Co do drugiej - wysłał mi tylko krótką wiadomość, że chwilowo nie ma wystarczająco zapału, może kiedyś się zbierze. Zaliczam połowicznie 🙂

4Rozie przysłał swoje rozwiązanie ciut później, też połowiczne. Nadgryzł pierwszą zagadkę algorytmem trochę dookoła, ale wynik mu wyszedł poprawny. Podobnie jak Butterowi, tu też zaliczam połowicznie.

prisoners = [ n for n in range(1, 21) ]
dead = []

skip = True
while len(dead) < 20:
    for p in prisoners:
        if p not in dead:
            if skip:
                skip = False
            else:
                dead.append(p)
                skip = True
print(dead)

5W okolicach wtorku wieczorem drugą odpowiedź nadesłał Waldek, przy okazji wyjaśniło się, że byle jak zorganizowałem nie tylko pole z odpowiedzią (niemożność wpisania ułamków), ale też miejsce do zamieszczania komentarzy. Na pohybel mi.

Wisienką na torcie waldkowego rozwiązania jest załączony kod, który - zamiast wszechobecnego ostatnimi czasy Pythona - został napisany w Visual Basic-u Delphi:

Function Flawiusz(n: integer): integer;
begin
  if n=1 then begin
    Result:=1;
    Exit;
  end;
  Result:=((Flawiusz(n-1)+Random(2)+1) mod n)+1;
end;

const zakres=10000000;

procedure TForm1.BStartClick(Sender: TObject);
var i, j: integer;
    s: string;
    tRes: array[1..20]of integer;
begin
  Randomize;
  for j:=1 to zakres do
    Inc(tRes[Flawiusz(20)]);

... Liczenie średniej trzech najlepszych wyników i drukowanie...
end;

Wyniki faktycznie dają sporą dokładność (10M prób - nie w kij dmuchał):

Wyniki:
------
1:  622837
2:  306165
3:  302503
4:  454501
5:  306385
6:  389789
7:  398538
8:  375279
9:  432581
10:  435332
11:  465354
12:  501813
13:  525919
14:  569315
15:  605702
16:  637130
17:  667813
18:  678269  <-- maks1
19:  672987  <-- maks2
20:  651788  <-- maks3

Średnia: 0,0667681333333333

https://xpil.eu/azhs