Problem Józefa Flawiusza

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: na okręgu ustawiamy $n$ obiektów, następnie eliminujemy co $k$-ty obiekt, tak długo, aż zostanie tylko jeden. Należy wskazać obiekt, który pozostanie.

Dla $k=2$ istnieje wzór jawny, a dla pozostałych $k$ istnieją algorytmy rozwiązujące problem między innymi w złożonościach czasowych $O(n)$ i $O(k\log n)$.

Historia i odmiany problemu

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:

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.

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. 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ć.

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.

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.

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ć.

Rozwiązania

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

k=2

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

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

$J(2n)=2J(n)-1\quad {\mbox{dla }}n\geqslant 1$

(1)

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

$J(2n+1)=2J(n)+1\quad {\mbox{dla }}n\geqslant 1$

(2)

Łącząc te równania z $J(1)=1$ otrzymujemy wzór rekurencyjny, który pozwala na policzenie $J(n)$ w złożoności obliczeniowej $O(\log n).$ Można wykorzystać ten wzór do stablicowania funkcji $J(n)$:

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
$J(n)$	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:

$J(2^{m}+l)=2l+1\quad {\mbox{dla }}m\geqslant 0\wedge 0\leqslant l<2^{m}$

(3)

Wzór (3) można udowodnić za pomocą indukcji ze względu na $m.$ Gdy $m=0,$ $l$ musi być równe $0,$ więc baza indukcji sprowadza się do $J(1)=1,$ co jest prawdą.

Jeśli $l$ jest parzyste, to:

$J(2^{m}+l)=2J\left(2^{m-1}+{\frac {l}{2}}\right)-1=2\left({\frac {2l}{2}}+1\right)-1=2l+1$

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

$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,$

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

$J(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1.$

Można też udowodnić, że $J(n)$ odpowiada obrotowi bitowemu $n$ o jedno miejsce w lewo. Jeśli przedstawimy $n$ w postaci dwójkowej: $n=(b_{m}b_{m-1}\dots b_{1}b_{0})_{2}$ to, wiedząc, że $n=2^{m}+l,$ otrzymamy:

$n=(1b_{m-1}b_{m-2}\dots b_{1}b_{0})_{2}$

$l=(0b_{m-1}b_{m-2}\dots b_{1}b_{0})_{2}$

$2l=(b_{m-1}b_{m-2}\dots b_{1}b_{0}0)_{2}$

$2l+1=(b_{m-1}b_{m-2}\dots b_{1}b_{0}1)_{2}$

$J(n)=(b_{m-1}b_{m-2}\dots b_{1}b_{0}b_{m})_{2}$

Ostatni krok wynika z tego, że $J(n)=2l+1,$ a $b_{m}=1$.

Implementacja

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

Problemem, który pozostaje otwarty, jest wyznaczanie $J(n)$ w sytuacji, gdy $k\neq 2.$ Rozwiązanie intuicyjne, działające w złożoności $O(nk),$ polega na wykorzystaniu listy i przechodzeniu jej w koło, usuwając co $k$-ty odwiedzony element. Opisano też rozwiązania, działające w $O(n\log n)$ i $O(n\log k),$ wykorzystujące zamiast listy binarne drzewa poszukiwań.

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

$J(n)={\begin{cases}1&{\mbox{dla }}n=1,\\((J(n-1)+k-1){\bmod {n}})+1&{\mbox{dla }}n>1.\end{cases}}$

Linki zewnętrzne

• Symulacja problemu na cut-the-knot.org (ang.)