S.O.S.

Na pokładzie tonącego statku znajduje się kapitan i 30 członków załogi. Jest także jedna szalupa dla 16 osób. Poza tym ogólnie jest wesoło, więc marynarze postanowili zabawić się w „wyliczankę”. Kapitan ustawił wszystkich w rzędzie i wydał rozkaz:
– Do dziewięciu, kolejno, odlicz!
Przedtem jednak podana była trzypunktowa instrukcja:
1. Pierwsze i każde kolejne odliczanie jest kontynuowane, zaczynając od pierwszego marynarza w rzędzie, który mówi następną liczbę po tej, jaką powiedział ostatni (a więc np. po pierwszym odliczeniu pierwszy marynarz powie „cztery”, drugi „pięć” itd.);
2. Każdy, kto mówi „dziewięć”, natychmiast bierze koło ratunkowe, oddala się od szalupy i szuka sobie jakiejś osobistej ostatniej deski ratunku;
3. Wyliczanka kończy się po odejściu z szeregu 15 marynarzy; pozostali wraz z kapitanem spuszczają na wodę szalupę i zajmują w niej miejsca (kapitan, ma się rozumieć, jako ostatni).

Połowę załogi tonącego statku stanowią zwolennicy koalicji rządowej, drugą połowę – sympatycy opozycji. Kapitan zna preferencje polityczne wszystkich podwładnych, ale swoich nikomu nie ujawnił. Dopiero teraz, w krytycznym momencie, wszystko ma się wyjaśnić, bowiem przed rozpoczęciem wyliczanki kapitan ustawił wszystkich tak, aby w szalupie znaleźć się wyłącznie w gronie osób reprezentujących jego opcję polityczną.
Które miejsca w szeregu zajmują ludzie kapitana?

Kto w oceanie łamigłówek czuje się jak rekin, ten natychmiast zauważy, że powyższe zadanie jest wariacją na temat jednej z odmian tzw. problemu Flawiusza, która w oryginale jest mocno niepoprawna politycznie. Na pokładzie znajdują się w niej bowiem chrześcijanie oraz wyznawcy islamu, zaś jedni z nich nie dostają żadnych szans w postaci kół ratunkowych – po prostu wyrzucani są za burtę. Którzy, to zależy od tego, w jakim kraju zadanie jest publikowane.

Jeszcze bardziej drastyczna jest najstarsza odmiana tej zagadki.
41 żydowskich wojowników oblężonych przez Rzymian, aby nie wpaść w ręce wroga zdecydowało się popełniać samobójstwa. Decyzja o tym zapadała jak w pokładowej wyliczance, ale odliczano do trzech, czyli każdy co trzeci wojownik natychmiast robił sobie kuku. Dwóch z nich, Flawiusz i jego kumpel, zajęło takie miejsca w szeregu, aby mieli zaszczyt popełnić samobójstwo jako ostatni (albo nie popełnić). Które to były miejsca?

Jeden ze znanych polskich fizyków wspominał mi kiedyś, że gdy jako chłopiec zetknął się z zagadką Flawiusza, miewał nieprzyjemne sny. Z rzędu m osób, w którym był ustawiony, z życiem mógł ujść tylko ten, kto zostawał jako ostatni po wielokrotnym odliczaniu do n (w opisany wyżej sposób) i usuwaniu każdej n-tej osoby. Zawsze budził się przerażony tym, że nie wie, na którym miejscu powinien stanąć, aby wyjść cało z opresji. Właśnie, na którym?

Komentarze

[Andrzej]

Ogólna wesołość na pokładzie tonącego statku jest dziwna. Chyba, że załoga ma grog we krwi albo jest z Latającego Cyrku Monty Pythona.

Czy znany polski fizyk ma już spokojny sen i wie na którym miejscu w szeregu powinien stanąć.
Kto wie niech powie.

Pozdrawiam

[marek]

Obawiam się, Panie Andrzeju, że przesadziłem ze stopniem trudności, a zapewne i z czarnym humorem. W każdym razie wygląda na to, że sam będę musiał podać wzór określający zależność między wielkościami m i n a bezpiecznym miejscem fizyka w szeregu straceńców.

[Wojciech]

Tak sobie przeglądałem historię blogu i widzę, że to zadanie nie ma rozwiązania. Opierając się na pana komentarzu nasunęło mi się pytanie czy mógłby pan podać „wzór określający zależność między wielkościami m i n a bezpiecznym miejscem fizyka w szeregu straceńców”?

[Michał S.]

Skoro już ktoś „odkopał” to zadanie, to jako ciekawostkę podam, że niedawno była „afera” z podobnym zadaniem w konkursie matematycznym Kangur. Poszło o to, że w zadaniu należało tak ustawić pasażerów statku, by uratowali się chrześcijanie, a potopili Turcy.

[Marek Penszko]

Wojciechu, wzór ogólny nie jest znany. Przy obliczaniu gdzie stanąć, żeby przeżyć w konkretnym przypadku, trzeba korzystać z rekurencji. Inaczej mówiąc, znając rozwiązanie dla m1 i n1, można znaleźć wynik dla m2 i n2. To jednak temat na dłuższe opowiadanie. Spróbuję je niedługo popełnić, a tymczasem odsyłam do Wikipedii http://en.wikipedia.org/wiki/Josephus_problem i podanych w niej linków.
mp
PS ściśle rzecz biorąc, pojawiają się propozycje ogólnego wzoru, ale wszystkie takie, że głowa boli od samego wyglądu, więc nie będę ich przytaczał, aby nie straszyć matematyką 🙂