I Will Survive!

Probability Level 3

$100$ people stand in a circle in an order $1$ to $100$ . The first person has a sword and he kills the next person on his right (the second person) and gives the sword to the following right person (third person). All person do the same until only $1$ person survives. Which number was that?

The answer is 73.

3 solutions

Prakhar Gupta
Jan 26, 2015

Consider $2$ people standing, and $No.1$ has sword. Of course he will be last survivor.

If $4$ people are standing then again the $No.1$ will be the last survivor. (You can observe it).

Hence it can be concluded that if $2^{n}$ people are standing in a circle then the person having the sword for the first time will the ultimate survivor.

Let's use this newly found technique to the given problem.

We see that we have $100$ people, if we kill $36$ of these people than we will be left with $64$ survivors. The person having the sword when $36$ people are killed will be the ultimate survivor.

It can be easily seen that $73^{rd}$ person will be the ultimate survivor.

WOW! +1

Generalization: If there $n$ people, then the lone survivor is the $\left [ 1 + 2(n - 2^{\lfloor \log_2 n \rfloor}) \right ]^\text{th}$ person

Pi Han Goh - 6 years, 3 months ago

That's incorrect! It'll always give the answer as 1 which is wrong. Re-check your formula.

Nivesh Vyas - 5 years, 10 months ago

Man ..... its correct

I know where you made a mistake $\Rightarrow \left [ 1 + 2(n - 2^{\lfloor \log_2 n \rfloor}) \right ]^\text{th}$

Here we have to take highest integral function of ${\lfloor \log_2 n \rfloor}$

Akshat Sharda - 5 years, 10 months ago

Great.....thank you so much

Akshat Sharda - 5 years, 10 months ago

Does it work if it's not 2?

Norman Bintang - 6 years, 3 months ago

Woah cool! One wouldn't have thought of it this way! :P

Nivesh Vyas - 5 years, 10 months ago

Mahfuzur Rahaman
Sep 30, 2014

Let's solve this using pen and paper.

Firstly,

We have all the numbers (let, 101 is 1 in the circle):

1, 2, 3, 4, 5, 6, 7, . . . . . . . . . . . . 97, 98, 99, 100, 101

1 has the Sword, Common difference 1.

Secondly,

Cutting all the numbers of even positions (divisible by 2) we have:

1, 3, 5, 7, 9, 11, . . . . . . . . . . . . 95, 97, 99, 101

1 has the Sword, Common difference 2.

Thirdly,

Cutting all the numbers of even positions (if n-1 is divisible by 4 then they remain, others will be cut) we have:

1, 5, 9, 13, 17, . . . . . . . . . . . . . . . 93, 97, 101

1 has the Sword, Common difference 4.

Fourthly,

Cutting all the numbers of even positions (if n-1 is divisible by 8 then they remain, others will be cut) we have:

1, 9, 17, 25, 33, . . . . . . . . . . . . . . . 89, 97

Here, 101 is eliminated. So we do not have 1 anymore. Actually we have (let 105 is 9 in the circle):

9, 17, 25, 33, . . . . . . . . . . . . . . . 89, 97, 105

9 has the Sword, Common difference 8.

Fifthly, Cutting all the numbers of even positions we have:

9, 25, 41, 57, 73, 89, 105

9 has the Sword, Common difference 16.

Sixthly,

We have a small series now and we can easily see what will happen. Cutting even position numbers we get:

9, 41, 73, 105

9 has the Sword, Common difference 32.

Seventhly,

Cutting even position numbers we get:

9, 73

105 is no more. So we do not get 9 here. It has already been cut by 73.

Finally,

We got the number 73 that will survive :-)

Though it is long but can be a solution.

Barry Zhang
Feb 2, 2015

I Will Survive!

The answer is 73.

3 solutions

0 pending reports