Puzzle time - Rating the Horses

[jon-nyc]

You have 25 horses and can race them in groups of five, but having no stopwatch, you can only observe the order of finish.  How many heats of five horses to you need to determine the fastest three of your 25?

[Klaus]

Just to have a quick baseline, which I'm certain isn't optimal:

The naive strategy would be the "keep the best three so far" strategy, which in this case would require 11 races.

Another suboptimal strategy would presumably be "reject 2/5th of the candidates in each round", i.e. 5 races for the first round (leaving 15), 3 for the second (leaving 9), 2 for the third (leaving 5, with a little trick), and then a final round. Which also adds up to 11.

[Horace]

Testing all 25 in 5 groups to start seems reasonable. From there you can test the five heat winners, which will give you the fastest. You can disregard the groups led by the two slowest. That leaves six horses which might be the next two fastest, which are the two fastest horses from each of the three remaining groups. You don't have to race the second fastest from the group led by the third fastest in the semi-final though, because you know it's at best fourth fastest. So there are only five left. Total 7 races.

[jon-nyc]

That's what I got

[Klaus]

But can you prove that there is no better method?

[Horace]

You have to race all of them at least once, so 5 races is a minimum. That leaves 15 horses that might be in the top three - the three fastest from each race. Is it possible to do one race that finds the top three, from those 15?

[jon-nyc]

You can determine it in 6 races if you’re really lucky.

[Horace]

@jon-nyc said in Puzzle time - Rating the Horses:

You can determine it in 6 races if you’re really lucky.

Number three from one heat against the winners of the other four heats, hope he wins?

[jon-nyc]

almost.

Number 3 from first heat, run him against the other 20 in groups of 4

[Horace]

@jon-nyc said in Puzzle time - Rating the Horses:

almost.

Number 3 from first heat, run him against the other 20 in groups of 4

I think mine works too.

[jon-nyc]

It does