Josephus-Problem

Das Josephus-Problem oder die Josephus-Permutation ist ein theoretisches Problem aus der Informatik oder Mathematik (Kombinatorik).

Es werden $n$ nummerierte Objekte im Kreis angeordnet; dann wird, beginnend mit der Nummer $k$, jedes $k$-te Objekt entfernt, wobei der Kreis immer wieder geschlossen wird. Die Reihenfolge der entfernten Objekte wird als Josephus-Permutation bezeichnet.

Ziel dieses Problems ist es, bei gegebenem $n$ und $k$ das letzte Objekt der Permutation zu bestimmen.

Geschichte

Das Problem wurde nach dem jüdischen Historiker Flavius Josephus benannt, welcher sich 67 n. Chr. beim Kampf um die galiläische Stadt Jotapata mit 40 weiteren Männern in einer Höhle vor den Römern versteckt hielt (insgesamt also 41 Personen). Er berichtet darüber in seinem Buch Jüdischer Krieg (Buch 3, Kapitel 8). Als das Versteck verraten wurde, forderten die Römer sie auf, sich in Gefangenschaft zu ergeben. Seine Gefolgsleute zogen allerdings vor, durch kollektiven Suizid zu sterben, wobei das Los über die Reihenfolge entschied. Durch Glück waren Josephus und ein weiterer Mann die Letzten und ergaben sich. Später wurde daraus eine Denksportaufgabe gemacht, in dem sich alle im Kreis aufstellen und jeder 3. durch seinen rechten Nachbarn getötet werden sollte. Josephus stellte sich in diesem Spezialfall an die 16. Stelle, blieb damit als Vorletzter übrig und überwältigte den schwächeren Mann an der 31. Position. Beide ergaben sich den Römern und überlebten.

Nach Wilhelm Ahrens hat Gerolamo Cardano in seinem Werk Practica arithmeticae (1539) den Problemtyp Josephsspiel (Ludus Josephi) genannt, er war aber älter. Nach Moritz Cantor findet es sich in der Handschrift von Nicolas Chuquet La triparty en la science des nombres (Lyon 1484). Das Problem wird auch von Claude Gaspard Bachet de Méziriac (Problèmes plaisans et delectables, 1612) behandelt, der auch eine Variante angibt: 15 Türken und 15 Christen sind auf einem Schiff im Sturm. Der Kapitän muss 15 von ihnen opfern damit das Schiff nicht sinkt und lässt sie in einer Reihe aufstellen, wobei jeder neunte geopfert wird.

Lösung

Das Problem wird hier gelöst für den Fall, dass jedes 2. Element entfernt wird ($k=2$). Für den allgemeinen Fall $k\neq 2$ folgt eine Lösung unten. Die Lösung wird mittels Rekursion hergeleitet. $f(n)$ bezeichne das letzte Element der Permutation, wenn anfangs $n$ Elemente vorhanden waren (mit $k=2$). Im ersten Durchlauf werden alle geradzahligen Elemente entfernt. In der zweiten Runde werden die Elemente entfernt, die an der neuen 2., 4. usw. Position stehen, so als hätte es keine erste Runde gegeben. Wenn die Anfangsanzahl von Elementen gerade ist, dann war das Element $x$ aus der zweiten Runde in der ersten Runde an Position $2x-1$. Das Element $f(2n)$ war ursprünglich auf Position $2f(n)-1$. Das ergibt folgende Rekursionsformel:

$f(2n)=2f(n)-1.\,$

Wenn die Elementanzahl anfangs ungerade ist, dann wird in der zweiten Runde das ursprünglich erste Element entfernt, aber auch hier wird dann das neue 2., 4. usw. Element entfernt. In diesem Fall ergibt sich, dass Element $x$ in der ersten Runde an Position $2x+1$ war. Daraus folgt die Rekursionsformel:

$f(2n+1)=2f(n)+1.\,$

Wenn man die Werte für $n$ und $f(n)$ tabellarisch darstellt, sieht man ein Muster:

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

Diese Tabelle lässt vermuten, dass $f(n)$ eine aufsteigende Folge ungerader Zahlen ist, welche wieder mit $f(n)=1$ startet, wenn der Index $n$ eine Zweierpotenz ist. Wenn man $m$ und $l$ so wählt, dass $n=2^{m}+l$ und $0\leq l<2^{m}$, dann folgt $f(n)=2\cdot l+1$. Es ist offensichtlich, dass die Werte aus der Tabelle diese Gleichung erfüllen. Nachfolgend erfolgt der Beweis durch vollständige Induktion.

Behauptung: Wenn $n=2^{m}+l$ und $0\leq l<2^{m}$, dann folgt $f(n)=2l+1$.

Beweis: Vollständige Induktion über $n$. Der Fall $n=1$ ist wahr. Man betrachte die Fälle für gerades $n$ und ungerades $n$ getrennt.

Wenn $n$ gerade, dann wähle man $l_{1}$ und $m_{1}$ so, dass $n/2=2^{m_{1}}+l_{1}$ und $0\leq l_{1}<2^{m_{1}}$. Es gilt $l_{1}=l/2$. Wir haben $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$, bei der die zweite Gleichung aus der Induktionsannahme folgt.

Wenn $n$ ungerade, dann wähle man $l_{1}$ und $m_{1}$ so, dass $(n-1)/2=2^{m_{1}}+l_{1}$ and $0\leq l_{1}<2^{m_{1}}$. Es gilt $l_{1}=(l-1)/2$. Wir haben $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$, bei der die zweite Gleichung ebenfalls aus der Induktionsannahme folgt. Damit ist die Behauptung bewiesen.

Die eleganteste Form der Lösung folgt aus der binären Repräsentation von $n$: $f(n)$ kann durch eine 1-Bit-Linksrotation von $n$ selbst ermittelt werden. Wenn man $n$ binär als $n=b_{0}b_{1}b_{2}b_{3}\dots b_{m}$ repräsentiert, dann ist die Lösung gegeben als $f(n)=b_{1}b_{2}b_{3}\dots b_{m}b_{0}$. Der Beweis folgt aus der Repräsentation von $n$ als $2^{m}+l$.

In geschlossener Form lautet die Lösung für den Fall k=2:

$f(n)=1+2n-2^{1+\lfloor \ln n\rfloor }$

mit der Gaußklammer (Abrundungsfunktion) $\lfloor ...\rfloor$

Es gibt auch eine Lösung in geschlossener Form für den Fall k=3.

Die dynamische Programmierung ist der einfachste Weg, dieses Problem für den allgemeinen Fall zu lösen.

Diese Methode verwendet die Rekursionsformel:

$f(n,k)=(f(n-1,k)+k-1){\bmod {n}}+1$, mit $f(1,k)=1$

welche offensichtlich ist, wenn man berücksichtigt, wie sich die Nummer des letzten Elements ändert, wenn man von $n-1$ nach $n$ wechselt. Diese Methode hat eine Laufzeit von $O(n)$, aber für kleine $k$ und große $n$ gibt es einen anderen Ansatz. Dieser zweite Ansatz verwendet auch die dynamische Programmierung, erfordert aber nur eine Laufzeit von $O(k\log n)$. Er entfernt die k., 2k., ..., $\lfloor n/k\rfloor$. Elemente in einem Schritt und ändert dann die Nummerierung.

Implementierung

Der folgende Algorithmus realisiert das Problem rekursiv nach der obigen Rekursionsformel für den Fall k=2 und besitzt eine Laufzeit von O(log(n)).

int josephus(int n) 
{
    if(n == 1) 
        return 1;

    if((n%2) == 0) 
        return 2 * josephus(n / 2) - 1;

    if((n%2) == 1) 
        return 2 * josephus((n - 1) / 2) + 1;
}

Gemäß der geschlossenen Formel f(n)=2*l + 1 lässt sich der folgende nicht-rekursive Algorithmus angeben. Seine Laufzeit liegt in O(1).

int josephus(int n)
{
    m = floor( log2(n) );
    l = n - 2^m;
    j = 2*l + 1;

    return j;
}

Literatur

• Paul Yiu: Recreational Mathematics, Florida Atlantic University: Department of Mathematics (Als PDF in englischer Sprache verfügbar; 868 kB)
• Walter William Rouse Ball, Harold Scott Macdonald Coxeter: Mathematical Recreations and Essays, Dover, 1987. Seiten 32–36, ISBN 0-486-25357-0
• Ronald L. Graham, Donald E. Knuth und Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science, Massachusetts, 1994. Seiten 8–16, ISBN 978-0-201-55802-9
• James Dowdy, Michael E. Mays: Josephus Permutations, Journal of Combinatorial Mathematics and Combinatorial Computing, Band 6, 1989, S. 125–130

Weblinks

• Lorenz J. Halbeisen: The Josephus Problem.
• Josephus Flavius game bei Cut-the-knot