# 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:

Before 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.

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...

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:

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.

Which makes the answer 7 races.

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 | 1^{st} |
A1 | B1 | C1 | D1 | E1 | |

2^{nd} |
A2 | B2 | C2 | D2 | E2 | ||

3^{rd} |
A3 | B3 | C3 | D3 | E3 | ||

4^{th} |
A4 | B4 | C4 | D4 | E4 | ||

5^{th} |
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 | 1^{st} |
A1 | B1 | C1 | D1 | E1 | |

2^{nd} |
A2 | B2 | C2 | D2 | E2 | ||

3^{rd} |
A3 | B3 | C3 | D3 | E3 | ||

4^{th} |
A4 | B4 | C4 | D4 | E4 | ||

5^{th} |
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 | 1^{st} |
A1 | B1 | C1 | D1 | E1 | |

2^{nd} |
A2 | B2 | C2 | D2 | E2 | ||

3^{rd} |
A3 | B3 | C3 | D3 | E3 | ||

4^{th} |
A4 | B4 | C4 | D4 | E4 | ||

5^{th} |
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.

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 inquire using the link at the top of the page. Secure version of this 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