You might have heard of the famous "Horse Racing" problem.
"There are 25 horses, each one runs at constant speed and each one runs at different speed. You need to find out the minimum races it takes to find out the first, second and third fastest horses from them. Each horse race can only have 5 horses and you don't have a stop watch to time it."
Ans: 7 races
There are standard solutions available for this specific case (25 horses, 3 positions, 5 gates). Now, its your turn to come up with a generic solution which will work for any 'x' number of horses, y' positions needed and 'z' gates. [In the problem above, x = 25, y = 3, z=5]. Solve it to win some exciting goodies. [Excitement is a relative term :P] Applicable only in India.
-- Varun
Answer : 7
ReplyDelete5 races : to get the set of all 1,2,3 positions. (U eliminate 10 horses)
1 Race : Race all the 1st position horses (u get the first horse)
You can eliminate the horses in the 3 and 4th positions from the competition and also the other horses from the set in which those horses were the first.
You can also eliminate the 3rd positions horses from whose initial set corresponding winner is not the first. You can also eliminate the horse that is 2nd in position from the original set to the horse tat finished 3rd in this race.
(You can eliminate 10 horses including the one in the first place)
1 Race : Race the remaining horses for the 2nd and 3rd positions.
Sorry. I dint read the question properly. I was solving the same problem 2 days back and as i saw horse racing words i posted it.
ReplyDelete