The Josephus Problem — Who Will Survive?
(Image Courtesy: Numberphile)
The Josephus Problem goes back a long way. It is named after Flavius Josephus, a historian who lived around the 1st century BC. According to his account, he and 40 other soldiers were trapped in a cave by Roman soldiers during the siege of Yodfat. The men decided to commit suicide instead of being captured by the enemy. They decided to adopt a method of suicide by drawing random lots
The details after this point are a bit vague with no clear account of what exactly transpired. The story has been often repeated and the detail varies each time. The most common theory is that the men arranged themselves in a circular fashion and each person killed the person next to him. Some versions mention that each person killed the third person while some say 7th person. In this post, I will be going with the assumption that each person killed the person next to him.
The thing is, Josephus did not want to be killed and preferred surrendering. So, the big question here is: In which position should he stand to survive?
This article is based on a video I recently saw in a YouTube Channel called “Numberphile” of which I am a long time subscriber. If you are somebody who is into mathematics, I seriously suggest you to subscribe to their channel and go through their videos
Understanding the Problem
Let me explain the problem pictorially. Consider 8 people numbered 1 to 8 standing in a circle and assume we start from person 1 and move clockwise
Person 1 kills person 2. After this, 3 kills 4, 5 kills 6 and 7 kills 8 and we are back to person 1. One round has been completed and we are back again to person 1. 1, 3, 5 and 7 are alive
Now, 3 is the person closest to 1. Hence, 1 kills 3. Next in line is 5, who kills 7 (his immediate neighbour who is alive). We are back to 1.
The only remaining people are 1 and 5 and it is 1’s chance. No prizes for guessing what is going to happen. Yes. 1 will kill 5
We see that, out of 8 people, the person standing in position 1 survived.
Some Analysis
First, we need to see if we can figure out some kind of a pattern. For this, we need to try it out for various values and see for ourselves.
For 1 soldier and 2 soldiers, it is obvious that soldier in position 1 will be the survivor
When there are 3 people, 1 will kill 2. Next, 3 will kill 1. This leaves 3 as the survivor
With 4 people, 1 will kill 2 and 3 will kill 4. 1 and 3 are remaining and it is 1’s turn. Obviously, 1 kills 3, leaving 1 as the ultimate survivor
Similarly for 5 people, I have illustrated below. 1 kills 2 & 3 kills 4. Now it is the turn of 5, who kills 1 in the next round. Now, it is 3’s turn, who finishes off 5 to remain the lone survivor
You can try out on your own for 6 and 7 and for other higher numbers if you have a lot of time to kill
Find below the positions of the survivor from 1 till 16
A few points would immediately jump out when you observe the above table
Not very surprising if you think a bit. If you observe carefully, in all the cases, the people in the even numbered positions are eliminated in the first round itself. Hence, this leaves only the odd numbered people alive for the subsequent rounds
2. The next thing that you would observe is that, whenever the number of people are powers of 2, the person in the 1st position survives.
This is because, consider 16 soldiers standing in a circle. At the end of the 1st round of elimination, 8 soldiers remain (all even numbers killed).
As you can see from the above picture, if we re-number the remaining soldiers, it reduces to the situation of 8 soldiers with 1 at the starting position. This set of 8 soldiers, after another round of elimination, reduces to 4 soldiers with 1 at the starting position
Whether it is 2, 4, 8 or 16 or 32 soldiers, higher order powers of 2 get reduced to lower orders. This is the reason why for all powers of 2, the person in position 1 is the survivor. To summarize, the survivor in the case of 2 soldiers is the same as the survivor in the case of 4, 8, 16 and other higher powers of 2 (This is an example of recursion which I would have explained at the end)
What Is The Answer?
The steps to finding out the final answer are a bit complicated, requiring more detailed analysis. I do not wish to complicate things further for you. Those interested can check out the video from Numberphile (link provided under References) or this link.
The formula to calculate the position of the survivor for number of people(N) is:
- Take the number of people (41 in Josephus’s case including himself). Find the closest power of 2 lesser than that number. It is 32 in this case
- Now, write 41 in terms of 32 plus some number. Here, 41 = 32 + 9
- Take this 9. Multiply by 2 and add 1. You get 19
Hence, Josephus should stand in position 19 to avoid being killed
In Computer Programming
The Josephus problem is pretty famous in the world of Computer Science since it involves the concept of Recursion. Recursion is a concept in Computer Science where we make use of the same line/snippet of code repeatedly to find a solution. Recursion involves minimal usage of variables since it involves making use of the same piece of code repeatedly.
A classic example of recursion is finding the factorial of a number using recursion. It is enough if we know the factorial of 1(this is called the base case). Using this, we can find the factorial of higher numbers by making use of the same piece of code repeatedly
In a similar manner, the recursive solution for the Josephus problem is given by:
where n is the number of soldiers and k indicates that the kth soldier is killed after skipping (k-1) soldiers in between. (In our case, k=2 since we are skipping 1 soldier in between).
By substituting the base case (2nd equation) repeatedly in the general equation, we can calculate the position of the survivor for any value of n & k
Complicating It Further….
Here is an add-on to the above problem that you can
Now that Josephus has found out where he has to stand to survive, he needs to find out the position of the person who will be killing him so that he can strike a deal with him and avoid being killed. How will he find this out?
I will also think about it in the meanwhile
Thanks for reading!!!
References
Originally published at http://infinitesimallysmallcom.wordpress.com on January 31, 2021.
