Problem Józefa Flawiusza

Problem Józefa Flawiusza

Problem Józefa Flawiusza, znany również jako permutacja Józefa Flawiusza, jest teoretycznym zagadnieniem z zakresu kombinatoryki, które ma zastosowanie w informatyce. Polega na ustawieniu $n$ obiektów w okręgu i eliminacji co $k$-tego obiektu, aż pozostanie tylko jeden. Celem jest wskazanie obiektu, który przetrwa. Dla $k=2$ istnieje wzór jawny, a dla innych wartości $k$ dostępne są algorytmy o złożoności czasowej $O(n)$ oraz $O(k\; log\; n)$.

Historia i odmiany problemu

Nazwa problemu pochodzi od Józefa Flawiusza, historyka rzymsko-żydowskiego, który opisał sytuację, w której wraz z grupą powstańców został otoczony. Aby uniknąć pojmania, postanowili losować, kto z nich ma zabić kolejnego, aż zostanie tylko jedna osoba. Flawiusz przeżył, co zainspirowało matematyków do sformułowania tego problemu.

Pierwszym matematykiem, który przekształcił tę historię w problem matematyczny, był Claude Gaspard Bachet de Méziriac w XVI wieku. W kolejnych wersjach problemu zmieniała się liczba uczestników oraz zasady eliminacji.

Rozwiązania

W przypadku $k=2$, po pierwszej rundzie eliminacji uczestnicy o numerach parzystych są usuwani. Wprowadza to rekurencyjne wzory, które pozwalają na obliczenie pozycji ocalałego:

• $J(2n)\; =\; 2J(n)\; –\; 1$ dla $n\; geqslant\; 1$,
• $J(2n+1)\; =\; 2J(n)\; +\; 1$ dla $n\; geqslant\; 1$.

Ogólny wzór jawny dla $J(n)$ można zapisać jako:

$J(n)\; =\; 2(n\; –\; 2^\{lfloor\; log\_2(n)\; rfloor\})\; +\; 1.$

Implementacja

Przykładowa implementacja w języku Python 3:

def flawiusz(n):
l = n – (1 << (n.bit_length() - 1)) wynik = 2*l + 1 return wynik

Przypadek ogólny

Problem pozostaje otwarty dla wartości $k\; neq\; 2$. Istnieją różne podejścia do rozwiązania, w tym algorytmy o złożoności $O(nk)$, $O(n\; log\; n)$ oraz $O(n)$ oparte na programowaniu dynamicznym. Dla dowolnego $k$, rekurencja może być zapisana jako:

Linki zewnętrzne

• Symulacja problemu na cut-the-knot.org