Josephus problem
Encyclopedia
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.
, 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):
. (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:
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 
.
. This approach gives us the recurrence:
This can be seen from the following arguments:
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.
, 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).
We eliminate second of every two remaining persons until one person remains. Given the n, determine the number of xth person who is eliminated.
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 YodfatSiege 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 programmingDynamic 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 MathematicsConcrete 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
- Josephus Flavius game (Java Applet) at cut-the-knotCut-the-knotCut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...
allowing selection of every nth out of 50 (maximum). - Josephus Problem at the MathWorld encyclopedia
- Josephus Problem at Shippensburg University