Im 1. Jahrhundert beschreibt der Historiker Flavius Josephus in seinem Buch »Geschichte des jüdischen Krieges« eine grausame Szene. Beim Kampf um die galiläische Stadt Jotapata verstecken sich 41 Männer in einer Höhle, um nicht den Römern in die Hände zu fallen. Einer davon ist Josephus, der sich ergeben möchte. Seine Gefährten sehen das anders; sie wollen lieber von eigener Hand sterben, als vo n den Römern gefangengenommen zu werden. Josephus versucht den anderen die Selbsttötung auszureden, bleibt jedoch erfolglos. Also schlägt er folgendes Verfahren vor: »Weil es nun einmal beschlossene Sache ist, dass wir jetzt sterben, wohlan, so werden wir das Los entscheiden lassen, wer jedes Mal Opfer und Henker sein soll. Derjenige nämlich, welcher zuerst vom Lose betroffen wird, soll immer von dem, der nach ihm herausgelost wird, niedergestoßen werden.« (Buch III, Kapitel 8)

Josephus hat Glück und bleibt als Vorletzter übrig. Gemeinsam mit dem letzten Mann ergibt er sich und überlebt. Wie die Opfer ausgelost wurden, ist unbekannt, aber der französische Mathematiker Claude Gaspard Bachet de Méziriac griff die Geschichte im 17. Jahrhundert für sein Buch »Angenehme und ergötzliche Probleme, die mit Zahlen gelöst werden« auf. Er beschreibt, dass sich die 41 Männer im Kreis aufgestellt haben und der Reihe nach jeder dritte getötet wurde.

Mit der Zeit hat sich aus dieser grausigen Geschichte eine klassische Denksportaufgabe entwickelt: Man ordnet n Objekte im Kreis an und jedes k-te Objekt wird, beginnend mit der Nummer k, aus dem Kreis entfernt. Die Lücken im Kreis werden dabei immer wieder geschlossen. Die Frage ist, welche Nummer das letzte verbleibende Objekt hat.

Für den Fall k = 2 lässt sich die Antwort durch diese Formel berechnen:

Man schreibt also n als Zweierpotenz mit Rest l, wobei l immer kleiner als die Zweierpotenz sein muss. Die Nummer des letzten Objekts ist dann einfach das Doppelte des Rests plus 1. Im Fall von n = 41 kann man n = 2⁵ + 9 schreiben und f(41) ergibt sich zu 19. Hätten sich die 41 Männer aus Josephus' Geschichte in der Höhle also im Kreis aufgestellt und beschlossen, dass Person 1 die neben ihr stehende Person 2 umbringen muss, dann Person 3 die Nummer 4 und so weiter, bis alle tot sind, dann hätte Josephus sich auf Platz 19 stellen müssen, um als Letzter zu überleben.

Die obige Formel lässt sich mit einem rekursiven Ansatz vergleichsweise einfach herleiten. Etwas mehr Aufwand braucht es, eine Gleichung für den allgemeinen Fall beliebiger Werte von k zu finden. Damit kann man dann zum Beispiel ausrechnen, dass sich Josephus auf Platz 31 im Kreis stellen muss, damit er als Vorletzter übrigbleibt, wenn der Reihe nach jede dritte Person eliminiert wird.

Von Schiffen bis Katzen

In einer anderen Version des Problems, die im Mittelalter kursierte, geht es um ein Schiff, auf dem sich 15 Türken und 15 Christen befinden. Ein Sturm zieht auf und das Schiff ist dem Untergang geweiht, wenn es nicht schnell an Gewicht verliert. Die Hälfte der Passagiere muss ins Wasser geworfen werden, um die andere Hälfte zu retten. Der Kapitän beschließt, die 30 Personen im Kreis aufzustellen und der Reihe nach jeden Neunten zu opfern. Je nachdem, wo diese Geschichte erzählt wurde, besteht die Aufgabe nun darin, die Positionen so zu bestimmen, dass alle Christen oder alle Türken überleben.

Das »Josephus-Problem« ist im Lauf der Zeit in immer neuen Versionen untersucht worden. 2010 haben die kanadischen Mathematiker Frank Ruskey und Aaron Williams zum Beispiel das »Feline Josephus Problem« definiert, bei dem alle Beteiligten – so wie die sprichwörtliche Katze – mehrere Leben haben. Aber so interessant die Mathematik in all diesen Fällen auch sein mag: Ich rechne lieber mit Formeln, bei denen es nicht um den Tod von Menschen (oder Katzen) geht.