Zahlwort

Jeder kennt aus seiner Kind­heit Abzähl­verse, um den näch­sten Kan­di­da­ten zu be­stim­men. Zum Bei­spiel „a ba bu und ab bist du“. Nor­ma­ler­weise sind sie etwas län­ger, doch bereits bei die­sen sie­ben Sil­ben ist es schwie­rig vor­her­zuse­hen, wel­che Posi­tion es tref­fen wird, um sich an sie zu stellen oder sie zu meiden. Die nach­ste­hende Abbil­dung zeigt links zweimal fünf abzu­zäh­lende Posi­tio­nen. Die letzte ist die rechts in der Reihe ste­hende oder die abzäh­len­de Per­son selbst. Im linken Teil­bild wird immer wie­der vorne begon­nen, und es trifft zum Schluß die fünfte Posi­tion. Diese Methode ist unschön, wenn mehr Per­so­nen n in der Reihe stehen als der Abzähl­vers Sil­ben k hat. Dann fällt dumm auf, daß es stets zunächst die hin­teren Posi­tio­nen k bis n trifft. Des­halb wird bes­ser wie im zwei­ten Teil­bild nach dem Aus­schei­den einer Per­son an der rechts dane­ben fort­gefah­ren. Ich meine, daß es in mei­ner Kind­heit so war. Alles andere hätte mir dumm auf­fal­len müs­sen.

1 2 3 4 5   1 2 3 4 5   00000000011111111112222222222333333333344
a b b u a   a b b u a   12345678901234567890123456789012345678901
b d | | |   b d a b b   ||X||X||X||X||X||X||X||X||X||X||X||X||X||
a   b b u   u   a b d   X| |X || X| |X || X| |X || X| |X || X| |X
a   b d |   a   b b      | |  X|  | X  ||  X |  |X  | |  X|  | X
a   b   b   u   a b      | |   X  |    |X    |  |   X |   |  X
u   a   b   d   a b      | |      X    |     |  X     |   |
d   |   |       b u      X |           |     X        |   |
    a   b       a b        X           |              |   X
    b   u       d |                    |              |
    a   b         |                    X              |
    d   |<-----letzter            Josephus        letzter

Während Kinder im all­gemei­nen wenige Posi­tio­nen mit lan­gen Ver­sen abzäh­len, sind es im rech­ten Teil­bild viele Posi­tio­nen n=41 und wenige Sil­ben k=3. Flavius Jose­phus wollte angeb­lich mit 40 wei­teren Gefan­genen Selbst­mord bege­hen. Nach­dem das Los bereits 39 das Leben kostete, war Jose­phus selbst an der Reihe. Da ergaben sich die rest­lichen beiden den Römern. Das führte zu der Frage: An welcher Posi­tion stand Jose­phus, wenn 41 Leute sich im Kreis auf­stellen und begin­nend mit der Posi­tion 3 jeder dritte erschlagen wird? Das vor­ste­hende Bild liefert die Antwort.

Das allgemeine Jose­phus-​Pro­blem  besteht darin, die Posi­tion p des letzten für alle n und k zu ermit­teln. Eine geschlos­sene Lösung ist wohl über k=3 hinaus nicht bekannt. Doch für k=2 ist es recht einfach:

0000000001111111111222222222233333333334444444444555555555566666
1234567890123456789012345678901234567890123456789012345678901234
|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X
| X | X | X | X | X | X | X | X | X | X | X | X | X | X | X | X
|   X   |   X   |   X   |   X   |   X   |   X   |   X   |   X
|       X       |       X       |       X       |       X
|               X               |               X
|<--letzter                     X

Die vorstehende Abbil­dung zeigt, daß für Zweier­poten­zen n=2^m in jedem der m Um­läu­fe die An­zahl hal­biert wird und die Posi­tion 1 übrig­bleibt. Ist nun n=2^m+l mit l<2^m, dann kom­men zu­nächst die l Po­si­tio­nen 2, 4, 6, ..., 2l<n ums Leben. Danach stehen noch 2^m Mann. Nun ist der an Posi­tion p=2l+2 an der Reihe, und sein Vorgänger bei p=2l+1 bleibt letzt­lich übrig. Wer diese Über­le­gung scheut, aber pro­gram­mie­ren kann, der er­stellt sich eine Ta­belle, erkennt das Prin­zip und hofft, daß es sich so fort­setzt.

 n        p        n          p         n            p
1   1    1 1      8 1000  0001  1     15  1111   1111 15
2  10   01 1      9 1001  0011  3     16 10000  00001  1
3  11   11 3     10 1010  0101  5     17 10001  00011  3
4 100  001 1     11 1011  0111  7     18 10010  00101  5
5 101  011 3     12 1100  1001  9     19 10011  00111  7
6 110  101 5     13 1101  1011 11     20 10101  01011  9
7 111  111 7     14 1110  1101 13     21 10110  01101 11

Es gibt eine nette Spie­lerei, zur An­zahl n die Posi­tion p des Über­leben­den zu bestim­men: Aus der Binär­dar­stel­lung der Zahl n wird die füh­ren­de 1 ge­stri­chen und hin­ten ange­fügt. So er­gibt sich eine Binär­dar­stel­lung der Posi­tion p. Der Grund ist ein­fach: Durch das Ent­fer­nen der füh­ren­den 1 geht n in n-2^m=l über. Das Anfü­gen ei­ner 1 am Ende macht aus l dann 2l+1=p.

[1] Wolfram Mathworld. Josephus Problem.
[2] The On-Line Encyclopedia of Integer Sequences. A032434, A006257, A054995.

41 | Sieb von Josephus