Minimum Races for Top 3 horses

Question

There are 37 horses and 6 horses can race each time on a track. Find the fewest number of races required to get the top 3 fastest horses.

Source - Glassdoor

I know we can definitely do it in 9 races but was wondering if we could do it in 8 races too. 7 definitely doesn't seem possible

We can divide the 37 horses into 6 groups of 6 with 1 horse remaining on the side. We then have 6 races to race these 6 horses. Now we have a 7th race to race the fastest horse from each group.

Now we can race the 2nd and 3rd fastest horse from the group with the fastest horse, the 1st and 2nd fastest horse from the group with the 2nd fastest horse in the previous race and the fastest horse from the group with the 3rd fastest horse in the previous race and the odd 37th horse which was ungrouped. This would be 6 horses so 1 additional race for a total of 8 races.

Now we can have the case where the 37th horse is the fastest horse - faster than the fastest horse we identified earlier then we need 1 more additional race in this case.

Is my approach is correct? Is there some trick with which we can do it 8 races instead since in the last race we only have 2 horses and are not using all 6 lanes which may not be the optimal way/solution.

Answer 1

I think

8

races suffice to get the group of the top 3 but we won't necessarily know the order among them.

Start out as you said with making 6 groups of 6 horses and race each group. Then race the the 6 winners of the groups against each other. Label the 6 groups A, B, .. , F and without loss of generality assume the winners of the group winner race are A then B then C. Denote by A1 the winner of group A, A2 the second of group A and so on, and let 37 denote the horse that hasn't raced yet. Now lets take stock of what we know.

A1 is faster than any horse except possibly 37. So it is among the top 3 no matter what. No horse in groups D, E or F can be in the top 3. The remaining candidates for the top 3 are 37, A2, A3, B1, B2, C1. So we will just race these 6 against each other.

This will give us the group of the top 3

The top 3 consists of A1 and the top 2 from the last race. If 37 happens to win race 8 we don't know whether it is faster or slower than A1 but we know both of them are in the top 3.

Answer 2

Seven races is sufficient: Time each horse and compare their times.