Counting Joseph Flavius: whom to kill first

Original author: Numberphile
  • Transfer
image

A long time ago, during the time of the Roman Empire, a group of Jewish soldiers was surrounded by the Roman army. The choice is small - to surrender or perish. Tricky Jews came up with a system so as not to give up alive, and not to commit suicide. And so on, until only one remains alive, and only he will have to commit suicide. In the story I heard, the hero, Joseph , wanted to save his life and surrender, not die. And so he decided to find the cherished place.

(At the time of writing the post, the dofig of the painted soldiers died).

“I was in high school when Professor Phil told me to solve this problem.
He proposed to solve it manually, on paper. Take a different number of people and find a pattern, where n is the number of seats, and w (n) is the winner’s place. ”



Consider what happens with the example of seven people: 1 kills 2. 3 kills 4, 5 kills 6. Well, for 7 there is no 8, so 7 kills 1. Then 3 kills 5, 7 kills 3. 7 won.

image

This is Joseph, he wants to live.

image

Joseph had 41 people in the squad. And now this is serious.

Consider an example when there are 5 people in a group. 1 kills 2, 3 kills 4, 5 kills 1, 3 kills 5. The winner is 3.

For six. 1 kills 2, 3 kills 4, 5 kills 6, 1 kills 3 and 5 kills 1. Winner - 5.

image

Strange patterns appear. So far, the winner is an odd number.

image

Got on an even place - krants.

Now fill the table completely.

Take one person. Well. This man won, so it was easy.

If there are two people: 1 kills 2. 1 - the winner.

If there are three people: 1 kills 2, 3 kills 1. 3 won.

image


If there are four people: 1 kills 2, 3 kills 4, 1 kills 3.

If there are eight people: 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8, 1 kills 3, 5 kills 7, 1 kills 5. The winner is 1.

Well, the results are: 1, 1, 3, 1, 3, 5, 7, 9.
The result all the time increases by 2, but then it is reset at some point.

image


We’ll make it quickly to 13, we’ll get 11, and 14 will have 13.

Now we’ll see when there is a reset to one. Pay attention to the numbers that give you one. We can already guess that 16 will be the winner 1.

We conclude:
If n (number of people) is 2 in power, then the winning place is number one.

Now I will draw a larger diagram. Scheme for 16 people.
After the first round of murders, there will be half as many people, that is 8. Now again, we will start from the first. We go around in a circle, and again half as much, that is 4. We make another circle. There are two people left. We start from number one, and he wins.

Now consider what happens to numbers between 4 and 8.

The result is increased by two. But when I add 2 to 7, it turns out 9. Here and there will be a reset to 1. And now I can say that, any combination can be painted as 2 to the power plus some other number.

image


Let’s take the number 77. The largest number from which I can extract the root is 64. Then we get the sum: 64 + 13.

Then we write the same big numbers as 13 for the number 13: 8 + 4 + 1. The sum of the twos in degrees . 77 = 2⁶ + 2³ + 2² + 2⁰. The key point is that the degrees are not repeated, so we did everything right.

Now we derive the formula, where 64 (n) is 2 to the degree A + 13 is L, it turns out n = 2ͣ + l

13 we will write as the sum: 8 + 4 + 1 and substitute the formula n = 2ͣ + l (13 = 8 + 5)
And the odd number is the number of moves after which you need to stop.
I will take five steps. So: 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8, 9 kills 10. I stopped at number 11. Now look what happens: how many people are left? What remains is the root of the two. And as we know, the one who will win at the root of the two is the one who will start!

Now we look: 11 kills 12, 13 kills 1, 3 kills 5, 7 kills 9. Again we return to the eleventh, now there are only four people left. 11 kills 13, 3 kills 7. There are 2 people left and the eleventh begins. 11th won.

The theory is to paint a number by the formula, where L is less than 2 to the power of a. And the winning spot is 2L + 1.
Our last sum was 13 = 8 + 5, where 5 was L. Substitute in the formula and see that everything converges: 2 * 5 + 1 = 11

Let's get back to our task. There were 41 people in the squad. 41 = 32 + 9
Take our formula 2L + 1. Get 19

Draw a circle.
So, 1 kills 2 ...
We lose our even numbers.
41 kills 1, 3 kills 5 ... 19 kills 35, 35 kills 1 and 19 kills 35. The

formula that I wrote can be written in binary code. We write the sum of the degrees: 41 = 2⁵ + 2³ + 2⁰. The code is nothing but a power of two. And the code is a unit or zero. We write down, in order of two, to the left, the largest at the end, two to the degree 0. Where the degree corresponds to our value, we put 1, otherwise 0. 0. Thus we get: 2 получаем 2⁴ 2³ 2² 2¹ 2⁰. The binary code will be: 2⁵ is 1, 2⁴ is 0, etc. ... And we get: 101001.

And now I will show the main chip in solving the problem. The winning position will be your binary code, but the first digit needs to be moved back: 010011. It turns out: 2⁰ + 2¹ + (I missed 2² and 2³) + 2⁴. And here is the sum: 16 + 2 + 1, where the answer is 19.

That's the whole solution for our problem.

PS

And in this position Joseph did not abandon his prudence: in the hope of God's mercy, he decided to risk his life and said: “Once it is decided to die, so let's give the lot to decide who should kill whom. The one on whom the lot will fall will die at the hands of the person closest to him, and so we all will take turns taking death from one another and avoid the need to kill ourselves; it will, of course, be unfair if, after others have already died, one will think over and survive. ” With this offer, he again regained their confidence; By persuading others, he himself also participated in the lot with them. Everyone who fell on the lot, in turn, voluntarily gave himself to stab another comrade who followed him, since soon the commander was supposed to die as well, and death together with Joseph seemed to them better than life. By a fluke, or maybe by divine predestination, it was Joseph who remained the last with one more. And since he did not want to be killed by lot himself or to stain his hands with the blood of a compatriot, he persuaded the latter to surrender to the Romans and save his life.Judean War Book 3, Chapter 8, 7

Read more



About GoTo School


image


Also popular now: