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.