Josephus Problem

Given a group of $n$ men arranged in a Circle under the edict that every $m$th man will be executed going around the Circle until only one remains, find the position $L(n,m)$ in which you should stand in order to be the last survivor (Ball and Coxeter 1987). The original problem consisted of a Circle of 41 men with every third man killed ($n=41$, $m=3$). In order for the lives of the last two men to be spared, they must be placed at positions 31 (last) and 16 (second-to-last).

The following array gives the original position of the last survivor out of a group of $n=1$, 2, ..., if every $m$th man is killed:

$$\matrix{ 1\cr 2 & 1\cr 3 & 3 & 2\cr 4 & 1 & 1 & 2\cr 5 & 3 &... ... & 7 & 2 & 3 & 8\cr 10 & 5 & 4 & 5 & 3 & 3 & 9 & 1 & 7 & 8\cr}$$

(Sloane's A032434). The survivor for $m=2$ can be given analytically by

$$L(n,2)=1+2n-2^{1+\left\lfloor{\lg n}\right\rfloor },$$

where $\left\lfloor{n}\right\rfloor$ is the Floor Function and Lg is the Logarithm to base 2. The first few solutions are therefore 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, ... (Sloane's A006257).

Mott-Smith (1954) discusses a card game called ``Out and Under'' in which cards at the top of a deck are alternately discarded and placed at the bottom. This is a Josephus problem with parameter $m=2$, and Mott-Smith hints at the above closed-form solution.

The original position of the second-to-last survivor is given in the following table for $n=2$, 3, ...:

$$\matrix{ 1 & 1\cr 2 & 1 & 1\cr 3 & 1 & 1 & 2\cr 4 & 3 & 2 & ... ...2 & 7 & 1 & 3 & 7\cr 9 & 5 & 4 & 5 & 3 & 3 & 8 & 1 & 6 & 4\cr}$$

(Sloane's A032435).

Another version of the problem considers a Circle of two groups (say, ``A'' and ``B'') of 15 men each, with every ninth man cast overboard. To save all the members of the ``A'' group, the men must be placed at positions 1, 2, 3, 4, 10, 11, 13, 14, 15, 17, 20, 21, 25, 28, 29, giving the ordering

$$AAAABBBBBAABAAABABBAABBBABBAAB$$

which can be remembered with the aid of the Mnemonic ``From numbers' aid and art, never will fame depart.'' Consider the vowels only, assign $a=1$, $e=2$, $i=3$, $o=4$, $u=5$, and alternately add a number of letters corresponding to a vowel value, so 4A (o), 5B (u), 2A (e), etc. (Ball and Coxeter 1987).

If every tenth man is instead thrown overboard, the men from the ``A'' group must be placed in positions 1, 2, 4, 5, 6, 12, 13, 16, 17, 18, 19, 21, 25, 28, 29, giving the sequence

$$AABAAABBBBBAABBAAAABABBBABBAAB$$

which can be constructed using the Mnemonic ``Rex paphi cum gente bona dat signa serena'' (Ball and Coxeter 1987).

See also Kirkman's Schoolgirl Problem, Necklace

References

Bachet, C. G. Problem 23 in Problèmes plaisans et délectables, 2nd ed. p. 174, 1624.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 32-36, 1987.

Kraitchik, M. ``Josephus' Problem.'' §3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.

Mott-Smith, G. Mathematical Puzzles for Beginners and Enthusiasts. New York: Dover, 1954.

Sloane, N. J. A. Sequences A006257/M2216, A032434, and A032435 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.