Who will be the survivor?

Josephus Puzzle: Who will be the Survivor?

In this puzzle you will have to Find Who will be the Survivor?
There were a hundred people brought in front of the king for execution.
The king ordered them to stand in a circle, and gave each of them a sword. He instructed one person to kill the person next to them and then the person after will kill the person to their next and this pattern will go on, until the last survives. The last one who survives, the king will grant that person freedom.

Question:-

Following this pattern, find out Who will be the survivor?

Who will be the survivor?

Solution

Let us number 100 people from 1 to 100. Therefore from the pattern given in the question, the person at no.1 will kill no.2 and then no.3 will kill no.4 and this will continue.

Following this execution style, the person marked at 73 will win.

How?

There are several methods with which we can determine the answer of Who’s the survivor Puzzle.

Method 1: 

The first method to solve this problem “Who will be the survivor?” is to simply write down 1 to 100 in a circle, and start cutting off the people as mentioned above.

Round 1:- 1, 2, 3, 4,....15, 16, 17, 18, 19.33, 34, 35,..45, 46, 47, 48...76, 77, 78, 79, 80…. 98, 99, 100

Round 2:- Starting from 1 everyone kills the person next to them, i.e., all even numbers are
      killed, therefore we are left with:
        1, 3, 5, 7, 9, 11, 13, 15, 17..35, 37,.…71, 73, 75, 77, 79, 81...95, 97, 99(all odd numbers)

Round 3:- Again starting from 1, elimination is done, such that 1 kills 3, 5 kills 7 and so, and we are left with:
        1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 68, 73, 77, 81, 85, 89, 93, 97

Round 4:- Again the elimination is conducted, where 1 kills 5, 9 kills 13 and so on, and we are left with

        1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97

Round 5:- Since here 97 was the last person with the sword, this round starts with 97 killing 1, then 9 killing 17
and so on:

        9, 25, 41, 57, 73, 89

Round 6:-Previously 89 kills 97 and fives the sword to 9, who starts again:

        9, 41,73

Round 7:-  73 gives the sword to 9 and in the last round 9 kills 41 and gives the sword to 73 and 73 kills 9 and survives.

Method 2:

The problem “Who will be the survivor” with the above method is that it is too long and tedious. Therefore the second method is more preferred. This method is more logical rather than brute force like the previous method.

In this method we use the formula 2^k + l, where the number of survivors can be calculated by 2(l)+1.

Below we have given the logical proof behind the formula.

Proof:-

Before counting for 100, first let us try and count for a smaller number, say 7.

Using brute force method let us see which person will survive for 7 people in a circle.

 Round1:- 1 2 3 4 5 6 7
1 kills 2, 3 kills 4, 5 kills 6, 7 kills 1


Round 2:-
3 5 7

3 kills 5, 7 kills 3

         7 survives

Let us try the same for 8 and for 4.

Round 1:- 1 2 3 4 5 6 7 8
1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8

Round 2:- 1 3 5 7

1 kills 3, 5 kills 7

Round 3:- 1 5

1 kills 5

1 survives

Round 1:- 1 2 3 4
1 kills 2 and 3 kills 4

Round 2:- 1 3
1 kills 3

1 survives

Therefore if we are to calculate the survivors for number 1 to 10, we get the following:-

  • For 1 person, the survivor will be no. 1.
  • For 2 people, survivor will be no.1.
  • For 3 people, survivor will be no.3.
  • For 4 people, survivor will be no.1.
  • For 5 people, survivor will be no.3.
  • For 6 people, survivor will be no.5.
  • For 7 people, survivor will be no.6.
  • For 8 people, survivor will be no.1.
  • For 9 people, survivor will be no.3.
  • For 10 people, survivor will be no.5.

From the above details, we can see that for all powers of 2, number 1 i.e The person who starts survives. To check this hypothesis, let us take a random power of 2, say 64. Let us see if number 1 is the survivor or not.

Round 1:- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

Round 2:- 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59

Round 3:- 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57

Round 4:- 1 9 17 25 33 41 49 57

Round 5:- 1 17 33 49

Round 6:- 1 33

Round 7:- 1 kills 33 and survives

Thus we can say that any power of 2, i.e., any number which can be represented as 2^k, the survivor for that number will be 1. Now for numbers that are not powers of 2, can be broken down as 2^k + l, e,g.,

7 can be represented as 2^2 + 3, where k = 2 and l =3.

From the table, if we see the survivor for 7 is 7. Now if we are to write 7 in terms of l, we get

2(3)+1 = 7

Let us try this for 5, 5 can be represented as 2^2 + 1.

substituting 1 in 2(l)+1 we get, 2(1)+1 = 3, which is the survivor number for 5(from the table)

Therefore from the above deductions we can finally predict that for a number of n, which can be represented as 2^k + l, the survivors can be calculated by using 2(l)+1. 

So for 100 it will be: 64+36

                                 2^6 + 36

l= 36, and the survivor = 2(l)+1= 2(36)+1 = 73

Therefore in the second method we will use the formula 2(l) +1 to find the survivor’s number.

Most Asked Puzzles

josephus puzzle solution in detail

Most Viewed Puzzles

josephus puzzle solution in detail