Definition:Josephus Problem
Definition
Consider a collection of $n$ people in a circle.
Let them each be eliminated sequentially by counting out every $m$th person (closing the gap after each elimination).
For a given a number of people $n$, and a given step size $m$, the problem is to determine the initial position in the circle of the person who remains after all the others have been eliminated.
Also see
- Results about the Josephus problem can be found here.
Historical Note
The legend describes an incident during the sack of Jotapata in $\text {67 CE}$ by General Vespasian and his son Titus, both future emperors.
The story goes that the Jewish historian Flavius Josephus, at the time the commander of the Jewish rebels, was holed up in a cave with a bunch of comrades (some sources give the exact number of rebels as $41$), hiding from the Romans.
Death was preferable to capture, so they determined a procedure whereby they would all commit ritual suicide.
They all stood in a circle, and counted round.
Every third person was killed, and the gap was closed.
However, Josephus (and possibly a co-conspirator) figured out where to stand in the circle so as to be last to be picked.
He (or they) gave themselves up to the Romans.
Hence Josephus lived to tell the tale.
According to David Wells in his Curious and Interesting Puzzles of $1992$, this incident was first presented as a puzzle to be solved by Nicolas Chuquet, although he fails to indicate where it appears.
The exercise of elimination by counting is familiar to schoolchildren the world over.
Sources
- 1994: Ronald L. Graham, Donald E. Knuth and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science (2nd ed.): Chapter $1.3$
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Josephus problem