The Josephus Problem

The Josephus problem belongs to the history and is a perfect example that how mathematics can save your life.

There were Jewish soldiers who were captured by roman army, but in order to avoid the capture and probably torture they devised a method of suicide which will ensure the death of each individual. They formed a circle and numbered each member starting from 1 to n, n being the number of soldiers, they decided that the first person will kill the second one then next remaining alive person will kill next person alive to him and this goes on and the last person obviously has to kill himself.

However, there was a soldier named Josephus who preferred capture over suicide, so he wanted to know where he should take position so he remain alive as the last person

Here is the illustration how it works for n = 10.

What we do is, we will try to generalize this over n number of soldiers

For this problem we will try to understand using various values of n to get the safe position. Let f(n) be a function which gives the safe position for n soldiers, if we calculate will get these values.

Now a key point to observe in this table is that for the powers of 2 the winning seat is always 1 and using this point the problem is very easily solvable.

Mathematically,

if n = 2^a; f(n) = 1;

To understand why this is happening, consider this, when we have powers of 2 soldiers then after each cycle the number of soldiers becomes half and turn again comes in the hands of position no. 1, like for n = 8 , after first cycle the alive soldiers will be 4 and turn will be of 1st soldier then 2 again turn will be of 1st soldier, hence for 2^a no. of soldiers always 1st position wins.

This will be clear from the following figure

Now, what if the no. of soldiers are not even, well in that case we can write that number

as 2^a + c, where c<2^a.

Also, we know that if we have 2^a number of soldiers then the winner is the one who is having the turn so all we need to know is that whose turn it will be after c moves.

and that is equal to 2*c+1, or we can say for general f(n) = 2*c + 1 where n = 2^a + c and c<2^a.

Lets verify the table values against the formula we devised.

But according to history, there were 41 soldiers including Josephus.

Now, 41 = 2^(5) + 9, -> c = 9, -> f(n) = 2*9 + 1 = 19.

Hence, in order to survive, Josephus has to book seat number 19.

Thanks for reading, below is the link for the same problem solved in computer programming section.

http://sdjee2015.wixsite.com/whyandhow/single-post/2017/01/18/Josephus-problem