Answer to Puzzle #59: 25 Horses, Find the Fastest 3

59. You have 25 horses, you want to pick the fastest 3 horses out of those 25. In each race, only 5 horses can run at the same time. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?

There's one sort of little trap that you might fall in to but other than that it's not so hard. We have to do it all by comparison:

fastest horse and jockeyBefore reading the answer can I interest you in a clue?

I think a key thing to remember is if you know an elephant is bigger than an apple, and that a cat is bigger than an orange comparing an elephant to a cat tells you nothing about how an apple compares to an orange. That may seem an obvious if confusing example at this stage but we'll come back to it.

First off we are going to race them in 5 groups of 5. At this stage we will relabel them by the following scheme, that is all those that are in the first heat will be labelled A followed by a number representing where they came in their heat. So B3 came third in the second race, for example.

Race
    A B C D E
Position 1st A1 B1 C1 D1 E1
2nd A2 B2 C2 D2 E2
3rd A3 B3 C3 D3 E3
4th A4 B4 C4 D4 E4
5th A5 B5 C5 D5 E5

So far we have had 5 races. All the horses in red can be eliminated. Any horse that finished below third in it's group race can not be third or higher overall. But we don't know much else, there many possible combinations that could be the fastest three. It could be, in order C1, C2 & C3. A1, B1 & C1 B1, C1 & B2. B1, B2 & C1. But it can't be, in order A1, B1 & C2.

The rule is if a horse is in the top 3 then any horse that came higher in it's group must also be in the top 3 and higher than it. So for C2 to get in to the top 3 then C1 must also be in the top 3 and higher. For C3 to be in the top 3 then both C2 and C1 must also be in the top 3 and higher. Which would mean the top 3 would in fact have to be C1, C2 & C3 in that order.

Time for another race, lets race the top finishing horse from each group, A1, B1, C1, D1 & E1...

We shall assume for convenience that they finish in that order A1, B1, C1, D1 & E1. A1 is now clearly the fastest horse overall. But what else...

Race
    A B C D E
Position 1st A1 B1 C1 D1 E1
2nd A2 B2 C2 D2 E2
3rd A3 B3 C3 D3 E3
4th A4 B4 C4 D4 E4
5th A5 B5 C5 D5 E5


We're at 6 races.
• If D1 and and E1 are not in the top 3 then by our rules, D2, D3... E2, E3... can't be in either. Which follows.
• As we said before, but only by example in order that C3 be in the top 3 the top 3 would have to be C1, C2 & C3 in that order. It's not so C3 can go.
• Much the same can be said of C2. Since C1 is at best 3rd, (assuming the top 3 were A1, B1 & C1,) C2 can't possibly be in the top 3.
• B3 can be eliminated for the same reason as C3, That the Top 3 can't be B1, B2 & B3 as A1 is fastest.

So now our table looks like this:

Race
    A B C D E
Position 1st A1 B1 C1 D1 E1
2nd A2 B2 C2 D2 E2
3rd A3 B3 C3 D3 E3
4th A4 B4 C4 D4 E4
5th A5 B5 C5 D5 E5


For our seventh and final race we must test B1, C1, A2, B2 & A3. The fastest of these will be second overall and the second of these will be third over all. Who finishes 3rd, 4th etc in this race does not tell you anything about who is 4th, 5th over all. Maybe you could think about why?

I'm not sure how clear the diagram below is. The idea is that it shows you the possible combinations. Such as A1, A2 & B1 is possible but A1, A2 & B2 is not.
fastest horse possible combinations

Which makes the answer 7 races.

Assumptions

That the races are fair. That the results are consistent and do not vary from race to race. No lane has an advantage That sort of thing.





© Nigel Coldwell 2004 -  – The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please enquire using the link at the top of the page.
 


PayPal
I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel




This Website Uses Cookies

Mostly, but not entirely to remember if you have dismissed this very box. Also to increase the functionality of the site. The cookies I apply do not uniquely identify you, by continuing to use this site you agree to let me place a cookie. I also have advert and analytics providers, for more information click here here.x