100 people standing in a circle in an order 1 to 100. Person at No.1 has a sword. He kills next person (i.e. no. 2) and gives sword to next to next (i.e no.3). All person does the same until only 1 survives. Person at which number survives at the last ?
An easy solution:
The formula requires a few simple calculations, and is a function of the number of participants n: find the largest power of two in n, subtract it from n, double the result, and add 1. The person in that spot will be the survivor.
64 is the highest power of 2 in 100. So 100-64=36.We double it add one which gives 73 as the answer.
Those who want to find the idea/logic behind this can further read below:
As readers point out, there’s no need to work through the elimination process — a simple formula will give the answer. This formula, you won’t be surprised to hear, has connections to the powers of two and binary numbers. We will discuss solution, one based on the powers of two.
When the Number of Participants is a Power of Two
Alternating elimination means one of every two participants is eliminated. This is halving, and suggests powers of two are involved.
Let us take an example of n=8
Three passes are required to determine the survivor:
Regardless of the number of participants n, person 1 survives the first pass. Since n is even, as every positive power of two is, person 1 survives the second pass as well. In the first pass, the process goes like this: person 1 is skipped, person 2 is eliminated, person 3 is skipped, person 4 is eliminated, … , person n-1 is skipped, person n is eliminated. The second pass starts by skipping person 1.
As long as the number of participants per pass is even, as it will be for a power of two starting point, the same pattern is followed: person 1 is skipped each time. Therefore, for any power of two, person 1 always survives.
When the Number of Participants is NOT a Power of Two:
When the number of participants is not a power of two, we know this much: person 1 can’t be the survivor. This is because at least one pass will have an odd number of participants. Once the first odd participant pass is complete, person 1 will be eliminated at the start of the next pass.
Four passes are required to determine the survivor:
Powers of two come into play here, but you have to change your perspective to see them. They don’t occur on pass boundaries — they span them. At some point, during pass 1, the number of participants remaining becomes a power of two. In this example, that occurs when 5 of the 13 people are eliminated, leaving an 8 person problem: 11, 12, 13, 1, 3, 5, 7, 9. This means person 11, the first person in the new power of two circle, survives.
We can solve both cases — in other words, for an arbitrary number of participants — using a little math.
Write n as n = 2m + k, where 2m is the largest power of two less than or equal to n. k people need to be eliminated to reduce the problem to a power of two, which means 2k people must be passed over. The next person in the circle, person 2k + 1, will be the survivor. In other words, the survivor w is w = 2k + 1.
Let’s apply these equations to a few examples: