0
$\begingroup$

I've recently found an extended version of a rather well-known question.

The question goes as follows:

'There are 37 racehorses. You can race them together 6 at a time, and observe their relative performance. You do not have a timer. How many races do you need to determine the three fastest horses?'

Here is the link to the solution of the standard version of the puzzle.

https://puzzling.stackexchange.com/questions/51754/25-horses-find-the-3-fastest-ones

Going by the above solution, it seems to me that the answer to the 37 horses version is 8. Is that correct?

$\endgroup$
4
  • $\begingroup$ 37 is not 6^2, it's 1 greater than 6^2. $\endgroup$
    – mathlander
    Commented Nov 12, 2023 at 21:39
  • $\begingroup$ @mathlander Although it is one greater, but the construction for 8 races is the similar. The crucial problem is: Whether this construction is the best construction, I'm not sure how to prove it. $\endgroup$
    – JetfiRex
    Commented Nov 12, 2023 at 22:04
  • $\begingroup$ Many problems with this question: per SE guidelines, do not include links to relevant info. please make your post self-contained so that all relevant info is contained therein. also, if by "relative performance" you mean the ranking (1st place, 2nd place, etc) of each horse at the end of a race, then you should say exactly that. Also, the question does not account for random variability in the speed of each horse from race to race. A horse is not necessarily slower than one or more oppoenents because it fails to place $1$st in a single race. $\endgroup$ Commented Nov 13, 2023 at 1:01
  • $\begingroup$ (continued from above) a better and more accurate question is to ask for the minimum number of races needed to identify the $3$ fastest horses with a given level of confidence. $\endgroup$ Commented Nov 13, 2023 at 1:05

1 Answer 1

0
$\begingroup$

Let us assume the problem in question amounts to this:

There are 37 horses, each of which always runs at the same speed and any two of which run
 at different speeds. You can race up to 6 horses at a time, and each race will rank all
 the horses running in it in terms of which runs faster than which but will provide no
 further information.

What is the smallest number of races needed to determine which 3 horses are the 3 fastest
 of the 37?

One way to find the fastest 3 is to start by racing 36 of them 6 at a time (6 races), then run the fastest horse from each of those 6 races in a 7th race, and use the information obtained so far to choose 6 horses for an 8th and final race as follows:

Let the 1st 6 races be known as A through F according to the rank in the 7th race of each
 one's winner. For example, C will be the race won by the 3rd fastest horse in the 7th
 race. Also number the horses in each race according to relative speed. For example B2
 will be the 2nd fastest horse in race B, and C4 will be the 4th fastest horse in race C.

Horses C2 through C6 and all the horses in races D through F can be eliminated as
 candidates for the fastest 3 of the 37 since they have all been proven slower than A1,
 B1, and C1. B3 through B6 (proven slower than A1, B1, and B2), and A4 through A6
 (proven slower than A1, A2, and A3) can also be eliminated.

The one horse as yet without a name we can call X. Choose X, A2, A3, B1, B2, and C1 for
 the 8th race. Except for X, these others have already been proven faster than the 30
 eliminated horses, so the fastest 2 horses in the 8th race, being faster than at least
 4 + 30 other horses, must be among the fastest 3 of the 37. We already know A1 is faster
 than the other 35 horses in the 1st six races, so it will be among the fastest 3 of
 the 37 also.

Call any sequence of races sufficient to determine the 3 fastest horses of the 37 a solution, call 2 or more sets of horses disconnected if no horse in one ever runs in a race with a horse from another, and call any set of horses connected if it does not comprise 2 or more disconnected sets.

In any solution, the set of all 37 horses must be connected because, if the 37 horses are in 2 or more disconnected sets, there is no way to know which 3 are the fastest, even if the relative speeds of all the horses in each such set can be proven.

Call any horse in a given race a repeat if it has run in a previous race. Partitioning the horses in any solution into 2 disconnected sets would require eliminating at least 1 repeat, and increasing the number of disconnected sets further would require eliminating more repeats, at least 1 for each set to be disconnected.

In other words, there has to be a difference of at least n − 1 repeats between n disconnected sets and a solution.

Since only 6 horses can run at a time, it takes at least 7 races to include all 37 horses, and since 7 races with no repeats implies 7 disconnected sets, any solution will require at least 6 repeats.

37 horses + at least 6 repeats = at least 43 slots, which amounts to at least 8 races.

Since we have a solution in 8 races, and any solution requires at least 8 races, the answer to the problem is 8.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .