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.

Interview Candidate
Mar 1st, 2006
2
2605

Showing Answers 1 - 2 of 2 Answers

G@0

Mar 2nd, 2006

7 times will be enough.
Split 25 horses into 5 groups, and hold one race for each group to determine the ranks within each group. Then hold a race for the winners of each group, and rank them with A, B, C, D and E. Finally, hold a race for 2nd, 3rd in group A and 1st, 2nd in group B and 1st in group C. The 1st and 2nd winner of the last race would be the 2nd and 3rd winner over all horses.

kameshwaran

Mar 3rd, 2006

1) divide 5 groups, each of them 5 horses. without loss of generality, suppose h1 - h5 in group 1, h6 - h10 in group 2, etc. five matches, and suppose the champions from each group are h1,h6,h11,h16 and h21.

2) have another match. suppose the first three are h1, h6 and h11, and h1>h6>h11.

3) h1 is the fastest one. suppose in group 1 h2 and h3 are two immediately after h1, and in group 2 h7 is the one immediately after h6, pick h2, h3, h6, h7, h11.

4) the last match will find out the top 2nd and 3rd fastest horses.

total 5+1+1=7