## Tag Archives: modulo arithmetic

### The Josephus Problem

The Jewish historian Josephus was trapped in a cave with forty other Jews, all of them trying to evade their Roman conquerors who had captured their place Jotapat. The Jews decided to kill themselves rather than be captured by the invaders. However, Josephus and a friend of his did not wish to die. To avoid expressing dissent in the midst of all present, he suggested a sequential process of killing each a member. He arranged all 41 in a circle and starting with a given person, made the rule that every third man was to be killed. Of course, in this way, the circle would get progressively shorter, till only one person would be left, who was to commit suicide. Josephus placed himself and his friend in such positions with respect to the starting one that they were the last two left and thus escaped. The question is, where were they placed initially?

To solve this problem, number all the positions and progressively eliminate every third one till only two are left. The answer is that the positions 16 and 31 are the last to go. Thus, Josephus and his friends occupied these positions.

We can check this as follows:

The original positions are:

1,2,3,4,5,6,7,8,9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41.

After the last position 41, follows the position 1 in the circle, of course. Now, let us go around the circle once, removing every third number along the way:

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41.

Continuing to go around the circle the second time, after 40 and 41, the third number is 1, which has to go. So, after the second round, we are left with:

2, 4, 7, 8, 11, 13, 16, 17, 20, 22, 25, 26, 29, 31, 34, 35, 38, 40.

And, so we continue going round and round, and successively reducing the size of the circle:

2, 4, 8, 11, 16, 17, 22, 25, 29, 31, 35, 38.

2, 4, 11, 16, 22, 25, 31, 35.

2, 4, 16, 22, 31, 35.

4, 16, 31, 35.

16, 31.

So, this is the strategy that helped Josephus to plan his own and his friend’s survival!

Ref: Fun and Fundamentals of Mathematics by Jayant V Narlikar and Mangala Narlikar

More fun offered by Professor Narlikar to be shared later,

-Nalin Pithwa