Expert: Bernard Hawkes - 7/19/2007

Question
There are 25 Horses which all run at different speeds. A faster horse always beats a slower horse. You can race 5 horses at a time. There are no ties and you may not  ----- time ----- them. What is the minimum number of races needed to detemine the 3 fastest horses in order from fastest to slowest

Answer
Hi Prabhu

Well, it was a more 'interesting' problem than I originally thought. It can in fact be done in just 7 races. Let me attempt to explain how. Start by dividing the horses into 5 groups of 5 and racing each group. Now take the winner of each of the 5 preliminary heats and race them. Label the horses that come 1st, 2nd and 3rd (in the 6th race) A, B and C. Let A be the winner of heat X, B be the winner of heat Y and C be the winner of heat Z.

Firstly, A is overall the fastest horse. B is possibly the 2nd fastest and C the possibly th 3rd fastest. In heat X the horse that came 2nd can possibly be the 2nd fastest and the horse that came 3rd can possibly be the 3rd fastest. In heat Y the horse that came 2nd can possibly be the 3rd fastest. All other horses are eliminated.

That leaves just 5 horses in contention for 2nd and 3rd fastest overall. One more race decides these positions.

Best wishes,
Bernard.
-----------------------------
Hi Prabhu

Interesting question. In any random selection of 5 horses it is possible that all of the 3 fastest horses are contained in the group. However, you can always safely eliminate the 2 horses that come 4th and 5th.

So, select 5 horses at random, race them, eliminate the last two. Repeat 10 times (eliminate 20 horses) and you're left with 5 horses. One final race and you have your answer.

Is this the least number of races? Not sure. Will ponder further and get back to you if I come to any definite conclusions.

Best wishes,
Bernard.