Fastest Three

[modellingman]

25 mechanical contraptions are able to race on a track. However, the track only has capacity for racing 5 contraptions against each other. Each contraption performs consistently in terms of the time taken when racing on the track. What is the minimum number of races required to determine the three fastest contraptions? You do not have a watch/stopwatch available to time contraptions in a race.

modellingman

[9873210]

25 mechanical contraptions are able to race on a track. However, the track only has capacity for racing 5 contraptions against each other. Each contraption performs consistently in terms of the time taken when racing on the track. What is the minimum number of races required to determine the three fastest contraptions? You do not have a watch/stopwatch available to time contraptions in a race.

modellingman

No more than seven.

First run five heats each with five different contraptions. Call the heats A,B,C,D and E and label the contraptions A1, A2, A3, ... B1, B2, ... , by their order in the heats.

Race the winners of the five races against each other. The winner gets gold. WLOG say the top three are A1, B1 and C1. In the consolation race, race A2, A3, B1, B2 and C3. First place gets silver and second place gets bronze.

You need at least five, because you have to race everybody.

Six seems unlikely, the first race eliminates 2 contestants. 20 eliminations across the five remaining races can only be done if the third place from the first heat races the others four at a time and wins. So six races is possible if you get very lucky but you can't count on luck. I am not entirely satisfied with this argument, perhaps it just needs to be phrased better.

[DrFfybes]

7 Races.

5 heats of 5 (A to E)
A1 wins heat A, A2 runner up, B1 wins heat B, etc.

Then a Final of the winner of each heat to find the fastest horse.
For simpliciity assume A1 is fastest, then B1 down to E1.

The Second fastest horse is either B1 or A2 (the runner up in the fastest heat or the runner up in the final)

The third fastest horse is either C1, B2, or A3 - ie the runner up to the previous runners up.

So race these 5 to find second and third.

[Watis]

Although I haven't derived my own solution, I think it's going to need more than six races.

Neither solution offered so far has taken into account the possibility that all the contraptions in group A might be slower than the slowest contraption in group D or E and hence group A yields none of the winners.

We can't time them so only by racing the winners will we begin to establish which groups have the fastest contraptions - and hence which contraptions to include in the next races.

My hunch is that at least 9 races will be required.

Watis

[9873210]

Although I haven't derived my own solution, I think it's going to need more than six races.

Neither solution offered so far has taken into account the possibility that all the contraptions in group A might be slower than the slowest contraption in group D or E and hence group A yields none of the winners.

We can't time them so only by racing the winners will we begin to establish which groups have the fastest contraptions - and hence which contraptions to include in the next races.

My hunch is that at least 9 races will be required.

Watis

Seven is more than six.
Nine is too many.

WLOG means "Without Loss Of (much) Generality". After the final we can rename all the races so the order from that race is A1,B1,C1,D1,E1. If you don't want to rename you can build a tree with 120 branches and come to the same result but with more work. Doing too much work gets you cast out of mathematics and into the outer darkness that is computer science.

That all of one group is slower has been considered. You don't need to know if the winner of a group is slower than the slowest of another group, just that it is slower than at least 3 others.

The five heats eliminate the ten fourth and fifth place entrants (A4,A5,B4,B5,...)
The final eliminates the rest of groups D and E as well as C2,C3 (A1 > B1 > C1 > C2 > C3 so C2 and C3 are out) and B3 (A1 > B1 > B2 > B3).

There remain A1, the fastest, and A2, A3, B1, B2 and C1. These five race in the consolation race determining silver and bronze.

[jfgw]

I worked it out while lying in the bath and came to the same answer given, i.e., seven races.

Spoiler:

Round one: divide into five groups and race each group.

Round two: Race the winners from round one to find the overall winner.

Round three: Find which is second: Race the runner-up from round two against the runner-up from round one from the group which included the winner.

Round four: Find which is third.
Scenario 1: The two fastest are from the same group, so race the third-fastest from this group against the runner-up from round two.
Scenario 2: The two fastest are from different groups, so race whichever came second in each of these groups against whichever came third in round 2.

Rounds three and four can be combined into one race. It will contain:
The runner-up from round two (which may be second or third-fastest);
The runner-up from round one from the group containing the winner (which may be second or third-fastest);
Whichever came third in round one in the group containing the winner (which may be third-fastest);
Whichever came second in round one in the group containing the runner-up in round two (which may be third-fastest);
Whichever came third in round two (which may be third-fastest).


Julian F. G. W.

[modellingman]

Congratulations to 9873210, DrFfybes and jfgw for identifying the correct answer. All have applied the same logic that I originally saw when I first came across this puzzle some time ago. There are a lot of YouTube videos which explain it, some much better than others. Search for "25 horse puzzle Google" as the YouTubers claim it is used in recruitment selection tests for the ad-slinger.

9873210's 6 race scenario is interesting, possible, but requires extreme luck rather than just luck.

We won´t know that the scenario has played out until all 6 races have been run and the third placed contraption in race 1 is placed first in races 2-6. A necessary and sufficient condition for the scenario to play out is that race 1 must contain the fastest 3 selections. However, if race 1 contains a random selection of 5 contraptions, we can determine the probability that it will contain the fastest 3 contraptions - it is 1/230 or approx 0.004348. So extreme luck required.

modellingman

[9873210]

Congratulations to 9873210, DrFfybes and jfgw for identifying the correct answer. All have applied the same logic that I originally saw when I first came across this puzzle some time ago. There are a lot of YouTube videos which explain it, some much better than others. Search for "25 horse puzzle Google" as the YouTubers claim it is used in recruitment selection tests for the ad-slinger.

9873210's 6 race scenario is interesting, possible, but requires extreme luck rather than just luck.

We won´t know that the scenario has played out until all 6 races have been run and the third placed contraption in race 1 is placed first in races 2-6. A necessary and sufficient condition for the scenario to play out is that race 1 must contain the fastest 3 selections. However, if race 1 contains a random selection of 5 contraptions, we can determine the probability that it will contain the fastest 3 contraptions - it is 1/230 or approx 0.004348. So extreme luck required.

modellingman

The other way to think about the six race solution is you already know the answer and want to prove it to somebody else. This is similar to the "oracle" in P v. NP arguments.

Also I still haven't got a simple and totally convincing argument that there can be no six race solution. You really need this to prove the answer is seven.

[jfgw]

Also I still haven't got a simple and totally convincing argument that there can be no six race solution. You really need this to prove the answer is seven.

To find the fastest contraption, you can eliminate no more than four with each race. You could pick five at random and race them to eliminate four, leaving 21 possible winners. Then pick five from those left (which could include the winner of the first race, but need not do) and race those to eliminate another four, leaving 17. You have to do this a total of six times to eliminate 24, leaving the winner.

Now consider only being allowed six races: Once a contraption has been eliminated, it must not race again otherwise it will probably be impossible to eliminate another four contraptions in that race. This means that you cannot race potential runners-up against each other and, therefore, cannot establish which contraption is second (or third) fastest.


Julian F. G. W.

[9873210]

Also I still haven't got a simple and totally convincing argument that there can be no six race solution. You really need this to prove the answer is seven.

To find the fastest contraption, you can eliminate no more than four with each race.

In the seven-race solution the sixth race (all five heat winners) eliminates 9 contenders (E1,E2,E3,D1,D2,D3,C2,C3, and B3). So what exactly do you mean by "you can eliminate no more than four with each race"? The counter example demonstrates that by a simple interpretation it's not true.

It's not that I think there is a six-race solution, but what I think is not a proof. Since the number of combinations is finite so we could in theory do a proof by exhaustion. But 25! is large enough that I don't want to do that so I would wish for a simple argument, or very severe pruning of the cases that need to be considered.

[jfgw]

To find the fastest contraption, you can eliminate no more than four with each race.

In the seven-race solution the sixth race (all five heat winners) eliminates 9 contenders (E1,E2,E3,D1,D2,D3,C2,C3, and B3).

E2, E3, D2, D3, C2, C3, and B3 are not contenders for fastest contraption. Ignore these for now.

The first race eliminates four contraptions from being the overall winner.
The second race eliminates four more contraptions from being the overall winner.
Etc.

You can only eliminate four in a race of five as there cannot be more than four which do not come first. With six races, you can eliminate no more than 24. You need to eliminate 24.

In order to guarantee that four contraptions will be eliminated in any particular race, you must not enter a contraption that has already been eliminated. A contraption that has already been eliminated cannot be eliminated again so you will probably only eliminate three in that race. If you do this, you will not be able to determine the overall winner in just six races.

If you are limited to six races, you cannot compare runners-up as these have already been eliminated from being the overall winner. You would need a seventh race for that.

You may be able to determine the first, second and third fastest with six races but it will usually fail. It would involve entering a contraption that came third in one race into another race and hoping that it comes first. If it doesn't, you will not be able to determine the overall winner in six races.


Julian F. G. W.

[DrFfybes]

Also I still haven't got a simple and totally convincing argument that there can be no six race solution. You really need this to prove the answer is seven.

Each race eliminates a maximum of 4 runners. You need to eliminate 22. So yes, 6 races eliminates 24. But you only want to eliminate 22, so a 7th race is required to identify 2nd and third.

Unless you can eliminate 3.66667 horses per heat.

[9873210]

To find the fastest contraption, you can eliminate no more than four with each race.

In the seven-race solution the sixth race (all five heat winners) eliminates 9 contenders (E1,E2,E3,D1,D2,D3,C2,C3, and B3).

E2, E3, D2, D3, C2, C3, and B3 are not contenders for fastest contraption. Ignore these for now.

The first race eliminates four contraptions from being the overall winner.
The second race eliminates four more contraptions from being the overall winner.
Etc.

You can only eliminate four in a race of five as there cannot be more than four which do not come first. With six races, you can eliminate no more than 24. You need to eliminate 24.

In order to guarantee that four contraptions will be eliminated in any particular race, you must not enter a contraption that has already been eliminated. A contraption that has already been eliminated cannot be eliminated again so you will probably only eliminate three in that race. If you do this, you will not be able to determine the overall winner in just six races.

If you are limited to six races, you cannot compare runners-up as these have already been eliminated from being the overall winner. You would need a seventh race for that.

Julian F. G. W.

Thank you, that seems a rigorous enough proof.

FWIW the bolded bit was what I was missing. It's a matter of taste but I'd substitute "may" for "probably" and construct a single alternative case where it does not work, but it's clear enough how to do that.

[jfgw]

Each race eliminates a maximum of 4 runners. You need to eliminate 22. So yes, 6 races eliminates 24. But you only want to eliminate 22, so a 7th race is required to identify 2nd and third.

To find the overall winner, you need to eliminate 24. Eliminating the slowest 22 is more complicated and takes seven races.

Using the method initially proposed, the first five races will eliminate two contraptions each. After the sixth race, it is possible to eliminate nine more. This does not break the "one race cannot eliminate more than four" rule as information from four of the races is needed to eliminate this nine.
Of the remaining six, we know the fastest so racing the other five will eliminate the other three non-winners.


Julian F. G. W.