### XAT 2011 Question 82

Instructions

based on the following information.

From a group of 545 contenders, a party has to select a leader. Even after holding a series of meetings, the politicians and the general body failed to reach a consensus. It was then proposed that all 545 contenders be given a number from 1 to 545. Then they will be asked to stand on a podium in a circular arrangement, and counting would start from the contender numbered 1. The counting would be done in a clockwise fashion. The rule is that every alternate contender would be asked to step down as the counting continued, with the circle getting smaller and smaller, till only one person remains standing. Therefore the first person to be eliminated would be the contender numbered 2.

Question 82

# One of the contending politicians, Mr. Chanaya, was quite proficient in calculations and could correctly figure out the exact position. He was the last person remaining in the circle. Sensing foul play the politicians decided to repeat the game. However, this time, instead of removing every alternate person, they agreed on removing every 300th person from the circle. All other rules were kept intact. Mr. Chanaya did some quick calculations and found that for a group of 542 people the right position to become a leader would be 437. What is the right position for thewhole group of 545 as per the modified rule?

Solution

For f(2n), the one at 2f(n)-1 will win.

And for f(2n+1) members, the one at 2f(n)+1 will win.

When 2n = 2, the winner will be 1.

For 2n = 4, winner will be 2f(2) - 1. And since f(2)=1, for f(4), the winner will be 1.

Now, f(545) = 2f(242) + 1

f(272) = 2f(136) - 1

f(136) = 2f(68) - 1

f(68) = 2f(34) - 1

f(34) = 2f(17) - 1

f(17) = 2f(8) + 1

f(8) = 2f(4) - 1

f(4) = 2f(2) - 1

Since f(2) = 1, f(4) = 1,f(8) = 1, f(17)= 3,f(34)= 5, f(68) = 9, f(136) = 17, f(272) = 33, f(545) = 67

Now, f(544) = 65, f(543) = 63....

So when every second member is removed, for f(n) = A, f(n - m) = A - 2m.

When every x member is removed and f(n) = A, f(n - m) = A - x*m.

If A > f(n), then f(n) = A % f(n)...(i)

Now, f(542) = 437, and x = 300

f(543) = 437 + 300 = 637 % 543 = 194

f(544) = 196 + 300 = 494

f(545) = 496 + 300 = 794 % 545 = 249

Thus, the correct option is C.