1000 men are standing in a circle. All of them are numbered from 1 to 1000. I give a sword to the first man. He kills the one standing next to him (numbered 2) and hands over the sword to the man numbered 3. He in turn kills the one numbered 4 and hands it over to the one numbered 5 and so on. This killing cycle goes on and on until the last man standing.
1) Who is the last man standing ?
2) Generalize this with a formula to find the last man standing given a finite number of men starting the killing cycles.
Subscribe to:
Post Comments (Atom)
1 comment:
Correct solution submitted by Santosh --
Trick is in realizing that if there were 'n' number of people where 'n' is some power of 2 then the person who will live is with number '1'.
That is if there were 2, 4, 8, 16, 32 or 64 etc... then 1 will live.
So at the stage of the game, when the number of people living is a power of two, then the person with the sword at that time will eventually live.
For example in this particular case, we started with 1000 people
A number which is power of 2 less than 1000 = 512. So when 488 people have died, the person with the sword will live. Knowing when 488 people have died is very easy as in the first cycle only even number of persons die. So 488*2 =976. So after the person 976 dies the remaining number is exactly 512, and person #977 will have the sword at this stage, so 977 eventually is the last mans standing.
General formula = 2*(n-2^k) +1 where n = number of people starting, 2^k is the highest power of 2 lower than n.
Post a Comment