Josephus Problem

From ProofWiki
Jump to navigation Jump to search

Problem

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.


Solution


Historical Note

The legend goes that the $1$st-century Jewish historian Flavius Josephus was holed up in a cave with a bunch of comrades (some sources give the exact number of rebels as $41$), hiding from a band of Roman soldiers.

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.


The exercise is familiar to schoolchildren the world over.


Sources