Placeholder Image

字幕表 動画を再生する

  • 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², zeroand 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 skippedand 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.

So it's called the Josephus Problem.

字幕と単語

ワンタップで英和辞典検索 単語をクリックすると、意味が表示されます

A2 初級

ジョセフス問題 - Numberphile (The Josephus Problem - Numberphile)

  • 3 0
    林宜悉 に公開 2021 年 01 月 14 日
動画の中の単語