The Josephus problem. 100 people standing in a circle, 1 kills 2 passes the sword to 3….who survives in the end?
Have you ever heard about this problem where there are 100 people/soldiers in a circle (numbered in order from 1 to 100) and 1 numbered guy has a sword with which he kills 2 and passes it to 3, who kills 4 and passes it to 5, and it keeps on going such that a guy kills next person and passes it to next to next person until there is only one left alive. Question is who stays alive in the end of those 100 people? This problem is called Josephus problem though the narration starts with a story that 100 jew soldiers are trapped in a cave surrounded by roman soldiers, and they chose suicide over capture and followed the above procedure. Josephus problem wikipedia
PS: Don’t experiment with this question in real life. I had to lose very few friends I had.
The brute force (lame) method:
Though I am calling it lame, it is not. Actually I was able to look some patterns once I did this. What is lame is, if you do this and just stop with this. Write 100 (or 10 to get an idea) numbers down, just keep on crossing the numbers until one number is remaining.
Improvising brute force:
Here, we will exploit our knowledge in factors/multiples and powers of 2, for that we have to shift the numbers down to 0 to 99 from 1 to 100, so 1 is 0, 2 is 1…and 100 is 99.
round 1:0 kills 1, 2 kills 3…..98 kills 99, so we now have only even numbers, and 0 has the sword after this round.
round 2:0 kills 2, 4 kills 6…..96 kills 98, so only multiples of 4 are surviving now and 0 has the sword
round 3:0 kills 4, 8 kills 12…. 88 kills 92, and 96 has the sword, as all 97–99 are dead already (more precisely, there is no multiple of 4 between 96 and 99) , 96 kills 0 and gives the sword to 8, now only multiples of 8 are surviving except 0.
round 4:8 kills 16,24 kills 32…88 kills 96, (observe that 8(2l+1) is killing 8(2l+2), where l is number between 0 to 6), now only numbers of form 8(2l+1) are surviving, and 8 has the sword
round 5:8 kills 24, 40 kills 56,72 kills 88 (that is 8+16(2l) kills 8+16(2l+1) where l is a number between 1 to 3), now only 8,40,72 are alive and 8 has the sword
round 6:8 kills 40, 72 kills 8. But we have shifted everything down by a number right? (1–100 to 0–99) so, we have to shift it up now by 1. so the real survivor is 72+1=73
If you’re worried what has to be done if the starting guy(one with the dagger at the start of the process), you can remap numbers so that you can start from 0 and exploit the properties of (powers of 2)’s multiples.
Beautiful method:
Now employ improvised brute force method to n=1, n=2, n=4, n=8, n=16. n=32, n=64, n=128 starting where 1 numbered guy starts the massacre. You’ll be amazed to see that the guy numbered ‘1’ always survives, it’s easily deductible, shift everything to 0 to n-1 numbers and employ improvised brute force, after 1st round only evens survive, then 4 multiples, then 8 multiples…and after every round the sword comes back to 0th guy. so he survives in the end.
A generalization of the above statement is that when there are 2^n number of people in the circle, the guy who starts the killing is going to survive. (one way to see why this is true is to map numbers such that the starting guy is mapped to 0, guy next to him as 1 and all others accordingly, if you’re struck at that think of a circular dinner table, how will you serve food on it? you can start from any chair, because there is nothing called as a fixed starting point on a circular chair)
No, the point to note from previous paragraphs is when there are exactly 2^n people in the circle, the person who has the weapon at starting moment is going to survive. so given a number n, write it as n = 2^k + m where m is strictly less than 2^k. so, we can say that by the time m people are dead, the person who has the sword is going to survive, because by then there are exactly 2^k people alive.
Special case of this is when number 1 guy is starting the whole massacre. then we know ‘2m+1’th guy has the weapon by the time l people were killed. because 1 kills 2, 3 kills 4….and ‘2m-1’th guy kills ‘2m’th guy (who is mth kill) and gives it to 2m+1
Ex: n=100. n=64+36 (64=2⁶). so the answer should be the guy who has the weapon by the time 36 people are found dead. do it manually, 1 kills 2, 3 kills 4….71 kills 72 , by then 36 people are killed already and 73 has the sword, so he is the lucky(or sad if it’s Josephus’s story) survivor. Or, just blindly apply 2l+1, you get it to be 2(36)+1 = 73.
Beautiful method transformed into Binary :
So, if n = 2^k + m people are there in the circle, 1 is starting to kill fellow beings, we know that the answer is 2l+1, but should we always find n = 2^k + m manually?(i.e, k and l to satisfy that equation).
Binary is the saviour here(though it can not really save those soldiers, it saves us from some untidy calculations XD). If you don’t have any idea about binary system, you either learn it or suffer the mathematical wrath. but if you know binary, you are in for a treat.
The process is first write n in binary from, and you can straight away see that MSB (most significant bit) followed by zeros is nothing but 2^k and digits from 2nd MSB to LSB (least significant bit) is m.
Ex: 100 = 64+36 can be written as 64+32+4, that is in binary 1100100. and you can see that 1000000 (binary number of n, but everything except MSB is kept to be 0) is 64, which is 2^k .And 100100(binary number of n, where MSB is omitted) is 36 (which is m)
We want to 2m+1 right? so, what we can do is, move every binary bit in m to one place up by adding 0 as LSB (i.e, 100100 =36 can be turned into 36(2) =72 by adding a 0 next to LSB, that is 1001000, check the decimal value of it, if you can’t believe) and add 1 to that.
Putting everything together, it’s (binary number of n with it’s MSB omitted and a 1 added(not exactly added but kept) to the right of LSB) that is for 100 (decimal number) it’s binary is 1100100 and it’s solution is, omit MSB (which is 1 in this case) to have 100100 and add 1 to the right of it’s LSB (next to 0). so the answer is 1001001 which is 73.
And if you observe closely, whatever we did till now can be just done in this following one line. write n in binary, delete MSB(from the left most position) and add it to the right of itself (right most position) . This gives us the correct answer because MSB is always 1, we are omitting it from the start and adding it(1) to the right of LSB. exactly what we did in previous paragraph. this process is called right shift (if you’re familiar with CS or Data structures)
explanations to other solutions on internet:
There are quite a few answers on internet where there is barely any explanation is given, I’ll try adding explanations to those.
One of the answer is n -1’s complement of (binary representation of n).
I will provide a proof for this, 1’s complement of a number is (2^j-1)- n where j is the number of bits in binary representation of number n, actually 2^j is power of two which is just greater than n. so, if you remember k from earlier discussion, you can see that j = k+1.
So n -1’s complement of (binary representation of n) is n - (2^(k+1)-1-n)
==> 2n + 1 - 2^(k+1)
==> 2n + 1 - 2(2^k)
==> 2(n -2^k) + 1
==> 2(m) + 1
Exactly what we had proved in the earlier section. All the binary methods to solve the puzzle can be tweaked(mapping the starting point to 1) a little bit to still use the formulae even if the killing doesn’t start from number 1.
Find the code in python code here if interested.
This is an amazing puzzle, have a good time exploring this. look at this amazing video if you like it better listening to someone. Give a clap if you liked this, or correct my mistakes if there were any. Check my github and see if we are like minded.
Lastly, my sincere condolences for the deaths of people who were killed in the process of coming up with these solutions!
If you have time, read this related post https://medium.com/@sudheernaidu53/mbeewalk-bee-walk-spoj-17f71415bac2
