@rkshtsurana said:how v ll proceed if instead of alternate..every 3rd contestant is asked to step up...there was a method that we convert in base 3 and then ve do right shift..can u explain ?
I think you are talking about this problem:-
The 150 contestants of Miss India 2010 are given individual numbers from 1 to 150. Several rounds happen before the final winner is selected. The elimination in each round follows an interesting pattern. In the 1st round starting from first contestant, every 3rd contestant is eliminated i.e. 1st, 4th, 7th, .... This repeats again from the first numbered (among the remaining) contestant in the next round (leaving 3, 5, 8, 9, ... ). This process is carried out repeatedly until there is only the winner left. What is the number of Miss India 2010?
The logic that you mentioned goes like this:-
Convert 150 in base 3
150 in base 3 is 12120
Now remove first two digits and append them to the end of the remainder number.
So, new number becomes 12012
It is 140 is base 10
So, contestant number 140 will be the winner.
(I don't know the reason why it works)
But somehow I'm not sure if its the correct way to go about it.
For example has the number been 159, then in base 3 its 12220
After removing first digits and appending them at the end it will become 22012 which is 221 in base 10 (which doesn't make any sense)
So, I'm not sure about this method.
Alternatively:-
Backtracking will also help.
If any contestants position in a round is n, then in the previous round its position will be 3n/2 or [3n/2] + 1
So, positions of winner are 1, 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, 140, 210, ...
Means for any n (no of contestants) between 62 and 92 winner will be contestant no 62 and so on
Since here we have 150 contestants winner will be 140
But here the contestants are not standing around the circle (for that you can read about Josephus problem)