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