Das Josephus-Problem

Im Jahr 67 n. Chr. wurde die galiläische Stadt Jotapata, die unter der Führung des späteren jüdischen Geschichtsschreibers Josephus (37 - 100) ein Zentrum des antirömischen Widerstandes war, nach 47-tägiger Belagerung von Kaiser Vespasian eingenommen. Josephus und 40 Soldaten versteckten sich in einer Zisterne. Um der Versklavung zu entgehen, wollten die Soldaten sich selbst töten. Josephus, der sie vergeblich beschwor, von ihrem Vorhaben Abstand zu nehmen, wollte wenigstens sich und einen Freund retten. Deshalb schlug er als Tötungsritual den beliebten römischen Brauch des 'decimatio' vor. Dabei bilden die Soldaten einen Kreis, es wird jeweils jeder zehnte Soldat ausgezählt. An welche Stellen des Kreises sollten sich Josephus und sein Freund stellen, um das Ritual zu überleben?

Diese Aufgabe ist in vielen Variationen überliefert. Spätere (kaum weniger blutrünstige) 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 (in anderen Quellen neunte) wird vom Kapitän ausgezählt, die nicht ausgezählte Hälfte der 30 Passagiere darf an Bord bleiben. Nicht schwer zu erraten war die Frage nach den sicheren Positionen für die Christen.
Dabei ergibt sich, wenn wir C für Christen und x für ungläubige setzen, die Folge der sicheren Positionen zu xxxxCCCCCxxCxxxCxCCxxCCCxCCxxC

Solche Rätsel waren früher äußerst beliebt. Man erdachte sogar Merksprüche, um die sicheren Positionen dieses 'Ludus Josephus' leicht im Kopf behalten zu können. Setzt man A=1, E=2, I=3, O=4, U=5, so kann man die Anzahl der Teilgruppen mithilfe der Vokale in Worten verschlüsseln. Ein überlieferter deutscher Spruch ist GOTT SCHUF DEN MANN IN AMALEK DER ISRAEL BEZWANG, was die erste Gruppe 4 Zeichen, die zweite 5 Zeichen, die nächste 2 Zeichen usw. lang macht.

Allerdings stellen auch die Auszählreime von Kindern genau diese Situation - zum Glück unblutig - dar. Die Anzahl der Silben oder Betonungen eines Zählreimes wird zum Zählen im Kreis verwendet. Ein Kind nach dem anderen scheidet aus, bis nur mehr eines übrigbleibt.

Allen diesen Beispielen ist folgendes gemeinsam:

• Eine Gruppe von n Personen bildet einen geschlossenen Kreis
• Von der ersten Person an wird jeweils bis zur k-ten Person weitergezählt. Diese Person scheidet aus, der Kreis wird wieder geschlossen.
• Vom Nachbarn (Nachfolger) der ausgeschiedenen Person beginnend verfährt man wie oben

Ganz allgemein stellt man sich die Frage, in welcher Reihenfolge die Personen ausgeschieden werden.

Werden die Personen durch die Zahlen 1,2,3,...n dargestellt, so ist das Ergebnis eine Umsortierung dieser Liste. Mathematiker sprechen von der Josephus-Permutation L(n,k).

Beim ursprünglichen Josephus-Beispiel wäre L(41,10) die Folge <10,20,30,40,9,21,...,16,31>

Wir wollen die Josephus-Permutationen für gegebenes n und k berechnen!

1.) Eine Listen-Version

Wie könnten wir eine Kette von n Leuten darstellen - am einfachsten wohl als Folge [1,2,3,4,...n]. In Python gesprochen range(1,n+1)

Wie können wir das weiterzählen realisieren? Etwa dadurch, dass dir die Person, die grade dran war, vom Anfang der Liste entfernen und hinten anfügen. Das ergibt dann [2,3,4,...,n,1]

Und wenn die Person ausgezählt wird? Dann wird sie einfach nicht hinten angefügt!

Was muss man zur Durchführung also wissen:

• die Liste der men Leute
• die Schrittweite k des Auszählens
• den Zähler i, wie weit man schon gezählt hat
• eine Liste out, in der wir die ausgezählten Nummern sammeln. Freilich könnte unsere Funktion die ausgezählte Nummer einfach nur am Bildschirm ausgeben. Die Erstellung der Liste erlaubt uns aber eine eventuell folgende mathematische Analyse.
  

Damit müsste unsere Funktion joseph(men,k,i,out) heißen!

Du kannst hier die fertige Version 1 bekonnen!

2.) Eine mathematischere Version

Das Übergeben der Listen beim einfachen Weiterzählen scheint übertriebener Aufwand zu sein. Wir können doch sofort berechnen, was die nächste auszusondernde Position ist: wenn wir einen Zeigen pos benutzen, der auf die aktuelle Position zeigt, dann liegt die nächste interessante Position ganz einfach bei pos+k. Nur müssen wir aufpassen, dass wir nicht rechts über das Ende der Liste hinausgelangen - da die Liste mit Index 0 beginnt, können wir einfach mit einer Modulo-Berechnung den Ort richtig finden: (pos+k)%len(personenliste)

Noch ein Fallstrick liegt verborgen: wenn pos auf die ausgesonderte Position zeigt, und diese aber soeben entfernt wurde, rutscht die Liste um ein Element zusammen - wir müssen also (pos+k-1)%len(personenliste) programmieren.

Und die Startnummer ist nicht mehr 1, sondern der Index Null.

Du kannst hier die fertige Version 2 bekonnen!

Dieses Programm läuft schneller, doch haben wir einige mathematische Tricks gebraucht und ziemlich trickreich nachdenken müssen - so intuitiv wie Lösung 1 ist diese Version nicht mehr!

3.) Eine objektorientierte Version

Lassen wir doch die Männer selbst agieren! Wir bringen ihnen nur die Spielregeln bei, damit sie den Auszählvorgang durchführen können.

Was muss jeder Mann sofort wissen: seinen Namen und die Schrittweite k. Das sind Klassenattribute bei der Erzeugung des Objektes

Was muss jeder Mann danach mitgeteilt bekommen: seinen Vorgänger und seinen Nachfolger, damit eine kreisförmige Anordnung gebildet werden kann. Ebenfalls Attribute.

Was muss ein Mann können (Methoden):

• weiterzählen - das heißt den Nachfolger mit einen um 1 erhöhten Zahl weitermachen lassen.
• sich aus dem Kreis nehmen, wenn er ausgezählt wurde. Er hängt einfach Vorgänger und Nachfolger zusammen.
• sich als Sieger fühlen, wenn man allein übriggeblieben ist

Du kannst hier die fertige Version 3 bekonnen!

Forschung

• Wenn 10 Personen mit Schrittweite 4 ausgezählt werden erhält man <1,5,9,..>. Wenn die Schrittweite 10+4=14 beträgt - geht man dann nur einmal sinnlos im Kreis herum, oder ändert das die Folge
• Mathematisches Denken: können alle Ergebnisse für unterschiedliche k verschieden sein? (Idee: wie viele Permutatine gibt es, wie viele k?). Kann man zu einem k ein anderes finden, das die selbe Josephus-Permutation ergibt?
• Wir können die bisherige Fragestellung umdrehen: wenn wir eine Umordnung von <1,2,3,..n> vorgeben, gibt es dann ein k, das diese Umordnung als Auszählfolge liefert?
• Rein mathematisch ist das Josephus-Problem höchst interessant, doch höchst schwer zu lösen!
  
  
• Ein reicher Farmer hat 30 Kinder. 15 von seiner verstorbenen ersten Frau, 15 von seiner jetzigen. Als es um die Verteilung des Erbes geht, schlägt die Frau eine Abzähltechnik wie bei Josephus vor, wobei jedes 10. Kind ausgezählt wird. Das letzte Kind soll der Haupterbe sein. Der Mann willigt ein, und stellt zu seiner Überraschung fest, dass von den 14 bisher ausgezählten Kindern alle von seiner ersten Frau sind und das nächste ebenfalls nicht von seiner jetzigen Frau wäre. Das scheint ihm seltsam, und er schlägt vor, nun die Zählreihenfolge einfach umzukehren. Die Frau willigt ein, da die Chancen für ihre Kinder doch 15 zu 1 stehen. Wer wird Haupterbe?
  
  
• Nimm 5 Christen und 5 Ungläubige xCxCCxCxCx. Aufgabe: beginnend bei Position a soll jeder k-te Mann ausgesondert werden, sodass alle Christen übrigbleiben. Beginnend bei b sollen nach Aussonderung jedes h-ten Mannes alle Ungläubigen übrigbleiben. Finde a,b,k,h! (Antwort: 1,9,11,29)
  
  
• k sei fix gegeben. Für welche n ist der letzte ausgesonderte Mann die ursprüngliche Nummer 1?
  Sei N so ein n. Welcher Mann bleibt bei N+1, N+2,.. Leuten übrig?
• nimm k=2, n=2**M eine Zweierpotenz. Welcher Mann überlebt bei diesen n? welcher bei n+1, n+2,..
  
  
• Wenn der Mann an Position p im p-ten Durchgang ausgezählt wird, nennt man p einen Fixpunkt der Permutation. Bestimme Fixpunkte der Permutationen L(n,k)! Beispiel: L(8,1) besitzt nur Fixpunkte, L(8,2) keinen einzigen
• Finde L(n,k) mit besonders vielen Fixpunkten (k>1)
  
  
• Als Grundlage für statistische Auswertungen können Dir die Funktionen in Version 4 helfen. Dabei wird die Permutation iterativ bestimmt. Beachte, dass nur ein Vektor mit den nachfolgenden Personen verwendet wird. Man muss sich also immer vom Bezugspunkt 'Vorgänger' aus orientieren und nicht an der gerade aktuellen Position.
  Weiters findest Du einen erstaunlichen Algorithmus von D. Knuth (The Art of Computer Programming), der sehr rasch herausfindet, welcher Mann im x-ten Auszählschritt entfernt wurde. Diese Methode kommt ohne ein Hilfsfeld aus und berechnet den Index direkt.
  
  
• Ergebnisse dieser Untersuchungen fallen in der Mathematik in ein spezielles Fachgebiet. Knuth hat auch dazu ein Lehrbuch geschrieben: Concrete Mathematics.