Solve 25 Horse Riddle: Find 3 Fastest in Minimal Races

[daniel_i_l]

Consider the following riddle:
You have 25 horses and want to know which are the 3 fastest. Whenever
you race horses, the order of finish accurately reflects the relative
speeds of the horses but you can only race 5 at a time. What's the
minimum number of races required to determine the 3 fastest.
Now, one way to solve the problem is to play around with different methods until you find one that seems minimalistic. But that way you can't prove that your answer is right. In an effort for a way to prove (or disprove) that the answer i got (7 by the way) was right I had the following idea: Let's call the information that one horse is faster than the other one bit of information. Then, in order to find the 3 fastest you need not only a certain amount of information, but also the right density (by that I mean that you need a lot of information about only 3 horses). Now maybe there's some way to find out the maximum amount of information and density that can be gotten by a given number of races.
Does anyone have any ideas about this? Are there existing theories that I can use?
Thanks.

 

[CRGreathouse]

Well, you certainly need at least six races. If you had less than five races then not all horses would race, and you couldn't tell the horses that didn't race apart. If you had five races all horses must race (else an unraced horse could be fastest or slowest and you couldn't tell which) so the races cannot overlap; but then you can't tell which horses are fastest across races.

I think a similar, more complicated argument could also rule out six.

 

[topherfox]

This depends on two factors:

1. If comparing is basically seeing the final results then (Bob came first, Jill came second:

I am thinking more along the lines of 11, since you need to see the comparisons to three of the horses with the rest of the pack, so the first run, 25, then the same 3 horses, with a different 2, 2*10 = 20, for the rest of the horses, so the first race plus the 10 other races, 11.

2. If you compare times, then you only need 6 (mathematical statistics can be compared to one linked denomination):

The first 5, then the same one horse after that, 4*5 = 20, so a total of 6 races.

EDIT:

I didn't read the last part, that was my idea on the problem.

 

[CRGreathouse]

Surely if you know the times of the race you can find the answer in five races -- each horse needs only run once.

OK, here's a thought on proving that six races aren't enough (with rankings only). On the first race only two horses can be eliminated, since the top three in the race might be the top three overall. So the remaining races would need to eliminate at least four horses each. This is possible only if the top horse from a past race participates and comes in 4th or 5th, eliminating one new horse and all the horses from the past race. But the old horse might come in better than 4th. Needs work, but is this doable?

 

[Ynaught?]

I do not think it is possible with fewer than 7 races:

Label the races 1, 2, 3, 4, 5, 6, and 7.

Label the horses in each race A, B, C, D, and E.

Each of the first five races includes five different horses. Thus, each horse races once in the first five races. For argument sake, let’s say that horses 1A, 2A, 3A, 4A, and 5A were the winners of each of the first five races (25 bits of info as identifiers for each horse and 5 bits for each of the race winners)

In race 6 we pit the five winners together. For arguments sake, let’s say they ranked in order 1A, 2A, 3A, 4A, and 5A (another 5 bits of info –- race 6 = 1 bit, the top three positions as 1 bit each and one bit for the overall winner). Horse 1A is declared the champion; she is the fastest of the fastest!

Since we are only concerned with the three fastest horses, all of the horses from race 4 and race 5 are eliminated because the winners of races 4 and 5 did not place in the top three of race 6.

Since 3A was the winner of race 3 and came in third in race 6, the other four horses in race 3 are eliminated. That leaves eight other possible candidates (from the losers from races 1 and 2) for race 7.

Since horse 2B can place no better than third (since she already lost to 2A, who lost to 1A) by beating 3A in a showdown, 2B wins the last post in race 7. The remaining four horses from race 3 are eliminated.

Since horse 1C can place no better than third (since she already lost to 1A and 1B), by beating 2B or 3A in a showdown, 1C wins the fourth post in race 7.

Finally, since horse 1B can place no better than second (since she already lost to 1A) by beating 2A, 2B and 3A in a showdown, 2B wins the third post in race 7.

(If you have not already surmised that 2A and 3A won the first and second posts in race 7, respectively, I did a really bad job of explaining…<L>)

So in race 7 you have horses 2A, 3A, 1B, 1C and 2B (another 6 bits of data, with two more bits to identify first and second runner up).

That’s 43 bits of data, if I counted correctly.

 

[daniel_i_l]

Thanks for the input. But I wasn't really asking how to solve this riddle. I wanted to know if there was some way of determining the minimum number of races needed without having to go into the details of how to do it. For example, I don't want to assume that first you race all the horses in groups of 5 (as almost everybody did). I want to know if there's some theoretical way of getting a minimum using ideas about information only.
Thanks.