2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Do you need to know the ordering of the three fastest horses, or just the set? $\endgroup$
    – xnor
    Commented Nov 18, 2023 at 8:14
  • $\begingroup$ @xnor If its just the set, could we guarantee to do it 8 or less races (7?) in every case? $\endgroup$
    – quantrader23
    Commented Nov 18, 2023 at 8:24
  • $\begingroup$ I think if we need the ordering, we might probably need 9 races then $\endgroup$
    – quantrader23
    Commented Nov 18, 2023 at 8:25
  • $\begingroup$ Do horses always run at the same speed? Is there any source of variance? $\endgroup$
    – fectin
    Commented Nov 18, 2023 at 20:19
  • $\begingroup$ Isn't that the same question as with 25 horses and 5 tracks or is the difference in numbers significant? $\endgroup$
    – xhienne
    Commented Nov 18, 2023 at 21:50

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ These puzzles assume that times are not allowed or are not comparable between races. $\endgroup$
    – Ross Millikan
    Commented Nov 18, 2023 at 20:23
  • 1
    $\begingroup$ @RossMillikan Sure. That's not stated here though, and if times are not comparable between races, "fastest" requires more careful definition anyway. $\endgroup$
    – fectin
    Commented Nov 18, 2023 at 20:28
  • $\begingroup$ The assumption is that the horses are linearly ranked in speed and in a given race the faster will always beat the slower. We then rely on the transitivity of the order $\endgroup$
    – Ross Millikan
    Commented Nov 19, 2023 at 5:11
  • $\begingroup$ @RossMillikan If we can assume that unstated fact (that placing is immutable), why can't we assume the times are constant as well? $\endgroup$
    – fectin
    Commented Nov 19, 2023 at 21:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.