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.
This was a terrific episode. I really enjoyed it.
The animations on this one were so well done! Interesting topic too.
What a cool episode! One of the few I actually understood lol
There is also a formula for if you change the number that you skip over from one to two, etc. Wikipedia
The trick at the end with shifting the binary digits over was really cool. Suddenly this arbitrary problem we solved has an intrinsically deeper connection to numbers themselves.
Great video, Brady. If only mathematicians could come up with some less morbid scenarios :)
I'm curious to know what animation software you use? This episode was excellent!
Fuck.
I'm currently trying to figure out how the algorithm would differ if instead the first person killed "two birds with one stone" (killed two people next to him instead of one). Any help would be appreciated