The Josephus Problem | He Survived a Death Lottery 2,000 Years Ago | Induction Proof + Binary Magic

[00:00:00]Today we'll study a famous special case of the famous Josephus problem. So typically in a Josephus problem you'll be given the setup n people stand in a circle starting from a chosen person.

[00:00:15]Every kth person is eliminated and this counting it continues around the circle till only one person survives. We have to find the starting position of the surviving person. Now here in this famous special case every second person is eliminated.

[00:00:35]So here what we given is we are given n people are standing in a circle and they are numbered say 1 2 3 4 up to n and starting from this chosen person every second person is eliminated. So this two will be eliminated, four will be eliminated and this arrangement will continue until we have a last surviving person.

[00:01:04]Now this theorem says if n is of the form 2 ^ m + l where l lies between 0 to 2 ^ m then the position of this surviving person jn will be given by 2 l + 1. Now first we'll try to understand this. So suppose we have 13 people and they're arranged in a circle. So we have 13 people.

[00:01:40]So this is 1 2 3 4 5 6 7 8 9 10 11 12 and 13. Now starting from one every second person is eliminated. So this 2 4 6 8 10 and 12 they'll be eliminated. So after first elimination we'll have this starting from 13 1 5 7 9 and 11.

[00:02:19]Now 1 5 9 and 13 they'll be eliminated.

[00:02:27]Now for this next round it'll start from three. So it'll be 3 7 11. Now seven will be eliminated and three will be eliminated. So our surviving person will be J13. It'll be this 11th person. Now if we use this theorem we can write 13 as 2Q + 5. So here L is 5 and then J3 it will be 2 L + 1. So it'll be 2 into 5 + 1 which is 11. So this theorem says this 11th person is going to survive this elimination. Now we'll prove this result using strong induction. So the problem statement is we have people 1 2 3 4 n.

[00:03:19]So we have n people standing in a circle. Counting starts at person 1 and every second surviving person is eliminated.

[00:03:28]And if n= 2 ^ m + l where l between included zero to 2^ m prove that the survivor is given by jn which is the position 2 + 1 in the original setup.

[00:03:42]Now first what we'll do is we'll try and understand what each elimination round does. So suppose there are people numbered 1 2 3 4 up to n. Now in the first round every second person is eliminated. So all the even numbers they'll be eliminated and the survivors will be odd numbered person 1 3 5 and so on. Now after first round we have these people and this situation it becomes a smaller Josephus problem. Now here we have to understand the distinction between two cases. So if n is even say for example we have six people 1 2 3 4 5 and 6.

[00:04:34]Now here 2 4 and six they'll be eliminated and this new round it'll start at one. So this new round it start from 1 3 and 5. This is when n is even. And if n is odd, say n is 5, 1 2 3 4 5. Now 2 and four, they'll be eliminated. And here the next counting will start from five.

[00:05:05]So we'll have 5 1 and three. So in case of even this counting it starts from one and in case of or this counting it restarts from the last survival person. So we have to consider two cases case one when n is even and the second case when n is odd.

[00:05:25]So we have our first case when n is even and say this is 2 r.

[00:05:36]So we have 1 2 3 4 and two R people. Now in the first round all the even number people they'll be eliminated and we'll be left with this Josephus problem 1 35 up to 2 R minus one. So there'll be these R survivors.

[00:06:02]Now if we re label these R survivors as 1 2 3 up to R then in this second problem this R position it corresponds to 2 R - 1 position in original problem. So this originally 2 R + 1 person it'll be this R person in this new setup and suppose for this R person problem the person surviving is given by J R then for original problem J2R it will be 2 JR minus one.

[00:06:49]So if n is even then j 2 r will be given by 2 * j r -1. Now we'll consider the second case when n is odd. So we have this second case when n is 2 r + 1 that is when n is a odd number.

[00:07:17]So here we have 1 2 3 2 R and 2 R + 1. Now in this all the even numbered person they'll be eliminated 2 4 2 R and since one is the next person. So this one will also be eliminated. So in the first round we have eliminated R minus one people and then the surviving people will be 3 5 7 up to 2 R + 1. So again this becomes a smaller Joseph's problem of R people and we'll reabel them as 1 2 3 and R. Now here any r it corresponds to 2 r + 1 in the original problem. So r position in this second arrangement will correspond to 2 r + 1 position in the original setup.

[00:08:24]So for this smaller Joseph's problem, if the person surviving is J R then position of this person in the original game, it will be J2R + 1 and it will be 2 JR + 1.

[00:08:41]So this is the understanding that we'll need before we can apply strong induction to prove this result. So before solving we'll write these results. So if n is even then j 2 r is 2 j r - 1 and if n is odd then j 2 r + 1 is 2 j r + 1.

[00:09:13]Now our problem statement is if we assume n is of the form 2 ^ m + l where l lies between included 0 to 2 ^ of m then the position of a surviving person will be given by 2 l + 1 and we'll use strong induction on Okay. So first we'll prove the base case.

[00:09:49]Base case is when n is 1. Now we can write this n as 2 ^ 0 + 0.

[00:09:58]Here l is 0.

[00:10:00]So this j1 it will be 0 + 1 1. So this one person will be the surviving person.

[00:10:08]And this is fairly simple.

[00:10:11]Now we'll come to our inductive step.

[00:10:15]So first we'll prove it for even n.

[00:10:19]If n is even, we can take any rs 2 ^ m -1 + q where this q it lies between 0 and 2 ^ of mus 1. Now this 2 R will be 2 ^ m + 2 q where this 2q lie between included 0 to 2 ^ m. Now for this one l is 2q.

[00:10:57]Now from induction hypothesis we already know this JR it will be 2Q + 1 then for this 2 R we have already established this J2R it is 2 J R - 1 when N is even now JR in this case is 2 Q + 1 so it'll be this 2 into 2 Q + 1 - 1 and that'll be 4 Q + 1.

[00:11:34]Now Q is simply L by 2. So we can write this as 2 L + 1 and 2 R is nothing but N. So from here we can say this J N will be simply 2 L + 1. So if N is even then the survivor's position is given by 2 L + 1.

[00:11:54]Now if n is odd and say n is 2 r + 1 we can again write r as 2 ^ [clears throat] n -1 + q and again this q it lies between 0 to 2 ^ of n - Now 2 R will be 2 ^ n + 2 q where this 2q li 0 to 2 ^ m and we can write 2 r + 1 will be 2 ^ m + 2 q + 1. Now in this case your L is 2 Q + 1 and since this is odd it cannot change the power of two. So we have to choose L as 2Q + 1.

[00:13:02]Now for this R person Joseph problem we know position JR will be given by 2Q + 1. Then for this 2 R + 1 person's gain this J 2R + 1 it is 2 J R + 1 and it'll be this 2 into 2 Q + 1 F + 1 and 2 Q + 1 is nothing but L. So it'll be this 2 L + 1. So again for this JN will be 2 L + 1.

[00:13:42]So whenever this n is of the form 2 ^ m + l where l lies between 0 to ^ n m then position of the survivor will be given by 2 l + 1 and we have proved this result using strong induction.

[00:14:06]So let us take an example. Say for example suppose 100 people they stand in a circle and every second person is eliminated. We need to find the position of last person remaining. So we have to express this 100 to the highest power of two. Now highest power of 2 till 100 is 64. So there'll be 2 ^ 6 and then plus 36. So in this case L is 36.

[00:14:34]So the surviving person will be 2 into 36 + 1 and there'll be 73. So the surviving person would be this 73rd person. And without Joseph's result, you'll need a long simulation.

[00:14:55]If you look at this n, we have expressed this n as 2 ^ of m plus l which is highest power of two.

[00:15:06]So if we express this n in binary then it'll be written as 1 and then there'll be this b m -1 b mus 2 up to b.

[00:15:28]So this is its binary expression and this is your l. So this L it will be B MUS1 B MUS 2 up to B 0 to the base 2. Then this J N will be 2 L + 1 which in binary is expressed as B MUS1 B MUS 2 B KN and then 1 in base 2. So in binary what happened is the survivor's position of this number n it is given by rotating this binary representation left by one place. Now if you look at this problem then we know this 100 it is 2 ^ 6 + 2 ^ 5 + 2² its binary representation will be 1 1 and then two zeros and then 1 and then two zeros. So this is 100 expressed in binary.

[00:16:45]Now to find the survivor's position, we'll rotate it one unit to the left. So this JN will be given by 1 0 0 1 0 0 1.

[00:16:57]Now this is 2 ^ 6.

[00:17:02]This is 2 ^ 3. And this is 2 ^0. So this jn will be 64 + 8 + 1.

[00:17:15]which is 73.

[00:17:19]Now in PNC there'll be many cases where they'll give you the same setup of every second elimination but they generally write n as 2 to the^ n they'll say 64 people they stand in a circle and every second person is eliminated. Now in all these cases we know L is zero. So this surviving person in this case it will always be 2 into 0 + 1 which is 1. So in all these cases the surviving person will be the first person. So so J 64 will always be one or you can simply write this as J 2 the^ M will be one. This Josephus problem is attributed to a historical story. So this flavors Josephus was a real person and he was a Jewish commander who revolted against Rome. So in this war they lost the city fell and he and 40 other soldiers they hid in a cave. Now soldiers they preferred death to capture but this person Josephus he wanted to surrender. When he was outvoted, he proposed again. He said each man will be killed by the next in sequence. And he planned it in such a way that he and one other men they ended up as the last two and he persuaded the last men to surrender to the Romans. Though he attributed his survival to the chance or the prudence of God but given that he is the sole source and had every incentive to sanitize the story but generally it is agreed that the story that he computed the safe position all these claims are retrofitted.

[00:19:04]So the problem is named after him by the analogy not because he solved it but because people find this story interesting and that's how the legend propagates.