TOPICS
Search

Josephus Problem


JosephusDecimation

Given a group of n men arranged in a circle under the edict that every mth 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 list giving the place in the execution sequence of the first, second, etc. man can be given by Josephus[n, m] in the Wolfram Language package Combinatorica` . For example, consider n=4 men numbered 1 to 4 such that each second (m=2) man is iteratively slaughtered, as illustrated above. As can be seen, the first man is slaughtered 4th, the second man 1st, the third man 3rd, and the fourth man 2nd, so Josephus[4, 2] returns {4, 1, 3, 2}.

To obtain the ordered list of men who are consecutively slaughtered, InversePermutation can be applied to the output of Josephus. So, in the above example, InversePermutation[Josephus[4, 2]] returns {2, 4, 3, 1} since the 2nd man is slaughtered first, the 4th man is slaughtered second, the 3rd man is slaughtered third, and the 1st man is slaughtered fourth.

Josephus41-3

The original Josephus problem consisted of a circle of 41 men with every third man killed (n=41, m=3), illustrated above, where the outer number indicates the order in which a given man is killed. 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 complete list in order of execution is 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 1, 5, 10, 14, 19, 23, 28, 32, 37, 41, 7, 13, 20, 26, 34, 40, 8, 17, 29, 38, 11, 25, 2, 22, 4, 35, 16, 31.

Josephus30-9

Another version of the problem considers a circle of two groups (say, "A" and "B") of 15 men each (giving a total of 30 men), with every ninth man cast overboard, illustrated above. 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. Written out explicitly, the order is

 AAAABBBBBAABAAABABBAABBBABBAAB.
(1)

This sequence of letters 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. (Mott-Smith 1954, §149, pp. 94 and 209-210; Ball and Coxeter 1987).

Josephus30-10

If instead every tenth man is 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. Written out explicitly,

 AABAAABBBBBAABBAAAABABBBABBAAB
(2)

which can be constructed using the Latin mnemonic "Rex paphi cum gente bona dat signa serena" (Ball and Coxeter 1987).

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

 1         ; 2 1        ; 3 3 2       ; 4 1 1 2      ; 5 3 4 1 2     ; 6 5 1 5 1 4    ; 7 7 4 2 6 3 5   ; 8 1 7 6 3 1 4 4  ; 9 3 1 1 8 7 2 3 8 ; 10 5 4 5 3 3 9 1 7 8
(3)

(OEIS A032434). The survivor for m=2 can be given analytically by

 L(n,2)=1+2n-2^(1+|_lgn_|),
(4)

where |_n_| 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, ... (OEIS A006257).

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

 1 2        ; 2 1 1       ; 3 3 4 3      ; 4 5 2 2 4     ; 5 1 5 6 3 5    ; 6 3 1 3 1 4 4   ; 7 5 4 7 6 2 3 7  ; 8 7 7 2 2 8 1 6 7 ; 9 9 10 6 7 4 8 4 6 4
(5)

(OEIS A032435).

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

 1 2 3       ; 2 4 2 1      ; 3 1 5 5 3     ; 4 3 2 3 2 2    ; 5 5 5 7 7 1 2   ; 6 7 8 3 4 7 1 2  ; 7 9 2 7 9 4 8 1 2 ; 8 1 5 1 4 10 5 9 1 7
(6)

(OEIS A032436).

Mott-Smith (1954, §153, pp. 96 and 212) 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.


See also

Kirkman's Schoolgirl Problem, Necklace

Explore with Wolfram|Alpha

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.Ballew, P. "The Josephus Problem." http://www.pballew.net/josephus.html.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Kraitchik, M. "Josephus' Problem." §3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.Mott-Smith, G. "Decimation Puzzles." Ch. 9, §149-154 in Mathematical Puzzles for Beginners and Enthusiasts, 2nd rev. ed. New York: Dover, pp. 94-97 and 209-214, 1954.Odlyzko, A. M. and Wilf, H. S. "Functional Iteration and the Josephus Problem." Glasgow Math. J. 33, 235-240, 1991.Skiena, S. "Josephus' Problem." §1.4.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 34-35, 1990.Sloane, N. J. A. Sequences A006257/M2216, A032434, A032435, and A032436 in "The On-Line Encyclopedia of Integer Sequences."Update a linkSmith, H. J. "Josephus Permutation Problems." http://www.geocities.com/hjsmithh/Josephus.html

Referenced on Wolfram|Alpha

Josephus Problem

Cite this as:

Weisstein, Eric W. "Josephus Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/JosephusProblem.html

Subject classifications