Josephus problem
Encyclopedia
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 and mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game
Counting-out game
A counting-out game is a simple game intended to select a person to be "it", often for the purpose of playing another game. These games usually require no materials, and are played with spoken words or hand gestures....

.

There are people standing in a circle
Circle
A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....

 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.

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
Siege of Yodfat
The Siege of Yodfat was a 47 day siege by Roman forces of the Jewish town of Yodfat which took place in 67 CE, during the Great Revolt. Led by Roman General Vespasian and his son Titus, both future emperors, the siege ended with the sacking of the town, the deaths of most of its inhabitants and...

, 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):



k=2

We explicitly solve the problem when every 2nd person will be killed, i.e. . (For the more general case , we outline a solution below.)
We express the solution recursively. Let denote the position of the survivor when there are initially people (and ).
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 during the second time around the circle was originally in position (for every choice of ). So the person in position was originally in position . This gives us the recurrence:


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 was originally in position . This gives us the recurrence:


When we tabulate the values of and we see a pattern:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1


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

Theorem: If and , then .

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

If is even, then choose and such that and . Note that .
We have , where the second equality follows from the induction hypothesis.

If is odd, then choose and such that and . Note that .
We have , 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 : can be obtained by a one-bit left cyclic shift of itself. If we represent in binary as , then the solution is given by . The proof of this follows from the representation of as .

The general case

The easiest way to solve this problem in the general case is to use dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

. This approach gives us the recurrence:


This can be seen from the following arguments:
  • When starting from position instead of 0, the number of the last remaining person also shifts by positions
  • After the first round of the person problem one eliminates the person on position and is left with an person problem. The person (in the person case) is the first of the next counts and thus has the label 1 in the problem. We must therefore shift the outcome of the problem by positions to get the answer for the case with persons.


This approach has running time , but for small and large there is another approach. The second approach also uses dynamic programming but has running time . It is based on considering killing k-th, 2k-th, ..., -th people as one step, then changing the numbering.

Variants and generalizations

According to Concrete Mathematics
Concrete Mathematics
Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, is a mathematical textbook that is widely used in computer-science departments. It provides mathematical knowledge and skills for computer science, especially for the analysis of algorithms...

, 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.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK