# Josephus Flavius Problem

Following is an excerpt from

*Mathematical Recreations and Essays*

by W.W. Rouse Ball and H.S.M.Coxeter

In the general case *n* men are arranged in a circle which is closed up as individuals are
picked out. Beginning anywhere, we continually go round, picking out each *m*th man until only
*r* are left. Let one of these be the man who originally occupied the *p*th place. Then had we
begun with *n* + 1 men, he would have originally occupied the (*p* + *m*)th place when *p* + *m* is not
greater than *n* + 1, and the *(p + m - n - 1)*th place when *p* + *m* is greater than *n* + 1. Thus,
provided there are to be *r* men left, their original positions are each shifted forwards along
the circle *m* places for each addition of a single man to the original group.

Now suppose that with n men the last survivor (*r* = 1) occupied originally the *p*th place,
and that with *n* + *x* men the last survivor occupied the *y*th place. Then, if we confine ourselves
to the lowest value of *x* which makes *y* less than *m*, we have *y* = *(p + mx) - (n + x)*.

Based on this theorem we can, for any specified value of *n*, calculate rapidly the position
occupied by the last survivor of the company. In effect, Tait found the values of *n* for which
a man occupying a given position *p*, which is less than *m*, would be the last survivor, and then, by repeated applications of the proposition, obtained the position of the survivor for intermediate values of *n*.

For instance, take the Josephus problem in which m=3. Then we know that the final survivor
of 41 men occupied originally the 31st place. Suppose that when there had been (41+*x*) men,
the survivor occupied originally the *y*th place. Then, if we consider only the lowest
value of *x* which makes *y* less than *m*, we have *y* = (31 + 3*x*) - (41 + *x*) = 2*x* - 10.
Now, we have to take a value of *x* which makes *y* positive and less than *m*, that is,
in this case equal to 1 or 2. This is *x* = 6, which makes *y* = 2. Hence, had there been 47 men, the man last chosen would have
originally occupied the second place. Similarly had there been 47+*x* men, the man would have
occupied originally the yth place, where, subject to the same conditions as before, we have
*y*=(2+3*x*)-(47+*x*)=2*x*-45. If *x* = 23, *y* = 1. Hence, with 70 men the man last chosen would have
occupied originally the first place. Continuing the process, it is easily found that if *n*
does not exceed 2000000 the last man to be taken occupies the first place when
*n* = 4, 6, 9, 31, 70, 105, 355, 799, 1798, 2697, 9103, 20482, 30723, 69127, 155536, 233304,
349956, 524934, or 787401 ; and the second place when *n* = 2, 3, 14, 21, 47, 158, 237, 533,
1199, 4046, 6069, 13655, 46085, 103691, 1181102, or 1771653. From these results, by repeated
applications of the proposition, we find, for any intermediate values of *n*, the position
originally occupied by the man last taken. Thus with 1000 men, the 604th place; with 100000
men, the 92620th place; and with 1000000 men, the 637798th place are those which would be
selected by a prudent mathematician in a company subjected to trimation.

Similarly if a set of 100 men were subjected to decimation, the last to be taken would be the man originally in the 26th place. Hence, with 227 men the last to be taken would be the man originally in the first place.

Modifications of the original problem have been suggested. For instance, let 5 Christians
and 5 Turks be arranged round a circle thus, TCTCCTCTCT Suppose that if beginning at the *a*th
man, every *h*th man is selected, all the Turks will be picked out for punishment; but if
beginning at the *b*th man, every *k*th man is selected, all the Christians will be picked out for
punishment. The problem is to find *a*, *b*, *h*, and *k*.
A solution is *a*=l, *h*=11, *b*=9, *k*=29.

### Reference

- W.W.Rouse Ball and H.S.M.Coxeter,
*Mathematical Recreations and Essays*, Dover, 1987

- Josephus Flavius problem
- Two ancient variants
- A simple solution
- Partial recursive solution
- A problem from USAMTS

|Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny64671746 |