IQ Question:
Suppose there are 100 people standing in a circle ??.
The first person?? has a gun?? in hand. What he has to do is shoot the second person and then pass the gun to the third person. Now, the third person kills the fourth person and gives gun to the fifth person.
This process is carried till there is only one person surviving ??.
Can you find out who survives at the end.
Solution : 73rd person
Here's the generalized formula to find the solution for N people:
Find the largest integer 'k' such that 2k≤N
The answer is then: 2∗[N−2k]+1
In this case, N = 100. The largest integral k is 6, as 26=64, and 27=128
Thus, the answer is 2∗(100−26)+1=73, i.e. the 73rd person will be left standing
Explanation :
This was my reasoning (there may very well be a neater solution):
It's easy to see that as long as the number of people is a multiple of 2, after a complete round, the gun will return to the person numbered "1" [i.e. 1 kills 2, then 3 kills 4, then 5 kills 6, ....... 99 kills 100 ... and the gun returns to 1]. Also, the number of people left after a round is reduced to half.
Thus, if the total number of people is a power of 2, the number of people left after each round is a multiple of 2. And hence, the last person to remain would be "1".
With that in mind, we try to reduce the number of people (from 100) to a power of 2. What's the closest such power? 64. To get to this number, we need to kill 100-64 = 36 people.
Now, in the first round, the first 36 people to be killed would be: 2,4,6,8,....72. Thus, after 36 kills, the 73rd person would be handed over the gun.
Starting with the 73rd person (our new number "1"), we continue the game. Note that there are 64 people left now. Since this is a power of 2, the gun will keep returning to him/her after every round. Thus, (s)he would ultimately be the lone survive.
The logic, when generalized to N people, results in the formula mentioned above.
Suppose there are 100 people standing in a circle ??.
The first person?? has a gun?? in hand. What he has to do is shoot the second person and then pass the gun to the third person. Now, the third person kills the fourth person and gives gun to the fifth person.
This process is carried till there is only one person surviving ??.
Can you find out who survives at the end.
Solution : 73rd person
Here's the generalized formula to find the solution for N people:
Find the largest integer 'k' such that 2k≤N
The answer is then: 2∗[N−2k]+1
In this case, N = 100. The largest integral k is 6, as 26=64, and 27=128
Thus, the answer is 2∗(100−26)+1=73, i.e. the 73rd person will be left standing
Explanation :
This was my reasoning (there may very well be a neater solution):
It's easy to see that as long as the number of people is a multiple of 2, after a complete round, the gun will return to the person numbered "1" [i.e. 1 kills 2, then 3 kills 4, then 5 kills 6, ....... 99 kills 100 ... and the gun returns to 1]. Also, the number of people left after a round is reduced to half.
Thus, if the total number of people is a power of 2, the number of people left after each round is a multiple of 2. And hence, the last person to remain would be "1".
With that in mind, we try to reduce the number of people (from 100) to a power of 2. What's the closest such power? 64. To get to this number, we need to kill 100-64 = 36 people.
Now, in the first round, the first 36 people to be killed would be: 2,4,6,8,....72. Thus, after 36 kills, the 73rd person would be handed over the gun.
Starting with the 73rd person (our new number "1"), we continue the game. Note that there are 64 people left now. Since this is a power of 2, the gun will keep returning to him/her after every round. Thus, (s)he would ultimately be the lone survive.
The logic, when generalized to N people, results in the formula mentioned above.
No comments:
Post a Comment