Ś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