In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game.
Contents
People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.
The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution.
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 soldiers were trapped in a cave by Roman soldiers. They chose suicide over capture, and settled on a serial method of committing suicide by drawing lots. Josephus states that by luck or possibly by the hand of God, he and another man remained until the end and surrendered to the Romans rather than killing themselves. This is the story given in Book 3, Chapter 8, part 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.
The details of the mechanism used in this feat are rather vague. According to Dowdy and Mays, in 1612 Bachet suggested the specific mechanism of arranging the men in a circle and counting by threes to determine the order of elimination. This story has been often repeated and the specific details vary considerably from source to source. For instance, Herstein and Kaplansky (1974) have Josephus and 39 comrades stand in a circle with every seventh man eliminated. A history of the problem can be found in S. L. Zabell's Letter to the editor of the Fibonacci Quarterly.
Josephus had an accomplice; the problem was then to find the places of the two last remaining survivors (whose conspiracy would ensure their survival). It is alleged that he placed himself and the other man in the 31st and 16th place respectively.
Variants and generalizations
A Medieval version of the Josephus problem involves 15 Turks and 15 Christians on board a ship in a storm which will sink unless half the passengers are thrown overboard. All 30 stand in a circle and every ninth person is to be tossed into the sea. Where should the Christians stand to ensure that only the Turks are tossed? In other versions the roles of Turks and Christians are interchanged.
In Concrete Mathematics: A Foundation for Computer Science, Graham, Knuth and Patashnik describe and study a "standard" variant: Determine where the last survivor stands if there are n people to start and every second person (k = 2 below) is eliminated.
A generalization of this problem is as follows. We suppose that every mth person will be executed from a group of size n, in which the pth person is the survivor. If there is an addition of x people to the circle, then the survivor is in the p + mx-th position if this is less than or equal to n + x. If x is the smallest value for which (p + mx) > (n + x), then the survivor is in position (p + mx) − (n + x).
Solution
In the following,
k=2
We explicitly solve the problem when every 2nd person will be killed, i.e.
If the initial number of people was even, then the person in position
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
When we tabulate the values of
This suggests that
Theorem: If
Proof: We use strong induction on
If
If
We can solve for
The most elegant form of the answer involves the binary representation of size
Implementation: If n denotes the number of people, the safe position is given by the function
Now if we represent the number in binary format, the first bit denotes
n = 1 0 1 0 0 1
2m = 1 0 0 0 0 0
l = 0 1 0 0 1
The general case
The easiest way to solve this problem in the general case is to use dynamic programming by performing the first step and then using the solution of the remaining problem. When the index starts from one, then the person at
which takes the simpler form
if we number the positions from
This approach has running time
This improved approach takes the form