Problem Józefa Flawiusza

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Dla istnieje wzór jawny[1], a dla pozostałych istnieją algorytmy rozwiązujące problem między innymi w złożonościach czasowych i [2][3][4].

Historia i odmiany problemu[edytuj]

Nazwa nawiązuje do postaci 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ęż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 Wojnie żydowskiej[5]:

Quote-alpha.png
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[5].

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[6][7]. 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ć[8].

Inne źródło podaje, że uczestników było łącznie 41, a Flawiusz i wtajemniczony przez niego powstaniec ustawili się odpowiednio na 31. i 16. pozycji. W tej wersji problemu należy wyznaczyć dwóch ostatnich ludzi, którzy pozostaną przy życiu[9]. Wersja przedstawiona w Matematyce konkretnej zakłada, że zabijany jest co drugi uczestnik. Jest to jedyna wersja problemu, dla której udowodniono istnienie wzoru jawnego[10][11].

Istnieje też pokrewny problem, który został wymyślony w średniowieczu. 15 Turków i 15 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ć[9][7].

Rozwiązania[edytuj]

Niech oznacza początkową liczbę osób w kręgu, a krok w każdej iteracji (po każdej egzekucji osób po poprzednio wybranej jest pomijanych, a -ta zabijana). Osoby w kręgu numerowane są od liczbami naturalnymi od do , a jako pierwszy zabijany jest uczestnik o numerze .

k=2[edytuj]

W tej sekcji podane jest rozwiązanie problemu w sytuacji, gdy . Niech oznacza pozycję pozostałego uczestnika w sytuacji, gdy na początku było ich .

Pierwsza runda wokół okręgu eliminuje wszystkich uczestników o numerach parzystych. Jeżeli 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 uczestnikami, po pierwszej rudzie sytuacja wygląda tak, jakbyśmy zaczynali z uczestnikami o podwojonych i zmniejszonych o 1 numerach. Otrzymujemy więc[12]:

(1)

Jeżeli zaczynamy z uczestnikami i wykonujemy jedną rundę, to uczestnik o numerze jest eliminowany zaraz po uczestniku o numerze . Ponownie zostajemy z osobami, jednak tym razem ich numery są podwojone i powiększone o 1, a więc[13]:

(2)

Łącząc te równania z otrzymujemy wzór rekurencyjny, który pozwala na policzenie w złożoności obliczeniowej . Można wykorzystać ten wzór do stablicowania funkcji [13]:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
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[13]:

(3)

Wzór (3) można udowodnić za pomocą indukcji ze względu na . Gdy , musi być równe , więc baza indukcji sprowadza się do , co jest prawdą[14].

Jeśli jest parzyste, to:

ze względu na wzór (1) i założenie indukcyjne. Podobnie udowadniamy dla nieparzystych:

co kończy dowód. Przekształcając wzór (3) otrzymujemy wzór jawny[15]:

Można też udowodnić, że odpowiada obrotowi bitowemu o jedno miejsce w lewo. Jeśli przedstawimy w postaci dwójkowej: to, wiedząc, że , otrzymamy[16]:

Ostatni krok wynika z tego, że , a [16].

Implementacja[edytuj]

Przykładowa implementacja powyższego rozwiązania w języku Python 3:

def flawiusz(n):
    # Wyznaczenie l
    l = n - (1 << (n.bit_length() - 1))

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

Przypadek ogólny[edytuj]

Problemem, który pozostaje otwarty, jest wyznaczanie w sytuacji, gdy . Rozwiązanie intuicyjne, działające w złożoności , polega na wykorzystaniu listy i przechodzeniu jej w koło, usuwając co -ty odwiedzony element[17]. Opisano też rozwiązania, działające w i , wykorzystujące zamiast listy binarne drzewa poszukiwań[18][4].

Szybsze rozwiązanie, działające w złożoności , przewiduje wykorzystanie programowania dynamicznego. Niech oznacza pozycję bezpieczną przy wybranym . Jeżeli numerujemy zaczynając od , to osoba o pozycji od niej znajduje się na pozycji . Gdy zabijemy osobę na -tej pozycji, zostajemy z kręgiem złożonym z osób i zaczynamy odliczać od osoby, która w oryginalnym problemie stała na pozycji . Biorąc pod uwagę zmianę numeracji w nowym kręgu, otrzymujemy następującą rekurencję[2][19]:

Przypisy

  1. Problem Józefa Flawiusza. W: Ronald Graham: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2006, s. 23-32. ISBN 83-01-14764-4.
  2. a b Gio Carlo Cielo: A Dynamic Programming Solution to the Josephus Problem (ang.). 2012-03-27. [dostęp 2017-06-09].
  3. Задача Иосифа (ros.). MAXimal, 2008-06-11. [dostęp 2017-06-09].
  4. a b Errol Lloyd. An O(n log m) Algorithm for the Josephus Problem.. „Journal of Algorithms”, s. 262-270, 1983-09 (ang.). 
  5. a b Józef Flawiusz: Wojna żydowska. s. 119-122.
  6. James Dowdy, Michael Mays. Josephus permutations. „Journal of Combinatorial Mathematics and Combinatorial Computing”. 6, 1989-01 (ang.). 
  7. a b Claude Gaspard Bachet de Méziriac: Problemes Plaisants ed Delectables qui se font par les Nombres. 1612, s. 174. (fr.)
  8. I.N. Herstein, Irving Kaplansky: Matters Mathematical. Harper and Row, 1974, s. 121-126. (ang.)
  9. a b W. W. Rouse Ball: Mathematical Recreations and Essays. Macmillan, 1896. (ang.)
  10. Problem Józefa Flawiusza. W: Ronald Graham: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2006, s. 23. ISBN 83-01-14764-4.
  11. Ari Ben-Menahem: Historical Encyclopedia of Natural and Mathematical Sciences. T. 1. s. 424.
  12. Problemy rekurencyjne. W: Ronald Graham: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2006, s. 24. ISBN 83-01-14764-4.
  13. a b c Problemy rekurencyjne. W: Ronald Graham: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2006, s. 24-25. ISBN 83-01-14764-4.
  14. Problemy rekurencyjne. W: Ronald Graham: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2006, s. 25-26. ISBN 83-01-14764-4.
  15. Josephus Problem (ang.). Wolfram MathWorld. [dostęp 2017-06-09].
  16. a b Problemy rekurencyjne. W: Ronald Graham: Matematyka konkretna. Warszawa: Wydawnictwo Naukowe PWN, 2006, s. 26-27. ISBN 83-01-14764-4.
  17. Donald Knuth: Sztuka programowania. T. 1: Algorytmy podstawowe. Warszawa: 2002. ISBN 83-2042-540-9.
  18. Donald Knuth: Sztuka programowania. T. 3: Sortowanie i wyszukiwanie. Warszawa: 2002. ISBN 83-2042-554-9.
  19. Set 1 (A O(n) Solution) (ang.). W: Josephus problem [on-line]. GeeksforGeeks. [dostęp 2017-06-09].

Linki zewnętrzne[edytuj]