A problem by Pratik Vora
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 300th 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 300.)
It is known that, for a group of 542 people the right position to become a leader would be 437. What is the right position for the whole group of 545 as per the modified rule?
The answer is 249.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Consider a group of person in which every Kth person counting from the first person is eliminated.
The person left in the process is the leader and let his position be f(n, k).
Please note the following in this regard.
f(n, k) = (f(n–1,k) +k) mod n
It is given that f(542, 300) = 437
f(543, 300) = (f(542, 300) + 300) mod 543
= (437+300) mod 543 = 194
f(544,3000 = (f(543,300) + 300) mod 544
= (194+300)mod 544 = 494
f(545, 300) = (f(544, 300) + 300) mod 545
= (494+300) mod 545 = 249
In this case, the leader is the person in the 249th position.