Josephus-Problem

Josephus-ProblemDer jüdische Historiker Flavius Josephus (37-95) berichtete davon, dass er mit 40 anderen Juden vor den Römern in einen Keller flüchtete. Um dem Feind nicht in die Hände zu geraten, beschlossen sie, sich gegenseitig umzubringen – nur Josephus war dagegen. Deshalb schlug er vor, sich in einem Kreis aufzustellen und jeweils jeden Dritten auf der Stelle zu erschlagen. Da er sich „geschickt“ in den Kreis stellte, blieb er als Letzter übrig und überlebte. In Auswertung der Überlieferung bedeutet dies:

N Personen (im Programm von 3 bis 20000) stehen in einem Kreis. Beginnend bei der ersten Person wird in Schritten von k abgezählt, wobei eine erreichte Person ausscheidet. Das Ganze wird so lange durchgeführt, bis nur noch eine Person übrig bleibt. Dieses Verfahren wird in der Literatur als Josephus-Problem bezeichnet.

Dieses Programm berechnet für die Personenzahl und die Zählweite die Reihenfolge des Ausscheidens einzelner Personen. Kann die 1. Person die Schrittweite festlegen, so gelingt es ihr, bei einer Vielzahl von Personenzahlen zu erreichen, dass sie selbst als Letzte übrig bleibt. Für 60 Personen müsste sie z.B. eine Schrittweite von 34 festlegen, bei 59 Personen eine Schrittweite von 46 … Allerdings gibt es beispielsweise bei 55 Personen keine solche Lösung. Die optimale Lösung (bei mehreren die kleinste) ermittelt das Programm zusätzlich.

Im rechten Teil des Fensters wird das Abzählen grafisch dargestellt. An den Rollbalken können Sie maximal 50 Personen und die entsprechende Abzählweite einstellen.

Wählen Sie nun mit einem Mausklick die von Ihnen gewünschte Person aus, beginnt das Programm zu streichen. Wenn Sie richtig wählen, bleiben Sie am Ende sogar übrig.

Übrigens: Josephus musste sich als 31. in den Kreis stellen, um zu überleben. Wäre das Abzählen bei ihm begonnen worden, hätte er als Abzählweite 16 vorschlagen müssen.
Allerdings ist die von Josephus erfundene Geschichte über die Jahrhunderte inhaltlich verändert worden. Im Originaltext waren es mit ihm zusammen 40 Juden, die sich durch Losentscheid paarweise umbrachten, bis er sich mit dem Letzten „einigte“. Diese Abänderung der Gesamtzahl ist für die mathematische Behandlung notwendig, da für 40 Personen keine optimale Abzählweite existiert.

Josephus wurde durch seine irrwitzigen Schilderungen von geschichtlichen Ereignissen bekannt, wie zum Beispiel dem Tod des Kaisers Titus. Historische Tatsachen ersetzte er gern durch sensationslüsterne, horrorartige, von ihm erfundene Erzählungen. Er war wohl der erste „Boulevard-Journalist“ der Menschheit.

Die Aufgabe des Josephus ist in vielen Variationen überliefert. Spätere Geschichten handeln von Seefahrern, die im Sturm die Hälfte der Mannschaft über Bord werfen müssen. Die Frage ist dann, an welchen Positionen im Kreis die Plätze sicher sind.

Eine oft überlieferte historische Version handelt von 15 Christen und 15 „Ungläubigen“ auf einem Schiff, jeder zehnte wird vom Kapitän ausgezählt, die nicht ausgezählte Hälfte der 30 Passagiere darf an Bord bleiben.

Die sicheren Positionen für die Christen (warum eigentlich die Christen?) ergeben sich, wenn wir C für Christen und X für Ungläubige setzen, die Folge der sicheren Positionen zu

XXXXCCCCCXXCXXXCXCCXXCCCXCCXXC

Im englischen Sprachraum ist das Rätsel als „Saint Peter’s Game“ überliefert. Hier werden 15 Whiskey-Trinker und 15 Abstinenzler betrachtet.

Wesentlich martialischer ist die mittelalterliche Variante „Ludus Sancti Petri“. Hier geht es um 15 Christen und 15 Juden und entsprechend der reaktionären Position sollen natürlich die Christen überleben. Eine jüdische Version von Ibrahim ben Meir Ezra favorisiert die Juden, eine arabische Version natürlich die Moslems.
In einer japanischen Variante will eine Stiefmutter ihre Stiefkinder los werden; auch nicht gerade harmlos. In Indien erzählt man von 15 ehrbaren Männern und 15 Dieben.

Josephus-Problem

Download

Das Josephus-Problem ist als Einzelprogramm ladbar.

Der Delphi-Quelltext des Einzelprogramms kann unter Quelltexte oder hier direkt geladen werden.