Josephus problem

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged with Josephus_permutation. (Discuss)

The Josephus problem is a theoretic problem occurring in computer science and mathematics.

There are n people standing in a circle waiting to be executed. After the first man is executed, k−1 people are skipped and the k-th man is executed. Then again, k−1 people are skipped and the k-th man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.

The task is to choose the place in the initial circle so that you survive (remain the last one), given n and k.

1 History
2 Solution
3 Variants
4 External links

[edit] History

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. As the legend goes, he and his 40 comrade soldiers were trapped in a cave, surrounded by Romans. They chose suicide over capture and decided that they will form a circle and start killing themselves using a step of three. As Josephus did not want to die, he was able to find the safe place, and stayed alive, later joining the Romans who captured him.

[edit] Solution

A partial solution is as follows. For simplicity, we assume that every 2nd person will be killed, i.e, k=2. Now, we frame the solution in terms of recursive relations. If the number of people present were odd, then the person who would survive after killing has gone once around the circle. He would be present, but this time killing would start from the first person, so, effectively his index would be increased by 1. Therefore,

$f (2 n + 1) = 2 * f (n) + 1$

But for even number of people it is the other way around. Therefore,

$f (2 n) = 2 * f (n) - 1$

where f(n) is the solution to the problem with n number of people present, while k=2.

When we tabulate the values of n against f(n) we find a nice regularity:

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 shows that f(n) represents an increasing odd sequence with $f (n) = 1$ appearing regularly whenever the index n is a power of 2.

Therefore, if we represent n as $2 m + l$ , where $0 < = l < 2 m$ , then $f (n) = 2 * l + 1$ . It can be clearly seen that the equation satisfies the table. But mathematics demands exact proof, i.e., simple proof by induction (not included here).

If n can be represented as $n = b 0 b 1 b 2 b 3... b n$ , where b0b1b2b3 is its binary notation, then the solution is $f (n) = b 1 b 2 b 3... b n b 0$ . The proof for this very simple regularity comes from the representation of n as $2 m + l$ .

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

$f(n,k)=(f(n-1)+k) \bmod n\quad (f(1,k)=0)$ ,

which is evident when considering how the survivor number changes when switching from n to $\,n-1$ . This is $\,O(n)$ approach, but for small k and large n there is another approach, which also involves dynamic programming. The second approach gives complexity $O(k\,\log\,n)$ . It is based on considering killing k-th, 2k-th, ..., $\lfloor n/k \rfloor$ -th people as one step, then changing the numeration.

[edit] Variants

According to Concrete Mathematics, section 1.3, Josephus was accompanied by an unindicted co-conspirator; the problem was to find the places of the two last remaining survivors (whose conspiracy would ensure their survival).