# The Josephus Problem - Numberphile

4M+ views   |   91K+ likes   |   1K+ dislikes   |
Oct 28, 2016

### Thumbs    ### Transcription

• 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!
• 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
• *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.
• *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 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?!
• 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.

### Description

The Josephus Problem, featuring Daniel Erman from University of Wisconsin-Madison.
Winning at Dots and Boxes: /watch?v=KboGyIilP6k
More links & stuff in full description below ↓↓↓

Correction: Around # that should be L less than 2^a NOT 2a --- Sorry, typo in editing! But you got the point hopefully.

Support us on Patreon: http://www.patreon.com/numberphile

NUMBERPHILE
Website: http://www.numberphile.com/
Subscribe: http://bit.ly/Numberphile_Sub

Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): http://bit.ly/MSRINumberphile