## 100 People in a Circle Puzzle (Interview Puzzle)

###### 2 years ago Lalit Bhagtani 0

100 People in a Circle Puzzle :- There are 100 people standing in a circle. Person standing at 1st position kills next person ( i.e. the person standing at 2nd position ) and gives sword to next to next person ( i.e. the person standing at 3rd position ). Which person survives in the last ?

## Solution of 100 People in a Circle Puzzle :-

You can easily solve this type of puzzle by using two rules :-

1) If total number of people are in power of 2, then person at 1st position will always survive.

Example :- Total number of people are 8 and they are standing in a circle.

People in circle :- 1, 2, 3, 4, 5, 6, 7, 8 (In start, knife is in the hand of 1st person)
After first pass 2, 4, 6, 8 will die and 1, 3, 5, 7 will survive (knife will be in the hand of 1st person)
After second pass 3, 7 will die and 1, 5 will survive (knife will be in the hand of 1st person)
After third pass 5 will die and 1 will be the last one to survive.

2) If total number of people are not in power of 2, then person at nth position of Arithmetic Progression defined below will always survive.

Arithmetic Progression ( X ) = a + d * ( n – 1 )
where, a = 3
d = 2
n = Total number of persons – Greatest nth root of 2 less that total number of persons
For example, if total number of people are 90 then greatest nth root of 2 less that total number of persons will be 64 as it is 6th root of 2 and less than 90, So a will be 65 and n will be 26

Example ( 1 ) :- Total number of people are 10 and they are standing in a circle.

People in circle :- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (In start, knife is in the hand of 1st person)
After first pass 2, 4, 6, 8, 10 will die and 1, 3, 5, 7, 9 will survive (knife will be in the hand of 1st person)
After second pass 3, 7 will die and 1, 5, 9 will survive (knife will be in the hand of 9th person)
After third pass 1, 9 will die and 5 will be the last one to survive.
X = 3  + 2 * ( 10 – 8 – 1) = 5

Example ( 2 ) :- Total number of people are 17 and they are standing in a circle.

People in circle :- 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 (In start, knife is in the hand of 1st person)
After first pass 2, 4, 6, 8, 10, 12, 14, 16 will die and 1, 3, 5, 7, 9, 11, 13, 15, 17 will survive (knife will be in the hand of 17th person)
After second pass 1, 5, 9, 13, 17 will die and 3, 7, 11, 15 will survive (knife will be in the hand of 3rd person)
After third pass 7, 15 will die and 3, 11 will survive (knife will be in the hand of 3rd person)
After fourth pass 11 will die and 3 will be the last one to survive.
X = 3 + 2 * ( 17 – 16 – 1 ) = 3

In our case total number of people are 100, So rule 2 will be apply here as 100 is not a nth root of 2. Let’s apply above AP formula :-

X = 3 + 2 * ( 100 -64 – 1 ) = 73