The Josephus Problem – Numberphile

The Josephus Problem – Numberphile

So it’s called the Josephus Problem. It’s based on something from history. There was a group of Jewish soldiers who were surrounded by the Roman army and they didn’t want to get captured, so they decided to come up with a system- – to avoid getting captured or suicide. So they’d sit in a circle, and the first man would kill the guy to the left of him The next remaining living person would kill the next remaining living person with their sword. And they’d go around like this, till there’s only one person left, and the last person would have to commit suicide of course, rather than get captured. And the story – at least the story I was told, I’m not sure if this is historically accurate – Was that Josephus preferred captured than suicide, but he worried that if he said this, the other soldiers would turn on him. And so he wanted to figure out: WHERE should he sit within the circle- – in order to be the last man living. And then he would surrender, rather than kill himself. That was the problem It’s a little tricky, so let’s do a smaller example. Let’s say there are seven people. And so just to be clear, the way it works is:
person number one kills number two. Person number three kills four, Five kills six, But now things gets a little of harder to kind of see in advance Because seven, there is no eight, so seven kills one, Three kills five, Seven kills three. So seven’s the winner; seven is the last one left over. For Josephus, there were 41 people.
He needed to figure out where to sit. The mathematical problem is if there were n people. Where’s the winning seat? When I learned this problem I was in high school, And it was one of the first problems that got me to understand how you approach- – difficult and- and… Math problems where you don’t know the answer in advance, or someone hasn’t shown it to you in advance. And it was a professor of mine his name was Phil Hanlon who played a big role in, kind of, leading me to math. And he suggested: what we should do is we should gather data. Just… Take various values of n and just do it by hand and start looking for a pattern. I don’t know, maybe we should just do that? n is the number of seats,
and w of n will be the winning seat. And what we know so far is that:
n is seven, w of n it turns out is also seven. And so what I would do is I’d start doing some other values So, I don’t know, why don’t I do five? One kills two, three kills four, five kills one, three kills five. The winner is three. I guess there was no reason for me to skip six,
so why don’t we fill in six. One kills two, three kills four, five kills six… … one kills three and five kills one. The winner is five. So If you’re watching you might already start to notice some patterns. For instance, they’re always odd.
I mean, that’s maybe the first thing you notice And you can start asking “why are they always odd?”
And maybe you can already see that- – in the first loop around, all the even people get killed. So So you can – even with a tiny amount of experiment – start to see some patterns. – *Brady* So you DON’T want to sit in an even seat?
– Don’t sit in an even seat, no no no. And maybe we’re even getting some glimmers of other patterns But before I really try to phrase those,
I’d like to fill in the table a little bit more. So let’s do some. So if there’s only one person… well… That person’s the winner, so that one was easy. If there’s two people: one kills two. One is the winner If there’s three people: one kills two, three kills one. Three is the winner If there’s four people: one kills two, three kills four, one kills three. If there’s eight people: one kills two, three kills four, five kills six, seven kills eight, one kills three, five kills seven, one kills five. The winner is one. Alright so it was one, one, three, one, three, five, seven. One, three, five, seven, nine. And you could keep going,
but maybe you can see the pattern now? – *Brady* Is thirteen a one?
– NO! Good guess actually! But it is not a one. So let’s do thirteen. *Brady* This is good, I don’t know then, I can’t see the pattern. So as you see it’s jumping by two each time,
but then it resets at some point and And I want to go back to this, so we’ll see what thirteen is quickly So we didn’t reset that,
and I claim we won’t reset it the next one either. Fourteen will be thirteen and here, by the way, we’re be starting to make predictions. It’s worth noting we’ve- Even though we maybe can’t say
exactly what like 178 would be- – we’re starting to see well enough so we can make a prediction. So… so you could guess. Is it really true that fourteen is going to give you thirteen? We could do it out, and you’ll see in fact that’s what you’ll get So we’re getting some understanding… But I want to go back to this point you had, you asked if it’s going to reset and go back to one there And the answer was no, and it’s worth looking. Because this is the next thing I was going to do. Where do we get the ones? So if you look for a sec, there’s something very special about the numbers that give you ones. It’s the powers of two. And so maybe you can now guess that if i put in a sixteen, I would get a one back. And that’ll be right, and that’s actually going to be a real key in unlocking this. The professor I was learning this from made a really big point out of this. And I thought, you know, well I don’t know what the general answer is yet! And he made a big point: If you know something… Prove it, and make sure you really understand that one thing, and that often unlocks the rest. So So he really pushed us when I was first doing this, to try to state a conjecture and then prove a theorem- based on what we just saw here. And so that’s what I want to do, so here’s the conjecture: If n is a pure power of two, then the winning seat is one. I want to think about this for a second and maybe see why this might be true. So let’s do the next biggest power of two,
maybe the biggest one I can bother writing down. So let’s do sixteen So I want to do one pass through the circle. – *Brady* Take out all the evens.
– Take out all the evens. And now, fifteen has just killed sixteen. So I’ll put a little dot here so we’ll remember it’s number one’s turn again. And it’s number one’s turn again, and we’ve removed all the evens. And what’s left is therefore exactly half as many. So if i relabel at this point You can see that there’s a power of two to start with. I pass through the circle once, I get rid of all the evens, I have half as many. And I’m back at number one’s turn. So now if I do this again,
the same thing ought to happen. Right? I should kill all the evens on the new labeling And now there are four people left, and it’s STILL number one’s turn So you go through again… Kill those guys, there’s two people left,
it’s still number one’s turn- – and that one kills that, and it’s still number one’s turn and that chair wins. So let’s say we believe that.
We know what happens to two to the n. So how do we explain what happens between the pure powers of two? If you see the pattern, you know- we know what happens at eight, and we know what happens at four… … but between them it goes up by twos until at this point, if I added two to seven, I’d have a nine Which would be too big anyway, so that’s our reset But we knew it was going to reset because it’s a pure power of two. So how do we explain this jumping by two phenomena inbetween? So what I’m going to do- I’m gonna just mention that: For any number- – you can write it as
a big power of two plus something else Take the biggest power of two you can subtract from a number- And then what’s left should be smaller than that. When you express a number in binary notation- – ou choose zeroes or ones, and that gives it out as a sum of a bunch of powers of two… … and you just choose the biggest one. So 77. The biggest power of two I can get is 64. And then, what is it, it’s 64 + 13. So then for 13, the biggest power of two is
8 + 4 + 1. Did I do this right? 72… 77, there you go. And these are all powers of two! And this is unique. This is the unique way to write 77 as a sum of powers of two. Where no powers repeated, that’s a key point. So if you wanted to take a general number, take the biggest power of two – 64 – and then the remaining part. *Mumble* Twelve… Thirteen. I’m going to call this part two to the a,
and the remaining part I’m going to call l And I claim that this l is going to tell us which of those odd number between are going to show up. So let’s see how. How about we do thirteen. n is thirteen. This is the binary expansion, but using our new method the eight will be the two to the a- – and the five (which is the four plus one) that’ll be the l. And here’s the thing that’s going to happen with the l: I’m going to do five steps. So 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8, 9 kills 10. So now I’ve dropped… l people. And it’s number eleven’s turn. Now watch what happens, how many people are left?
Well what’s left is a power of two. And we know who wins in a power of two,
it’s whoever starts! *Brady* The first killer. The first killer! So now, if we go from here I claim that eleven is going to win. And just watch, it’s going to be. 11 kills 12, 13 kills 1, 3 kills 5, 7 kills 9 Back to eleven, and now there’s only four people left. 11 kills 13, 3 kills 7… Back to eleven, two people… Eleven wins. And so this is really the key to the final answer. Which is If you’ve written your number as two to the a plus l- – after l steps, whosever turn it is is going to win. Because it’s going to be their turn and there’ll be a power of two left. And so the winning seat will be two l plus one. If you write it in this way, because that’s whose turn it is after l steps. The theorem or the claim, is that if you’ve written n in this way… So if n is two to the a plus l, where l is less than two to the a. It has to be strictly smaller So in other words: two to the a is the biggest power that sat inside of n. Then the winning seat is going to be 2 l plus one. So we’ve already seen it was true here, right? l was five and the winning seat was eleven, which is two times five plus one. And if you start going back through you’ll see it’s the same thing for all the answers. We’ve already illustrated the mechanisms, which is after l steps- It’s the turn of person 2 l plus one, and after l steps, there are a power of two number of people left. and… Everyone knows that the power of two people, the first person who kills, that’s who’s going to be the winner *Brady* Let’s see if Brady has learned! *chuckle* Yeah! Alright! Let’s do it *Brady* – I think I follow. Now in the Josephus problem… – Yep! – … There was Josephus and 40 soldiers. – That’s right. Oh yeah! We got to go back and do that! – Alright so we got 41 people… – So n is 41 – Alright, now I think – expressing that in the way you told me to – it’s going to be 32 + 9? – There you go, 32 + 9 – So… Two lots of nine… plus one… – Mhm – … is nineteen – There we go – So we want to sit in position nineteen. – There you go. You want to sit in the nineteenth chair. So here we go we’re going to do n=41 – Alright. Put them in, in the cave, waiting their fate. – Not a very good circle but… – It’s getting smaller now… – I know. *Brady and Daniel chuckles* *Daniel chuckles* Should I redo this? – Nah you’re okay. *Daniel mumbles* 40… 41… – Okay there we are.
So we got a little tight at the end – Look at that, this is a lession about
planning ahead, people. Okay so let’s do it. So one kills two… – We’re losing our even numbers. – Yep. Okay now… 41 kills 1. *Daniel mumbles* three kills five… And 19 kills 35 and there we go! – Alright. I was right! – There we go, nineteen! Oh and one other thing in this
problem which is kind of fun… So this formula I wrote can be interpreted in binary notation. When we wrote a number as a sum of powers of two… This can be re-expressed in binary notation. So what was this… 32 + 8 + 1 So that’s… 2⁵ + 2³ + 2⁰ And binary notation… The digits correspond to the various powers of two, and all the digits are either zero or one. So 41 in binary notation would be
one copy of 2⁵, zero of 2⁴, one of 2³, zero 2², zero 2¹ and one 2⁰ Here’s the trick for the Josephus problem. Which I won’t justify but it’s super cool,
and you can try it own your own. The way to find the winning solution if this is n- – the winning solution in binary is you take the leading digit- – and you put it at the end. So in other words I claim that if I write *Mumbles* Zero… One… So I take this part and then I add the first digit to the end. That number in binary code is… Well let’s see… It’s 2⁰ + 2¹ + (I skipped 2² and I skipped 2³) and I add 2⁴ So it’s 2⁴ + 2¹ + 2⁰ Which is 16 + 2 + 1 Which is nineteen, which is exactly what the winning seat was. and… And so there’s this super efficient way in binary code to jump straight from the number n- – to the winning number w of n. So if you’re writing you numbers in binary code, the pattern would’ve been even more quickly apparent Isn’t that cool?! *Brady agrees and chuckles* Isn’t that cool? – Yeah This video was filmed at the
Mathematical Sciences Research Institute (MSRI) That’s the building behind me. If you’d like to find out more about them, link’s in the video description. They do some really important serious mathematics here, and they’re also a big supporter of math outrage. As evidenced by this video.

100 thoughts on “The Josephus Problem – Numberphile

  1. The binary trick is trivial: if you remove the first one the rest is l and if you then put the one behind you multiply everything with 2, because you shift every bit to the left by one bit and add one because now on 2^0 there is a one. And he already showed why it's: 2l +1

  2. Here's the math on how many guys were killed in this video: (12+7+5+6+2+3+4+8+13+16+13+41)-12 = 118, or 1110110, if you prefer 😀

  3. This only works if you know where seat 1 is, and who's going first. Sitting in a circle just says that someone random is going to start the killing.

  4. What if josephus had a friend Jimmy who also wanted to live? And they want
    wanted to coordinate them being the last 2 survivors? How can one represent this as a function?

  5. Here is the justification of the binary "trick". By converting N to binary, the leftmost bit will be the 2^a part which we don't care about. The remaining part is the "L" that we have to multiply by 2 and then add one. In binary multiply by 2, just by adding a zero at the end of the number( just like you multiply with 10 indecimal) Then just add one. So taking the first bit and attaching it to the end, just does that, which is cool.

  6. Now Josephus just has to count his way to the 19th position without letting on to the others what he's up to…

  7. If you enjoyed this video, you must threaten to beat yourself up if you don't hand over your own milk money to yourself.

  8. I’m pretty sure the cycle resets at powers of 2. 2 gives you 1. 4 gives you 1. 8 gives you 1. 16 will give you 1. 32 will give you 1. 64 will give you 1 and so on and so forth until the end of infinity itself. It is always powers of 2.

  9. Btw, Josephus would want to be the 19th person in the circle. If it were 42, that would be 21. 43 would be 23. 44 would be 25 and so on until you hit 64 which is 1.

  10. Josephus could've been like my dudes, there is no way I'll slay my brethren. I shall go out there and die in battle.

  11. i am guessing that you are going to entirely get away with this unlike count dankula for his "gas the jews" video..

  12. The binary number explanation is not really that hard, its actually really simple, I don't know why he didn't explain it as if it is something really hard. Its just that in the binary number variant, the position of the first 1 (the left most one) would be exactly 2 to the power of a as in the other solution (101001 -> 100000 in binary is 2^5 and then the rest is 001001 which is 9, or on other words 32 + 9 = 41). Now if you take the 9 (001001) and you shift it left 1 position (which means to add a 0 at the end, which in binary numbers is exactly multiplying by 2) it will become 0010010 and if you add 1 it will be 0010011, which will be (9 * 2) + 1 or as in the solution (L * 2) + 1

  13. Spoiler alert:

    In the example, every power of 2 less than 5 would be a sumand of l. moving those following digits each one spot left is the same as doubling l, the leading digit appearing as the unit would be the same as adding 1 to 2l. Well done!

  14. I feel like it would have been faster for Josephus to just work out the position for 41 people instead of finding all these patterns and then applying them to his specific case

  15. It is also interesting to note, that when the total number of seats has a value closer to 2^(a+1) instead of 2^a, then it is simple to find the position 'from the back'.
    Just take [ n = 2^(a+1) – k ] instead of [ n = 2^a + l ] as shown in the video.
    Then the k-th position "from the back" is where the person needs to sit. This position would be [2^(a+1) – ( k – 1 )] which would be the same as from the method [ 2.l + 1 ] .

  16. I swear I am the most incompetent person on earth when it comes to math, I have peepee in my eyes that I actually understood everything first try

  17. Worth noting: the winning seat's number isn't "reseting", so much as it is "looping". It's 1 when there are eight seats, because it was 7 last and should be 9, but if you only have 8 people the 1st person is the 9th, the exact same way a 3-bit binary number loops back to 0 (000) instead of continuing to 8 (1000).

  18. One question: why would the soldiers turn on Josephus if he revealed he would prefer capture? You’d think they would make use of it and deliberately let him be the last one if he so wished.

  19. The problem is that in a circle, no one knows which place is 1 when everyone takes their place. This only works if the positions are pre-known. If the participants take a stand in the circle, they will likely choose the starting position by random. This whole strategy fails.

  20. But there is no way to tell in a circle of people, who is number one. This problem is not probable in real life applications.

    says the guy who dies at number 34

  21. Maybe it was the othet way round: josephus was so surprised to be the last man standing that he decided to not commit suicide but find out what freaking order of the universe made him sit at the right position…

  22. Could 3^a+L apply if you were to skip two people instead of one? Say theres 9 people in a circle, #1 skips #2 and #3 and kills #4? I think that wouldnt work though, something is telling me it wont work

  23. But what if they all wanted to be captured. But they didn't want to say it because they could be turned on. By their other friends who also didn't want to die. But hey, that's just a theory

  24. This is a classic example of making a problem much harder than it needs to be. You assume the the direction of action is clockwise. When really he would just sit with the first person to be killed on his right. Then let the action go CCW where the person who last killed someone is the next to die…..I highly doubt if the scenario ever happened and if it did there is little to no chance they wondered how to execute it. K.I.S.S.

  25. Binary swapping the first 1 to last is simply subtracting the biggest 2^a from number and adding 1 at the end of the binary number is multiplying with 2 +1. You could have just explained it.

  26. If the winning seat is 2L+1, what that binary trick does is remove the top power of 2 entirely, the left shift in binary is exactly the same as multiply by 2, and adding a 1 at the far right is the "+1" part of the formula. So you haven't really moved the 1 from the left to the right; you DROP the 1 on the left, shift everyone left one column, and insert a 1 at the least significant digit place.

  27. So instead of being nicknamed the Serial Killer, you might label the "winner" here the MSB-to-LSB Binary-Digit-Transfer Killer . . . – j q t –

  28. I'd have been real suspicious if Josephus was the guy who came up with this contrived system and also took like half an hour to decide on where he wanted to be seated.

Leave a Reply

Your email address will not be published. Required fields are marked *