The Man Surviving in Game Of Death
What was the problem?
First let's make it very simple by who are surviving after each round.
Round 1 : 1,3,5,7,9,11,13,15..........87,89,91,93,97,99
Round 2 : 1,5,9,13,17.........89,93,97
Round 3 : 1,9,17,25,33,41,49,57,65,73,81,89,97
Round 4 : 9,25,41,57,73,89
Round 5 : 9,41,73
Round 6 : 9, 73
At round 5, 9 kills 41 & passes sword to 73. So 73 kills 9 & survives.
Round 7 : 73
Now let's analyze how this happens & trick to get answer at the quickest.
Just for a moment let's assume there were 16 standing in circle.
Now after each round survived people are,
Round 1 : 1,3,5,7,9,11,13,15
Round 2 : 1,5,9,13
Round 3 : 1,9
Round 4 : 1
After round 2, when 9 kills 13 & passes sword to 1.
And in round 4, 1 kills 9. So 1 forms pair with other in every round.
Now imagine there were 17 people in circle.
Round 1 : 1,3,5,7,9,11,13,15,17
Round 2 : 1,5,9,13,17
Round 3 : 1,9,17
Round 4 : 1,17
Round 5 : 17
At the end of round 3, 1 kills 9 & passes sword to 17. Now 17 doesn't have any other in pair so kills 1 & survives.
So what does this indicate? When number of people are in power of 2 then 1st person always survives. Reason is he always pairs with someone next.
Now in given problem 100 people are standing & nearest power less than 100 is 64. So to make circle of 64 out of 100, 36 must be killed. And when 36th one is killed, a new circle of 64 can be imagined. That means when 71 kills 72 in first round,72 is 36th (72/2) one who is killed. So we are left with circle of 64 starting at 73.
Hence 73 would be survived at the end.
There is another way. 128 is the nearest power of 2 greater than 100. Imagine 128 people standing in circle. In the case, 1 would have been easily survived. But in given problem there are 100 people. So the survivor must have moved back from No.1 to No.100 & No.100 to No.73 i.e. total 28 positions (128 - 100) in opposite direction.
Now if some other problem asks you to find survivor among 200 people standing in circle , what would you answer? 145th right?
