The Josephus Problem - Numberphile

Key Takeaways

So, it's called the Josephist problem. It's based on 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 to come up with a system to avoid getting captured or or suicide. So, they'd sit in a circle, and the first man would 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 then 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 this is historically accurate, uh, was that Josephus uh, preferred capture to suicide, but he worried that if he said this, the other soldiers would turn on it. And so he wanted to figure out where should he sit within this circle in order to be the last man living. Uh, 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 were 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 get a little harder to kind of see in advance cuz seven there is no eight. So seven kills one. Three kills five. Seven kills three. So seven's the winner. Seven's 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. Uh, and it was one of the first problems that got me to understand how you approach difficult and and math problems where where you don't know the answer in advance where someone hasn't shown it to you in advance. And it was a professor of mine, his name was Phil Hanlin, who who played a big role in kind of leading me to to to math. Um, 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 so 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? So 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 kills two three kills four five kills six kills three 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 to ask yourself why are they always odd and maybe maybe you can already see that right the first loop around all the even people get killed. So so you can even with just a tiny amount of experiment start to start to see some patterns. 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's the winner. If there's three people, one kills two. Three kills one. Three's 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. Winner is one. All right, 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. I think it's 13 or one. No. Good guess, actually. But it's not a one. So, let's do 13. 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 13 is quickly. So, we didn't reset there. I claim we won't reset at the next one either. 14 will be 13. And and here, by the way, I'm we're 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 to see the pattern well enough. We could make a prediction. So, so you could guess is it really true that 14 is going to give you 13? And and we could do it out and and you'll see in fact it that's what you'll get. So, so we're getting some understanding. But I want to go back to this point you had. You asked if it was going to reset and go back to one there. And and the answer was no. And it's worth looking because 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 16, I would get a one back. And and that'll be right. And that's actually going to be a real key um in unlocking this. The professor I was learning this from made a really big point out of this. And 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, and so that's what I want to do. So, here's the conjecture is that if n is a pure power of two, then the winning seat is one. I want to think about this for a second and 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 16. So, I want to do one pass through the circle. Take out all the evens. Take out all the evens. And now 15 has just killed 16. So, I'm going to put a little dot here so we 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 reabeled at this point, you can see that there was a power of two to start with. I passed through the circle once. I get rid of all the evens. I have half as many and I'm back at number one's term. So now if I do this again, the same thing ought to happen, right? I should kill all the evens under 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 now one kills that and it's still number one's turn and that chair wins. So let let's say we believe that we know what happens for two to the n. So how do we explain what happens between the pure powers of two? If you see the the pattern, you know, we know what happens at 8 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 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 in between? And so what I'm going to do, I'm going to just mention that for any number um you can write it as uh 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, you choose zeros or ones and that gives it 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 of powers of two um where where no power is 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 123. I'm going to call this part 2 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 numbers between is going to show up. So let's see how how about we do 13. N is 13. 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, one kills two, three kills four, five kills six, seven kills 8, 9 kills 10. So, now I've dropped L people and it's number 11'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. The first killer. The first killer. So now if we go from here, I claim that 11's going to win. And just watch. It's going to be 11 kills 12. 13 kills 1. Three kills five. Seven kills nine. Back to 11. And now there's only four people left. 11 kills 13. 3 kills 7. Back to 11. Two people. 11 wins. And so this is really the key to the final answer, which is if you've written your number as 2 to the A plus L, after L steps, whoseever 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 and so the winning seat will be uh 2 L + one if you write it in this way because that's whose turn it'll be after L steps. The theorem or the claim is that if you've written n in this way, so if n is 2 to the a plus l where l is less than 2 to the a, it has to be strictly smaller. So in other words, 2 a is the biggest power that sat inside of n. Then the winning seat is going to be 2 L + 1. So we've already seen it was true here, right? L was five and the winning seat was 11, which is 2 * 5 + 1. And if you start going back through, you'll you'll see the same thing for all the answers. We've already really illustrated the mechanism which is after L steps it's the turn of person 2 L + one and after L steps there are a power of two uh number of people left and and when there's a power of two people the first person the first person who kills that's that's who's going to be the winner. Let's see if Brady has learned. Yeah. All right let's try this. I I think I followed now in the in the Josephus problem. Yep. There was Josephus and 40 soldiers. That's right. Oh, yeah. We got to go back and do that. All right. So, we've got 41 people. So, n is 41. All right. 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 + 1 Mhm. is 19. There we go. So, we want to sit in position 19. There you go. You want to sit in the 19th chair. So, here we go. We're going to do n= 41. All right. Put them in in the cave waiting their fate. Not a very good circle, but small one. I know. Should I redo this? No, you're okay. 40 41. Okay, there. There we are. So, it got a little tight at the end. Look at that. This is a This is a lesson about planning ahead, people. Okay, so let's let's do it. One kills two five. We're losing our even numbers. Yep. Okay. Now 41 kills one. Three kills five. And 19 kills 35. And there we go. All right. I was right. There we go. 19. Although one other thing in 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 a sum of powers of 2, this can be reexpressed in binary notation. So what was this? 32 + 8 + 1. So that's 2 5 + 2 cub + 2 0. And binary notation the digits correspond to the various powers of two. And all the digits are zero or one. So 41 in binary notation would be one copy of 2 to the 5th 0 of 2 4th one of 2 to the 3r 0 2^2 0 2 1st one here's a trick for the josephice problem which which I won't justify but it's super cool and you can try it on 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 0 1, 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 to the 0 plus 2 the 1 plus I skipped 2 ^ 2 and I skipped 2 cubed and I add 2 4th. So it's 2 4th + 2 1 + 2 0 which is 16 + 2 + 1 which is 19 which is exactly what the winning seat was. And and so there's this this super efficient way in binary code to jump straight from the number n to the to the winning number W event. So if you're writing your numbers in binary code, the pattern would have been even more more quickly apparent. Isn't that cool? Yeah. Yeah. Isn't that cool? 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, links in the video description. They do some really important serious mathematics here and they're also a big supporter of math outreach as evidenced by this