Flavius Josephus (Solution)

Contexto Histórico

Recapping, the Jewish rebels planned to organize themselves in a circle, where each one would have the task of killing the companion to their left in a clockwise direction. Initially, the Jew in position 1 should kill the one in position 2, and in the same way, the survivor who was after the first to die would kill the one alive to their left in a clockwise direction. This process would continue until only one Jew remained, and this last one should fulfill the pact with the others by taking their own life. However, Josephus had other plans and began to think about which position he should occupy to ensure that he would be the last survivor, thus avoiding someone killing him. He did not intend to commit suicide.

This is a very interesting mathematical problem. The central question is, “What would be the position P of the survivor in a circle with n people if the process starts at position 1?”

This problem does not have an obvious solution. When faced with a problem for which we don’t have a clear idea of how to solve it, it’s promising to test specific cases and look for patterns in the answers. To simplify the problem, we can analyze it for small values of n and observe the results. Let’s simulate the first few values:

– For n = 1: nothing happens, because there is only one rebel, and he survives.
– For n = 2: the rebel in position 1 kills the rebel in position 2. Therefore, the first survives.

Let’s analize more cases and write down these simulations on a table. (We sugest you to use the simulator, change the values, and watch what happens).

– For n = 3: the first one kills the second one, the next Jew is the third, which kills the first one. The third one survives.
– For n = 4: First kills second, third kills fourth; and finally, the first one kills the third one and survives.

So far we couldn’t conclude anything, then let’s try more cases and fill the table below (check the values by using our simulator):

Now, spend some time analizing the table and try finding patters…

• The survivors’ positions are always an odd number, that happens because we start with an odd position and the elimination proccess takes place in pairs (a Jew kills another), in a wat that in the first round, all the jews in an even position are eliminated;
• As we increase the value of n, the survivor’s position seems to follow a pattern in a spiral way: 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1. They increase, go back to position 1, and then, keeps increasing again and the proccess repeats;
• When the total number of people in the circle is a power of 2, the survivor will always be on the first position (position 1), therefor, position 1 is ideal for n=1,2,4,8, which correspond to powers of 2, 1=2^0, 4=2^2, 8=2^3, 16=2^4.

From the third observation, we can suppose that every time the number of rebels is a power of 2, the survivor will be the person in position 1. Although this is true for the first numbers in the table, we need to prove that it always holds. Fortunately, for this case, we can observe that if n is a power of 2, n=2^q and in the first round, all even positions are eliminated (the rebel in position 1 kills the one in position 2, the one in position 3 kills the one in position 4, the one in position 5 kills the one in position 6, and so on). 

Notice that in the first round, we have 2^q, in the second round n/2=2^q/2=2^{q-1}, because half of them die… until we reach 2^0=1, for a k number of rounds. Note that in all these cases, each round always starts with the first rebel (in this case, the rebel in position 1).

Example: n=64 =2^6
1st round: 32 die (the rebel in position 1 kills the one in position 2… the rebel in position 63 kills the one in position 64, ending the first round);
2nd round: initially, there are 32 rebels, and it starts again with the rebel in position 1 killing (in this round, he kills the rebel in position 3), 16 die;
3rd round: 8 die;
4th round: 4 die;
5th round: 2 die;
6th round: 1 dies, leaving the survivor in position 1.

We know that the first position belongs to the survivor whenever n is a power of 2, but what happens when n is not a power of 2?

We can write any number n as the sum of a power of two and another number that is less than that power of two, that is, n = 2^k+r, with r < 2 ^ k. It may seem complicated, but let’s give an example. Take n=19 and take the largest power of 2 less than 19. We’re talking about 16=2^4, so our r will be 3, which is the difference between 19 and 16. So, we can rewrite 19=16+3. Now, what happens after 3 of these 19 people die? In this case, there will be 16 people left, and we know that the first one to start the killing when there are 16 people (because it’s a power of 2) is the survivor. To have 3 of them die, 3 others must have killed them, as shown in figure 3a. In this case, 16 remain, and the first one to start the killing is in the 7th position. Notice that r=3 and the survivor will be at 2r+1 (the next one to start killing when 16 rebels remain).

Let’s repeat the reasoning for n=21. In this case, we can rewrite n = 16+5 (or n=2^4+5) and to have 5 deaths, in the last step, the 9th person kills the 10th, leaving 16 rebels with the 11th being the next to kill, meaning the rebel in the 11th position is the first to start killing among the 16, and as we know, this person will be the survivor. See the simulation in figure 4.

In general, for n being the number of people, we write n=2^q + r, where 2^q is the largest power such that 2^q \leq n. In this case, the survivor will be at position 2r+1.

What we did was construct the general case, a complete and very interesting solution, and the induction proof was done by Felippe Calsavara Gonçalves and Fernando Pereira de Souza in their work “THE FLAVIUS JOSEPHUS PROBLEM” in the journal Colloquium Exactarum, Vol.10 N.3, and it can be found at this link: here.