Tekst źródłowy strony Problem Józefa Flawiusza

'''Problem Józefa Flawiusza''' (także: '''permutacja Józefa Flawiusza''') – problem teoretyczny z zakresu [[kombinatoryka|kombinatoryki]]. Często rozważany w [[informatyka|informatyce]]. W ogólnej wersji problem brzmi następująco: na okręgu ustawiamy <math>n</math> obiektów, następnie eliminujemy co <math>k</math>-ty obiekt, tak długo, aż zostanie tylko jeden. Należy wskazać obiekt, który pozostanie.

Dla <math>k=2</math> istnieje [[wzór jawny]]<ref name="mk">{{Cytuj książkę |nazwisko = Graham |imię = Ronald |tytuł = Matematyka konkretna |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |data = 2006 |strony = 23–32 |isbn = 83-01-14764-4 |rozdział = Problem Józefa Flawiusza}}</ref>, a dla pozostałych <math>k</math> istnieją algorytmy rozwiązujące problem między innymi w [[Złożoność obliczeniowa|złożonościach czasowych]] <math>O(n)</math> i <math>O(k \log n)</math>{{r|dynamic}}<ref name="maximal">{{Cytuj stronę |url = http://e-maxx.ru/algo/joseph_problem |tytuł = Задача Иосифа |data = 2008-06-11 |opublikowany = MAXimal |język = ru |data dostępu = 2017-06-09}}</ref><ref name="nlogm">{{Cytuj pismo |nazwisko = Lloyd |imię = Errol |tytuł = An O(n log m) Algorithm for the Josephus Problem |czasopismo = Journal of Algorithms |strony = 262–270 |język = en |data = 1983-09}}</ref>.

== Historia i odmiany problemu ==
Nazwa nawiązuje do postaci [[Józef Flawiusz|Józefa Flawiusza]], rzymsko-żydowskiego historyka żyjącego w I wieku n.e. Miał on zostać wraz z grupą powstańców otoczony w jaskini w trakcie [[Oblężenie Jotopaty|oblężenia Jotopaty]]. Żołnierze woleli [[samobójstwo]] od pojmania, a że żydowskie prawo religijne zabrania odbierania sobie życia, zdecydowali się losować, kto zabije poprzednio wylosowanego, tak długo, dopóki nie pozostanie jeden, który będzie musiał się zabić sam. Gdy, zrządzeniem losu, przy życiu pozostali Flawiusz wraz z jednym z towarzyszy, zdecydowali się oni poddać Rzymianom. Tak to opisywał sam Flawiusz w ''[[Wojna żydowska (Flawiusz)|Wojnie żydowskiej]]''{{r|wojna}}:

{{Cytat
 |treść = Jednak nawet w tym rozpaczliwym położeniu nie brakło mu pomysłowości. Ufny w opiekę Bożą, życie swoje postawił na jedną kartę i rzekł: „Skoro już postanowiliśmy umrzeć, to niechaj los rozstrzygnie, w jakiej kolejności mamy jeden drugiego zabijać. Pierwszy, na którego padnie, niech zginie z ręki następującego po nim”. (…) W końcu pozostał tylko Józef wraz z jednym towarzyszem (można by rzec, że albo przypadek tak chciał, albo Opatrzność Boża) i nie chcąc zginąć z wyroku losu ani też, gdyby on sam był tym ostatnim, splamić swojej ręki bratnią krwią, przekonał także owego męża, aby otrzymawszy porękę pozostał przy życiu<ref name="wojna">{{Cytuj książkę |nazwisko = Flawiusz |imię = Józef |tytuł = Wojna żydowska |strony = 119–122}}</ref>.
}}

Pierwszym, który przekształcił tę historię w problem matematyczny, miał być szesnastowieczny francuski matematyk [[Claude Gaspard Bachet de Méziriac]]. Według niego, ustawieni w okrąg żołnierze mieli eliminować co trzeciego spośród siebie<ref name="dm">{{Cytuj pismo |nazwisko = Dowdy |imię = James |nazwisko2 = Mays |imię2 = Michael |tytuł = Josephus permutations |czasopismo = Journal of Combinatorial Mathematics and Combinatorial Computing |wolumin = 6 |język = en |data = 1989-01}}</ref><ref name="bachet">{{Cytuj książkę |nazwisko = Bachet de Méziriac |imię = Claude Gaspard |tytuł = Problemes Plaisants ed Delectables qui se font par les Nombres |data = 1612 |strony = 174 |język = fr}}</ref>. Po Bachecie historia ta była wielokrotnie powtarzana ze zmieniającymi się szczegółami – przykładowo Kaplansky podaje, że powstańców było 40 (wliczając Flawiusza), a eliminowano co siódmego. Flawiusz, postawiony przed problemem, miał szybko policzyć, gdzie musi się ustawić, by przeżyć<ref name="matters">{{Cytuj książkę |nazwisko = Herstein |imię = I.N. |tytuł = Matters Mathematical |wydawca = Harper and Row |data = 1974 |strony = 121–126 |nazwisko2 = Kaplansky |imię2 = Irving |język = en}}</ref>.

Inne źródło podaje, że uczestników było łącznie 41, a Flawiusz i wtajemniczony przez niego powstaniec ustawili się odpowiednio na 16. i 31. pozycji przy eliminowaniu co trzeciego powstańca. W tej wersji problemu należy wyznaczyć dwóch ostatnich ludzi, którzy pozostaną przy życiu<ref name="recreations">{{Cytuj książkę |nazwisko = Rouse Ball |imię = W.W. |tytuł = Mathematical Recreations and Essays |url = https://www.gutenberg.org/ebooks/26839 |wydawca = Macmillan |data = 1896 |język = en}}</ref>.

Wersja przedstawiona w ''[[Matematyka konkretna|Matematyce konkretnej]]'' zakłada, że zabijany jest co drugi uczestnik. Jest to jedyna wersja problemu, dla której udowodniono istnienie [[wzór jawny|wzoru jawnego]]<ref name="mk1">{{Cytuj książkę |nazwisko = Graham |imię = Ronald |tytuł = Matematyka konkretna |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |data = 2006 |strony = 23 |isbn = 83-01-14764-4 |rozdział = Problem Józefa Flawiusza}}</ref><ref name="encyclopedia">{{Cytuj książkę |nazwisko = Ben-Menahem |imię = Ari |tytuł = Historical Encyclopedia of Natural and Mathematical Sciences |strony = 424 |tom = 1}}</ref>.

Istnieje też pokrewny problem, który został wymyślony w średniowieczu. 15 [[Turcy|Turków]] i 15 [[chrześcijaństwo|chrześcijan]] płynie statkiem w trakcie sztormu. Kapitan stwierdza, że aby uratować statek, połowa pasażerów musi go opuścić. Pasażerowie stają w kręgu i co dziewiąty skacze do morza. W tej wersji należy znaleźć pozycje, na których mają ustawić się chrześcijanie, by przeżyć{{r|recreations|bachet}}.

== Rozwiązania ==
Niech <math>n</math> oznacza początkową liczbę osób w kręgu, a <math>k</math> krok w każdej iteracji (po każdej egzekucji <math>k-1</math> osób po poprzednio wybranej jest pomijanych, a <math>k</math>-ta zabijana). Osoby w kręgu numerowane są od [[liczby naturalne|liczbami naturalnymi]] od <math>1</math> do <math>n,</math> a jako pierwszy zabijany jest uczestnik o numerze <math>k.</math>

=== k=2 ===
W tej sekcji podane jest rozwiązanie problemu w sytuacji, gdy <math>k=2.</math> Niech <math>J(n)</math> oznacza pozycję pozostałego uczestnika w sytuacji, gdy na początku było ich <math>n.</math>

Pierwsza runda wokół okręgu eliminuje wszystkich uczestników o numerach parzystych. Jeżeli <math>n</math> jest parzyste, to po tej rundzie sytuacja będzie o tyle podobna, że wciąż mamy do czynienia z parzystą liczbą uczestników, lecz o nieco zmienionych numerach. Zakładając, że zaczęliśmy z <math>2n</math> uczestnikami, po pierwszej rundzie sytuacja wygląda tak, jakbyśmy zaczynali z <math>n</math> uczestnikami o podwojonych i ''zmniejszonych'' o 1 numerach. Otrzymujemy więc<ref name="mk10">{{Cytuj książkę |nazwisko = Graham |imię = Ronald |tytuł = Matematyka konkretna |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |data = 2006 |strony = 24 |isbn = 83-01-14764-4 |rozdział = Problemy rekurencyjne}}</ref>:
: {{wzór|<math>J(2n) = 2J(n) - 1\quad\mbox{dla } n \geqslant 1</math>|1}}

Jeżeli zaczynamy z <math>2n+1</math> uczestnikami i wykonujemy jedną rundę, to uczestnik o numerze <math>1</math> jest eliminowany zaraz po uczestniku o numerze <math>2n.</math> Ponownie zostajemy z <math>n</math> osobami, jednak tym razem ich numery są podwojone i ''powiększone'' o 1, a więc<ref name="mk11">{{Cytuj książkę |nazwisko = Graham |imię = Ronald |tytuł = Matematyka konkretna |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |data = 2006 |strony = 24–25 |isbn = 83-01-14764-4 |rozdział = Problemy rekurencyjne}}</ref>:
: {{wzór|<math>J(2n+1) = 2J(n) + 1\quad\mbox{dla } n \geqslant 1</math>|2}}

Łącząc te równania z <math>J(1) = 1</math> otrzymujemy wzór rekurencyjny, który pozwala na policzenie <math>J(n)</math> w [[złożoność obliczeniowa|złożoności obliczeniowej]] <math>O(\log n).</math> Można wykorzystać ten wzór do stablicowania funkcji <math>J(n)</math>{{r|mk11}}:

{| class="wikitable"
|<math>n</math> || '''1''' || '''2''' || 3 || '''4''' || 5 || 6 || 7 || '''8''' || 9 || 10 || 11 || 12 || 13 || 14 || 15 || '''16''' || 17
|-
|<math>J(n)</math> || '''1''' || '''1''' || 3 || '''1''' || 3 || 5 || 7 || '''1''' || 3 || 5 || 7 || 9 || 11 || 13 || 15 || '''1''' || 3
|}

Można zaobserwować, że wartości da się zgrupować według kolejnych potęg 2, a kolejne grupy są ciągami liczb nieparzystych. Stąd otrzymujemy wzór{{r|mk11}}:
: {{wzór|<math>J(2^m+l) = 2l+1\quad\mbox{dla }m \geqslant 0 \wedge 0 \leqslant l < 2^m</math>|3}}

Wzór {{LinkWzór|3}} można udowodnić za pomocą [[indukcja matematyczna|indukcji]] ze względu na <math>m.</math> Gdy <math>m=0,</math> <math>l</math> musi być równe <math>0,</math> więc baza indukcji sprowadza się do <math>J(1)=1,</math> co jest prawdą<ref name="mk12">{{Cytuj książkę |nazwisko = Graham |imię = Ronald |tytuł = Matematyka konkretna |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |data = 2006 |strony = 25–26 |isbn = 83-01-14764-4 |rozdział = Problemy rekurencyjne}}</ref>.

Jeśli <math>l</math> jest parzyste, to:
: {{wzór|<math>J(2^m+l) = 2J\left(2^{m-1}+\frac{l}{2}\right)-1 = 2\left(\frac{2l}{2}+1\right) - 1 = 2l+1</math>}}

ze względu na wzór {{LinkWzór|1}} i założenie indukcyjne. Podobnie udowadniamy dla <math>l</math> nieparzystych:
: {{wzór|<math>J(2^m+l) = 2J\left(2^{m-1}+\frac{l-1}{2}\right)+1 = 2\left(\frac{2(l-1)}{2}+1\right) + 1 = 2l+1,</math>}}

co kończy dowód. Przekształcając wzór {{LinkWzór|3}}, otrzymujemy wzór jawny<ref>{{MathWorld|adres=JosephusProblem |tytuł=Josephus Problem |data dostępu=2017-06-09}}</ref>:
: <math>J(n) = 2(n-2^{\lfloor \log_2(n) \rfloor})+1.</math>

Można też udowodnić, że <math>J(n)</math> odpowiada [[obrót bitowy|obrotowi bitowemu]] <math>n</math> o jedno miejsce w lewo. Jeśli przedstawimy <math>n</math> w [[Dwójkowy system liczbowy|postaci dwójkowej]]: <math>n=(b_m b_{m-1} \dots b_1 b_0)_2</math> to, wiedząc, że <math>n=2^m+l,</math> otrzymamy<ref name="mk13">{{Cytuj książkę |nazwisko = Graham |imię = Ronald |tytuł = Matematyka konkretna |wydawca = Wydawnictwo Naukowe PWN |miejsce = Warszawa |data = 2006 |strony = 26–27 |isbn = 83-01-14764-4 |rozdział = Problemy rekurencyjne}}</ref>:
: <math>n=(1b_{m-1}b_{m-2}\dots b_1 b_0)_2</math>
: <math>l=(0b_{m-1}b_{m-2}\dots b_1 b_0)_2</math>
: <math>2l=(b_{m-1}b_{m-2}\dots b_1 b_0 0)_2</math>
: <math>2l+1=(b_{m-1}b_{m-2}\dots b_1 b_0 1)_2</math>
: <math>J(n)=(b_{m-1}b_{m-2}\dots b_1 b_0 b_m)_2</math>

Ostatni krok wynika z tego, że <math>J(n) = 2l+1,</math> a <math>b_m = 1</math>{{r|mk13}}.

==== Implementacja ====
Przykładowa [[Implementacja (informatyka)|implementacja]] powyższego rozwiązania w [[Język programowania|języku]] [[Python]] 3:
<syntaxhighlight lang="python">
def flawiusz(n):
    # Wyznaczenie l
    l = n - (1 << (n.bit_length() - 1))

    # Wyznaczenie miejsca bezpiecznego z wzoru (3)
    wynik = 2*l + 1
    return wynik
</syntaxhighlight>

=== Przypadek ogólny ===
Problemem, który pozostaje otwarty, jest wyznaczanie <math>J(n)</math> w sytuacji, gdy <math>k \neq 2.</math> Rozwiązanie intuicyjne, działające w złożoności <math>O(nk),</math> polega na wykorzystaniu [[lista|listy]] i przechodzeniu jej w koło, usuwając co <math>k</math>-ty odwiedzony element<ref>{{Cytuj książkę |nazwisko = Knuth |imię = Donald |tytuł = Sztuka programowania |miejsce = Warszawa |data = 2002 |tom = 1 |tytuł tomu = Algorytmy podstawowe |isbn = 83-2042-540-9 |wydawca = Wydawnictwa Naukowo-Techniczne}}</ref>. Opisano też rozwiązania, działające w <math>O(n \log n)</math> i <math>O(n \log k),</math> wykorzystujące zamiast listy [[binarne drzewo poszukiwań|binarne drzewa poszukiwań]]<ref>{{Cytuj książkę |nazwisko = Knuth |imię = Donald |tytuł = Sztuka programowania |miejsce = Warszawa |data = 2002 |tom = 3 |tytuł tomu = Sortowanie i wyszukiwanie |isbn = 83-2042-554-9 |wydawca = Wydawnictwa Naukowo-Techniczne}}</ref>{{r|nlogm}}.

Szybsze rozwiązanie, działające w złożoności <math>O(n),</math> przewiduje wykorzystanie [[programowanie dynamiczne|programowania dynamicznego]]. Niech <math>L(n)</math> oznacza pozycję bezpieczną przy wybranym <math>k.</math> Jeżeli numerujemy, zaczynając od <math>1,</math> to osoba o <math>s</math> pozycji od niej znajduje się na pozycji <math>((s-1)\bmod n)+1.</math> Gdy zabijemy osobę na <math>k</math>-tej pozycji, zostajemy z kręgiem złożonym z <math>n-1</math> osób i zaczynamy odliczać od osoby, która w oryginalnym problemie stała na pozycji <math>(k\bmod n)+1.</math> Biorąc pod uwagę zmianę numeracji w nowym kręgu, otrzymujemy następującą rekurencję<ref name="dynamic">{{Cytuj stronę |url = http://giocc.com/a-dynamic-programming-solution-to-the-josephus-problem.html |tytuł = A Dynamic Programming Solution to the Josephus Problem |autor = Gio Carlo Cielo |data = 2012-03-27 |język = en |archiwum = https://web.archive.org/web/20170529181440/http://www.giocc.com/a-dynamic-programming-solution-to-the-josephus-problem.html |zarchiwizowano = 2017-05-29 |data dostępu = 2017-06-09}}</ref><ref>{{Cytuj stronę |url = http://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/ |tytuł = Set 1 (A O(n) Solution) |praca = Josephus problem |opublikowany = GeeksforGeeks |język = en |data dostępu = 2017-06-09}}</ref>:
: <math>J(n) = \begin{cases}
    1 & \mbox{dla } n = 1, \\
    ((J(n-1)+k-1) \bmod n)+1 & \mbox{dla } n > 1.
\end{cases}</math>

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{Pismo Delta | url = 2024/09/problem-flawiusza/ | autor = Dagna Czubla i Marcin Wierzbiński | tytuł = Problem Flawiusza | data = wrzesień 2024 | data dostępu = 2024-09-03 }}
* [http://www.cut-the-knot.org/recurrence/flavius.shtml Symulacja problemu na cut-the-knot.org] {{lang|en}}

[[Kategoria:Kombinatoryka]]