Josephus problem

In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.

There are people standing in a circle waiting to be executed. After the first person is executed, a certain number of people are skipped and one person is executed. Then, again, people are skipped and a person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

1 History
2 Solution
- 2.1 k=2
- 2.2 The general case
3 Variants and generalizations
- 3.1 Extended Josephus problem
4 Notes
5 References
6 External links

History

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. According to Josephus' account of the siege of Yodfat, he and his 40 comrade soldiers were trapped in a cave, the exit of which was blocked by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. Josephus states that by luck or maybe by the hand of God (modern scholars point out that Josephus was a well educated scholar and predicted the outcome), he and another man remained the last and gave up to the Romans.
The reference comes from Book 3, Chapter 8, par 7 of Josephus' The Jewish War (writing of himself in the third person):

However, in this extreme distress, he was not destitute of his usual sagacity; but trusting himself to the providence of God, he put his life into hazard [in the manner following]: "And now," said he, "since it is resolved among you that you will die, come on, let us commit our mutual deaths to determination by lot. He whom the lot falls to first, let him be killed by him that hath the second lot, and thus fortune shall make its progress through us all; nor shall any of us perish by his own right hand, for it would be unfair if, when the rest are gone, somebody should repent and save himself." This proposal appeared to them to be very just; and when he had prevailed with them to determine this matter by lots, he drew one of the lots for himself also. He who had the first lot laid his neck bare to him that had the next, as supposing that the general would die among them immediately; for they thought death, if Josephus might but die with them, was sweeter than life; yet was he with another left to the last, whether we must say it happened so by chance, or whether by the providence of God. And as he was very desirous neither to be condemned by the lot, nor, if he had been left to the last, to imbrue his right hand in the blood of his countrymen, he persuaded him to trust his fidelity to him, and to live as well as himself.^[1]

Solution

k=2

We explicitly solve the problem when every 2nd person will be killed, i.e. $k=2$ . (For the more general case $k\neq 2$ , we outline a solution below.) We express the solution recursively. Let $f(n)$ denote the position of the survivor when there are initially $n$ people (and $k=2$ ). The first time around the circle, all of the even-numbered people die. The second time around the circle, the new 2nd person dies, then the new 4th person, etc.; it's as though there were no first time around the circle. If the initial number of people was even, then the person in position $x$ during the second time around the circle was originally in position $2x - 1$ (for every choice of $x$ ). So the person in position $f(2n)$ was originally in position $2f(n) - 1$ . This gives us the recurrence:

$f(2n)=2f(n)-1.\,$

If the initial number of people was odd, then we think of person 1 as dying at the end of the first time around the circle. Again, during the second time around the circle, the new 2nd person dies, then the new 4th person, etc. In this case, the person in position $x$ was originally in position $2x%2B1$ . This gives us the recurrence:

$f(2n%2B1)=2f(n)%2B1.\,$

When we tabulate the values of $n$ and $f(n)$ we see a pattern:

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

This suggests that $f(n)$ is an increasing odd sequence that restarts with $f(n)=1$ whenever the index n is a power of 2. Therefore, if we choose m and l so that $n=2^m%2Bl$ and $0\leq l<2^m$ , then $f(n)=2 \cdot l%2B1$ . It is clear that values in the table satisfy this equation. Or we can think that after $l$ people are dead there are only $2^m$ people and we go to the $2l%2B1$ th person. He must be the survivor. So $f(n)=2l%2B1$ . Below, we give a proof by induction.

Theorem: If $n=2^m%2Bl$ and $0\leq l<2^m$ , then $f(n) = 2l%2B1$ .

Proof: We use strong induction on $n$ . The base case $n=1$ is true. We consider separately the cases when $n$ is even and when $n$ is odd.

If $n$ is even, then choose $l_1$ and $m_1$ such that $n/2 = 2^{m_1}%2Bl_1$ and $0\leq l_1 < 2^{m_1}$ . Note that $l_1 = l/2$ . We have $f(n) = 2f(n/2)-1=2((2l_1)%2B1) - 1=2l%2B1$ , where the second equality follows from the induction hypothesis.

If $n$ is odd, then choose $l_1$ and $m_1$ such that $(n-1)/2 = 2^{m_1}%2Bl_1$ and $0\leq l_1 < 2^{m_1}$ . Note that $l_1 = (l-1)/2$ . We have $f(n) = 2f((n-1)/2)%2B1=2((2l_1)%2B1) %2B 1=2l%2B1$ , where the second equality follows from the induction hypothesis. This completes the proof.

The most elegant form of the answer involves the binary representation of size $n$ : $f(n)$ can be obtained by a one-bit left cyclic shift of $n$ itself. If we represent $n$ in binary as $n=b_0 b_1 b_2 b_3\dots b_m$ , then the solution is given by $f(n)=b_1 b_2 b_3 \dots b_m b_0$ . The proof of this follows from the representation of $n$ as $2^m%2Bl$ .

The general case

The easiest way to solve this problem in the general case is to use dynamic programming. This approach gives us the recurrence:

$f(n,k)=(f(n-1,k)%2Bk) \bmod n,\text{ with }f(1,k)=1,\,$

This can be seen from the following arguments:

When starting from position $k (\bmod n)$ instead of 0, the number of the last remaining person also shifts by $k$ positions
After the first round of the $n$ person problem one eliminates the person on position $k \bmod n$ and is left with an $n-1$ person problem. The person $(k%2B1) \bmod n$ (in the $n$ person case) is the first of the next $k$ counts and thus has the label 1 in the $n-1$ problem. We must therefore shift the outcome of the $n-1$ problem by $(k%2B1 - 1)$ positions to get the answer for the case with $n$ persons.

This approach has running time $O(n)$ , but for small $k$ and large $n$ there is another approach. The second approach also uses dynamic programming but has running time $O(k\log n)$ . It is based on considering killing k-th, 2k-th, ..., $(\lfloor n/k \rfloor k)$ -th people as one step, then changing the numbering.

Variants and generalizations

According to Concrete Mathematics, section 1.3, Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival).

Extended Josephus problem

Problem definition: There are n persons, numbered 1 to n, around a circle. We eliminate second of every two remaining persons until one person remains. Given the n, determine the number of xth person who is eliminated.^[2]

Notes

^ Flavius Josephus, Wars Of The Jews III. 8. 7. (Translation by William Whiston).
^ Armin Shams-Baragh Formulating The Extended Josephus Problem.

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). "Chapter 14: Augmenting Data Structures". Introduction to Algorithms (Second Edition ed.). MIT Press and McGraw-Hill. p. 318. ISBN 0-262-03293-7.

External links

Josephus Flavius game (Java Applet) at cut-the-knot allowing selection of every n^th out of 50 (maximum).
Josephus Problem at the MathWorld encyclopedia
Josephus Problem at Shippensburg University