LOADING ...

The Josephus Problem - Numberphile

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

Thumbs

The Josephus Problem - Numberphile
The Josephus Problem - Numberphile thumb The Josephus Problem - Numberphile thumb The Josephus Problem - Numberphile thumb

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

Download subtitle

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/
Numberphile on Facebook: http://www.facebook.com/numberphile
Numberphile tweets: https://twitter.com/numberphile
Subscribe: http://bit.ly/Numberphile_Sub

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

Videos by Brady Haran

Brady's videos subreddit: http://www.reddit.com/r/BradyHaran/

Brady's latest videos across all channels: http://www.bradyharanblog.com/

Sign up for (occasional) emails: http://eepurl.com/YdjL9

Numberphile T-Shirts: https://teespring.com/stores/numberphile
Other merchandise: https://store.dftba.com/collections/numberphile

Keywords

numberphile

Trending videos