Josephus-Problem

In der Informatik und Mathematik ist das Josephus-Problem (oder die Josephus-Permutation ) ein theoretisches Problem, das mit einem bestimmten Auszählspiel zusammenhängt . Solche Spiele dienen dazu, eine Person aus einer Gruppe auszuwählen, z. B. Ene mene miste .

In dem speziellen Abzählspiel, das dem Josephus-Problem zugrunde liegt, stehen mehrere Personen im Kreis und warten auf ihre Hinrichtung. Das Zählen beginnt an einem festgelegten Punkt im Kreis und verläuft in einer bestimmten Richtung im Kreis herum. Nachdem eine bestimmte Anzahl von Personen übersprungen wurde, wird die nächste Person hingerichtet. Dieser Vorgang wird mit den verbleibenden Personen wiederholt, beginnend mit der nächsten Person, in derselben Richtung und mit derselben Anzahl übersprungener Personen, bis nur noch eine Person übrig ist, die freigelassen wird.

Das Problem besteht darin , die Position im Ausgangskreis zu wählen, um der Hinrichtung zu entgehen.

Das Problem ist nach Flavius ​​Josephus benannt , einem jüdischen Historiker und Anführer des 1. Jahrhunderts. Laut Josephus' Augenzeugenbericht über die Belagerung von Jodfat wurden er und seine 40 Soldaten von römischen Soldaten in einer Höhle eingeschlossen . Sie zogen den Selbstmord der Gefangennahme vor und beschlossen, sich per Losverfahren den Tod zuzufügen. Josephus berichtet, dass er und ein anderer Mann durch Glück oder möglicherweise durch göttliche Fügung bis zum Schluss ausharrten und sich den Römern ergaben, anstatt sich selbst zu töten. Diese Geschichte findet sich in Buch 3, Kapitel 8, Teil 7 von Josephus' „ Der Jüdische Krieg“ ( er schreibt in der dritten Person über sich selbst ).

Doch selbst in dieser äußersten Not verlor er nicht seine gewohnte Klugheit; er vertraute auf Gottes Vorsehung und setzte sein Leben aufs Spiel [auf folgende Weise]: „Nun“, sagte er, „da ihr beschlossen habt zu sterben, lasst uns unser aller Leben dem Los überlassen. Wer zuerst das Los zieht, soll von demjenigen getötet werden, der das zweite Los gezogen hat, und so soll das Schicksal seinen Lauf nehmen; keiner von uns soll durch seine eigene Hand umkommen, denn es wäre ungerecht, wenn jemand, nachdem die anderen gestorben sind, bereue und sich selbst rette.“ Dieser Vorschlag erschien ihnen sehr gerecht; und nachdem er sie überzeugt hatte, die Angelegenheit durch das Los zu entscheiden, zog er selbst auch eines der Lose. Derjenige, der das erste Los gezogen hatte, bot demjenigen, der das zweite gezogen hatte, seinen Hals dar, da er annahm, der Feldherr würde sogleich unter ihnen sterben; denn sie dachten, der Tod, wenn Josephus nur mit ihnen sterben dürfe, sei süßer als das Leben. Doch er war mit einem anderen bis zum Schluss übriggeblieben, ob dies nun Zufall oder göttliche Fügung war. Und da er weder durch das Los verdammt werden noch, falls er bis zum Schluss übriggeblieben wäre, seine rechte Hand mit dem Blut seiner Landsleute beflecken wollte, überredete er ihn, ihm Treue zu schwören und so gut wie möglich zu leben.

Die genauen Details des bei dieser Leistung angewandten Mechanismus sind recht vage. Laut James Dowdy und Michael Mays ^{[ 2 ]} schlug Claude Gaspard Bachet de Méziriac 1612 vor, die Männer im Kreis aufzustellen und in Dreiergruppen zu zählen, um die Reihenfolge des Ausscheidens festzulegen. ^{[ 3 ]} Diese Geschichte wurde oft erzählt, und die genauen Details variieren je nach Quelle erheblich. So berichten Israel Nathan Herstein und Irving Kaplansky (1974), dass Josephus und 39 seiner Gefährten im Kreis standen und jeder siebte Mann ausschied. ^{[ 4 ]} Eine Geschichte des Problems findet sich in S. L. Zabells Leserbrief an den Herausgeber des Fibonacci Quarterly . ^{[ 5 ]}

As to intentionality, Josephus asked: “shall we put it down to divine providence or just to luck?”^[6] But the surviving Slavonic manuscript of Josephus tells a different story: that he “counted the numbers cunningly and so managed to deceive all the others”.^[6][7] Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival). It is alleged that he placed himself and the other man in the 31st and 16th place respectively (for k = 3 below).^[8]

A medieval version of the Josephus problem involves 15 Turks and 15 Christians aboard a ship in a storm which will sink unless half the passengers are thrown overboard. All 30 stand in a circle and every ninth person is to be tossed into the sea. The Christians need to determine where to stand to ensure that only the Turks are tossed.^[9] In other versions the roles of Turks and Christians are interchanged.

Graham, Knuth & Patashnik 1989, p. 8 describe and study a "standard" variant: Determine where the last survivor stands if there are n people to start and every second person (k = 2 below) is eliminated.

A generalization of this problem is as follows. It is supposed that every mth person will be executed from a group of size n, in which the pth person is the survivor. If there is an addition of x people to the circle, then the survivor is in the p + mx-th position if this is less than or equal to n + x. If x is the smallest value for which p + mx > n + x, then the survivor is in position (p + mx) − (n + x).^[10]

Im Folgenden bezeichnet die Anzahl der Personen im Ausgangskreis und die Anzahl der Personen pro Schritt, d. h. Personen werden übersprungen und die -te Person wird ausgeführt. Die Personen im Kreis sind von bis nummeriert , wobei die Startposition und die Zählung inklusive ist . ${\displaystyle n}$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle 1}$

Das Problem ist explizit gelöst, wenn jede zweite Person getötet wird (jede Person tötet die Person zu ihrer Linken oder Rechten), d. h. . (Für den allgemeineren Fall wird weiter unten eine Lösung skizziert.) Die Lösung wird rekursiv ausgedrückt . Sei die Position des Überlebenden, wenn anfänglich n Personen vorhanden sind (und ). Im ersten Umlauf sterben alle Personen mit geraden Nummern. Im zweiten Umlauf stirbt die neue zweite Person, dann die neue vierte usw.; es ist, als gäbe es keinen ersten Umlauf. ${\displaystyle k=2}$${\displaystyle k\neq 2}$${\displaystyle f(n)}$${\displaystyle k=2}$

Wenn die anfängliche Anzahl der Personen gerade war, dann befand sich die Person an Position x während des zweiten Umlaufs ursprünglich an Position (für jede Wahl von x ). Sei . Die Person an Position , die nun überlebt, befand sich ursprünglich an Position . Dies führt zu der Rekursionsformel${\displaystyle 2x-1}$${\displaystyle n=2j}$${\displaystyle f(j)}$${\displaystyle 2f(j)-1}$$${\displaystyle f(2j)=2f(j)-1.}$$

Wenn die anfängliche Anzahl der Personen ungerade war , kann man sich vorstellen, dass Person 1 am Ende des ersten Umlaufs stirbt. Im zweiten Umlauf stirbt dann die neue zweite Person, anschließend die neue vierte Person usw. In diesem Fall befand sich die Person an Position x ursprünglich an Position . Daraus ergibt sich die Rekursionsgleichung. ${\displaystyle 2x+1}$$${\displaystyle f(2j+1)=2f(j)+1.}$$

Wenn die Werte tabellarisch erfasst werden und sich ein Muster herauskristallisiert ( OEIS :  A006257 , auch die linke Spalte der blauen Zahlen in der obigen Abbildung): ${\displaystyle n}$${\displaystyle f(n)}$

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

Dies deutet darauf hin, dass es sich um eine aufsteigende ungerade Folge handelt, die immer dann mit n beginnt , wenn der Index n eine Zweierpotenz ist . Wenn also m und l so gewählt werden, dass m = 1 und l = 2 , dann gilt m = 1. Es ist klar, dass die Werte in der Tabelle diese Gleichung erfüllen. Man kann sich auch vorstellen, dass nach dem Tod von l Personen nur noch l Personen übrig sind und die Folge mit der ersten Person beginnt. Diese Person muss der Überlebende sein. Somit gilt m = 1. Im Folgenden wird ein Beweis mittels vollständiger Induktion geführt . ${\displaystyle f(n)}$${\displaystyle f(n)=1}$${\displaystyle n=2^{m}+l}$${\displaystyle 0\leq l<2^{m}}$${\displaystyle f(n)=2l+1}$${\displaystyle 2^{m}}$${\displaystyle 2l+1}$${\displaystyle f(n)=2l+1}$

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

Beweis: Es wird die vollständige Induktion über n angewendet . Der Induktionsanfang ist wahr. Die Fälle, in denen n gerade und ungerade ist, werden separat betrachtet .${\displaystyle n=1}$

Ist n gerade, so wähle und so, dass und . Beachte, dass . ist gegeben, wobei die zweite Gleichheit aus der Induktionsvoraussetzung folgt. ${\displaystyle l_{1}}$${\displaystyle m_{1}}$${\displaystyle n/2=2^{m_{1}}+l_{1}}$${\displaystyle 0\leq l_{1}<2^{m_{1}}}$${\displaystyle l_{1}=l/2}$${\displaystyle f(n)=2f(n/2)-1=2[(2l_{1})+1]-1=2l+1}$

Ist n ungerade, so wähle und so, dass und . Beachte, dass . ist gegeben, wobei die zweite Gleichheit aus der Induktionsvoraussetzung folgt. Damit ist der Beweis abgeschlossen. ${\displaystyle l_{1}}$${\displaystyle m_{1}}$${\displaystyle (n-1)/2=2^{m_{1}}+l_{1}}$${\displaystyle 0\leq l_{1}<2^{m_{1}}}$${\displaystyle l_{1}=(l-1)/2}$${\displaystyle f(n)=2f[(n-1)/2]+1=2[(2l_{1})+1]+1=2l+1}$

l kann gelöst werden, um einen expliziten Ausdruck für zu erhalten : ${\displaystyle f(n)}$$${\displaystyle f(n)=2(n-2^{\lfloor \log _{2}(n)\rfloor })+1.}$$

Die eleganteste Lösungsform verwendet die Binärdarstellung der Größe n : Diese erhält man durch eine zyklische Linksverschiebung von n um ein Bit. Wird n binär als dargestellt , so ergibt sich die Lösung zu . Der Beweis hierfür folgt aus der Darstellung von n als oder aus dem obigen Ausdruck für . ${\displaystyle f(n)}$${\displaystyle n=1b_{1}b_{2}b_{3}\dots b_{m}}$${\displaystyle f(n)=b_{1}b_{2}b_{3}\dots b_{m}1}$${\displaystyle 2^{m}+l}$${\displaystyle f(n)}$

Implementierung: Wenn n die Anzahl der Personen bezeichnet, ist die sichere Position durch die Funktion gegeben , wobei und . ${\displaystyle f(n)=2l+1}$${\displaystyle n=2^{m}+l}$${\displaystyle 0\leq l<2^{m}}$

Wenn die Zahl nun im Binärformat dargestellt wird, bezeichnet das erste Bit den Wert l und die restlichen Bits den Wert l . Zum Beispiel lautet die Binärdarstellung von ⁠ ⁠ :${\displaystyle 2^{m}}$${\displaystyle n=41}$

n = 1 0 1 0 0 1 2 m = 1 0 0 0 0 0 l = 0 1 0 0 1 

/** * @param n die Anzahl der Personen im Kreis * @return die sichere Position derjenigen, die die Hinrichtung überleben * f(N) = 2L + 1 wobei N = 2^M + L und 0 <= L < 2^M */ public int getSafePosition ( int n ) { // Wert von L für die Gleichung finden int valueOfL = n - Integer . highestOneBit ( n ); return 2 * valueOfL + 1 ; }

Die sicherste Position lässt sich am einfachsten mithilfe von Bitoperatoren finden . Dabei wird das höchstwertige gesetzte Bit von n zum niederwertigsten Bit verschoben, um die sichere Position zu erhalten. ^{[ 11 ]} Die Eingabe muss eine positive ganze Zahl sein .

n = 1 0 1 0 0 1 f(n) = 0 1 0 0 1 1 

/** * @param n (41) die Anzahl der Personen im Kreis * @return die sichere Position, die die Ausführung überlebt */ public int getSafePosition ( int n ) { return ~ Integer . highestOneBit ( n * 2 ) & (( n << 1 ) | 1 ); // ---------------------- --- | ------------ // Das erste gesetzte Bit holen | | n um eine Position nach links verschieben und das letzte Bit invertieren // und sein Komplement bilden | | // | | // n mit 2 multiplizieren | // Bitweises UND, um die in beiden Operanden vorhandenen Bits zu kopieren. }

1997 entdeckten Lorenz Halbeisen und Norbert Hungerbühler eine geschlossene Formel für den Fall . Sie zeigten, dass es eine bestimmte Konstante gibt. ${\displaystyle k=3}$

${\displaystyle \alpha \approx 0.8111...}$

die mit beliebiger Genauigkeit berechnet werden kann. Gegeben diese Konstante, wähle m als die größte ganze Zahl, für die gilt (dies ist entweder oder ). Dann ist der letzte Überlebende ${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m})\leq n}$${\displaystyle m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )}$${\displaystyle m^{\prime }-1}$

${\displaystyle f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+(2}$wenn aufgerundet wird, sonst${\displaystyle 1)}$

für alle . ${\displaystyle n\geq 5}$

Als Beispielrechnung geben Halbeisen und Hungerbühler an (was tatsächlich die ursprüngliche Formulierung des Josephus-Problems ist). Sie berechnen: ${\displaystyle n=41,k=3}$

${\displaystyle m^{\prime }\approx \operatorname {round} (\log _{3/2}41/0.8111)\approx \operatorname {round} (9.68)=10}$

${\displaystyle \operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47}$und deshalb${\displaystyle m=9}$

${\displaystyle \operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31}$(Bitte beachten Sie, dass dieser Wert abgerundet wurde.)

${\displaystyle f(n)=3(41-31)+1=31}$

Dies lässt sich überprüfen, indem man jeden einzelnen Durchlauf der Zahlen betrachtet.1 bis41 :

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41

2, 4, 7, 8, 11, 13, 16, 17, 20, 22, 25, 26, 29, 31, 34, 35, 38, 40

2, 4, 8, 11, 16, 17, 22, 25, 29, 31, 35, 38

2, 4, 11, 16, 22, 25, 31, 35

2, 4, 16, 22, 31, 35

4, 16, 31, 35

16, 31

31

Dynamische Programmierung wird im allgemeinen Fall zur Lösung dieses Problems eingesetzt, indem der erste Schritt ausgeführt und anschließend die Lösung des verbleibenden Problems verwendet wird. Beginnt der Index bei eins, verschiebt sich die Person von der ersten Person an Position , wobei n die Gesamtzahl der Personen ist. Sei die Position des Überlebenden. Nachdem die -te Person getötet wurde, verbleibt ein Kreis von , und die nächste Zählung beginnt mit der Person, deren Position im ursprünglichen Problem war . Die Position des Überlebenden im verbleibenden Kreis wäre , wenn die Zählung bei beginnt ; eine Verschiebung, um dem Startpunkt Rechnung zu tragen, ergibt die Rekursionsgleichung ^{[ 12 ]} , die eine einfachere Form annimmt, wenn die Positionen stattdessen von bis nummeriert werden . ${\displaystyle s}$${\displaystyle ((s-1){\bmod {n}})+1}$${\displaystyle f(n,k)}$${\displaystyle k}$${\displaystyle n-1}$${\displaystyle (k{\bmod {n}})+1}$${\displaystyle f(n-1,k)}$${\displaystyle 1}$${\displaystyle (k{\bmod {n}})+1}$$${\displaystyle f(n,k)={\big (}[f(n-1,k)+k-1]{\bmod {n}}{\big )}+1,{\text{ with }}f(1,k)=1,}$$$${\displaystyle g(n,k)=[g(n-1,k)+k]{\bmod {n}},{\text{ with }}g(1,k)=0}$$${\displaystyle 0}$${\displaystyle n-1}$

Dieser Ansatz hat eine Laufzeit von O (n^2 ), aber für kleine und große Systeme gibt es einen anderen Ansatz. Der zweite Ansatz verwendet ebenfalls dynamische Programmierung, hat aber eine Laufzeit von O(n^2) . Er basiert darauf, das Töten der k -ten, 2k - ten, ..., -ten Person als einen Schritt zu betrachten und anschließend die Nummerierung anzupassen. ${\displaystyle O(n)}$${\displaystyle k}$${\displaystyle n}$${\displaystyle O(k\log n)}$${\displaystyle (\lfloor n/k\rfloor k)}$

Dieser verbesserte Ansatz nimmt folgende Form an $${\displaystyle g(n,k)={\begin{cases}0&{\text{if }}n=1,\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k,\\{\begin{Bmatrix}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}+n&{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)<n{\bmod {k}}\\\left\lfloor {\dfrac {k\left(g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)-n{\bmod {k}}\right)}{k-1}}\right\rfloor &{\text{if }}g\left(n-\left\lfloor {\frac {n}{k}}\right\rfloor ,k\right)\geq n{\bmod {k}}\end{Bmatrix}}&{\text{if }}k\leq n.\\\end{cases}}}$$

• FLAMMEN (Spiel)

• Josephus Flavius ​​Spiel (Java Applet) beim Knotenschneiden , wobei jede n- ^te aus 50 (maximal) ausgewählt werden kann.
• Weisstein, Eric W. „Josephus-Problem“ . MathWorld .
• Das Josephus-Problem – Numberphile auf YouTube
• Verallgemeinertes Josephus-Problem