14
$\begingroup$

The horse-racing puzzle has been asked on mathSE several times (1, 2, 3, 4); there is also a generalization. I restate the puzzle below:

25 horses all run at different speeds. You can race 5 horses at a time to rank them in order of speed, but you do not actually learn their numerical speeds by racing them. How many races are required to determine the third-fastest horse?

The correct strategy for doing it in 7 races has been described in detail here and elsewhere on the internet. But why isn't 6 races enough?

The only attempt at showing 6 races is not enough (in this answer) is pretty hand-wavy:

Now let's prove that $7$ races is optimal.

Using the same idea, we can draw a directed graphs to represent these races and relations. The circles or nodes are horses, and the directed paths represent one horse being faster than another. Here would be what one race would look like, with the fastest horse on the left:

$$ \circ\rightarrow\circ\rightarrow\circ\rightarrow\circ\rightarrow\circ $$

So basically, what we want to end up with to find the three fastest horses is a parent node and a total of at most $5$ children with a depth of $2$ from this parent, with all of the other nodes being under $5$ children. We need a race to compare these $5$ children, and the other races to set up the graph. Each race will place $4$ horses, as the fastest horse needs to be a horse that has already raced in order to be compared. The only exception is the first race, which can place $5$. $\lceil 24/4 \rceil = 6$, and we add that to our check race to show that the best possible solution is $7$ races, and it can in fact be attained.

I really don't follow this reasoning, and I don't think it provides rigorous justification.

Note as well, that 6 races IS enough if you get lucky. So a correct argument will have to appeal to some sort of worst-case-scenario.

Does anyone have a rigorous version of this argument, or a different rigorous argument, to show 6 races is not enough? I'd like to have a solution that is as elegant as possible.

$\endgroup$
6
  • $\begingroup$ I don't think 7 races is correct for the top three horses. This answer (and others I've found) don't seem to give convincing justification for that answer. They only seem correct up to the top two horses. I haven't thought it through carefully enough to be confident about that, though. $\endgroup$ – Nate C-K Jul 14 '15 at 19:05
  • 1
    $\begingroup$ The obvious solution I can see that should be correct (not necessarily optimal) is: 1) Race all 5 horses in groups of 5. 2) Run three more races, one with the #1 finisher from each race, one with the #2 finishers, one with the #3 finishers. 3) Run a final race with the top 3 #1 finishers, the top 2 #2 finishers and the top 1 #3 finisher. The top three placed in this last race are your fastest. That's 9 races in all to determine the three fastest horses. $\endgroup$ – Nate C-K Jul 14 '15 at 19:16
  • $\begingroup$ Oops, that solution I gave had 6 horses in the last race, so that's not correct either. $\endgroup$ – Nate C-K Jul 14 '15 at 19:31
  • 1
    $\begingroup$ It's best not to worry for the reasons behind downvotes unless it's obvious. $\endgroup$ – Nate C-K Aug 18 '15 at 22:30
  • 1
    $\begingroup$ My guess is that posting a bounty gets you more views, and more views means more likelihood of a downvote. $\endgroup$ – Nate C-K Aug 22 '15 at 13:18
7
+100
$\begingroup$

Assume that you have an algorithm to find the first three places in 6 races. Assume that after the fifth race $n$ horses have raced. If $n=25$, then the last race can detemine only the winner, but not the second nor the third place: it has to race one horse from each previous race, so if the first three places were all in the same heat or 1,2 in the same and 3 in a different, it couldn't tell the difference.

So $n<25$, and in the last race you have to race the new horses against the first three places A1, A2, A3 (possibly without knowing the order) of the $n$ horses that already have raced, otherwise you cannot determine the overall three fastest horses with the last race.

Hence $n=23$ or $n=24$.

If you assume $n=23$, then it is impossible to determine the three fastest horses out of 23 with 5 races:

You cannot have less than three different winners, since only two repetitions are allowed.

If you have three different winners that have not been compared, then any of the 5 second places could be A2 or A3.

If you have four or more different winners that have not been compared, all of them could be A1,A2, or A3.

If $n=24$, then you have to know a set of four horses out of the first 24 which contains A1,A2 and A3. But this is impossible in 5 races, since you have at least 4 different winners that have not been compared, and so these four horses and the second places could be all A1,A2 or A3.

Hence all cases lead to a contradiction, and so the assumption that 6 is enough, is untenable.

$\endgroup$
2
  • $\begingroup$ The same argument shows that you cannot determine the two fastest horses with 6 races $\endgroup$ – san Aug 12 '15 at 13:13
  • 2
    $\begingroup$ Perhaps the downvoter could explain the downvote? This seems like a great answer to me. $\endgroup$ – joriki Aug 13 '15 at 15:50
-1
$\begingroup$

Solution: the answer is 9 races.

Step 1: First, we group the horses into groups of 5 and race each group in the race course. This gives us 5 races.

W11 W12 W13 W14 W15

W21 W22 W23 W24 W25

W31 W32 W33 W34 W35

W41 W42 W43 W44 W45

W51 W52 W53 W54 W55

Step 2:we race the 5 level 1 winners(w11,w21,w31,w41,w51) and assume winning order of this race is w11,w21,w31,w41,w51 (THIS IS 6TH RACE)

Step 3: BECAUSE WE NEED TOP 5 AND W51 HAS COME 5TH Position that is the reason we don't need to consider W52 W53 W54 W55 now we have

W11 W12 W13 W14 W15

W21 W22 W23 W24 W25

W31 W32 W33 W34 W35

W41 W42 W43 W44 W45

W51

Step 4: because we need top 5 then dont need W25 W34 W35 W43 W44 W45

now we have

W11 W12 W13 W14 W15

W21 W22 W23 W24

W31 W32 W33

W41 W42

W51

Step 5: top 1 is already achieved which is W11(winner of 6th race) remaining are X W12 W13 W14 W15

W21 W22 W23 W24

W31 W32 W33

W41 W42

W51

Step 6: candidates for 5th position: W51 W42 W33 W24 W15. 1 RACE TO GET 5TH POSITION (this is 7th race)

remaining are

X W12 W13 W14

W21 W22 W23

W31 W32

W41

Step 7: candidates for 4th position: W41 W32 W23 W14. 1 race to get 4th position ((this is 8th race)

X W12 W13

W21 W22

W31

Step 8: Candidates for 2nd and 3rd position: W12 W13 W21 W22 W31. 1 race to get 2nd and 3rd position ((this is 9th race)

Hence answer is 9 races.

$\endgroup$
1
  • $\begingroup$ This seems to be a solution to a different problem. In this question, the answer is 7 races, not 9; I am also asking about how to prove 6 is not enough, NOT how to do it in 7. $\endgroup$ – 6005 Jul 19 '17 at 19:28
-2
$\begingroup$

$A_1$ $A_2$ $A_3$ $A_4$ $A_5$
$B_1$ $B_2$ $B_3$ $B_4$ $B_5$
$C_1$ $C_2$ $C_3$ $C_4$ $C_5$
$D_1$ $D_2$ $D_3$ $D_4$ $D_5$
$E_1$ $E_2$ $E_3$ $E_4$ $E_5$

We race $A,B,C,D,E$ groups.-$5$ races.
Now you say that we have to determine the $3$rd fastest horse. So if we take a look at the situation here, $A_1$ runs faster than everyone. So we have got the first one. Now we have to compare $A_2$ and $A_3$ with $B_1$ and $B_2$ and $C_1$.
I know you would think that why am I writing all this, this is the classic solution. But the rigorous solution is also this: In the starting, we had to compare $35$ horses. And after what seemed convenient, (the $5$ races), $10$ horses were left to compare.
These types of questions only demand a creative solution, there cannot be a rigorous proof for these types of question. Its like asking a unique solution for $x+y+z=10$. (Just an example).
Because even in the $7$ race method, we first assume the order of finishing positions of horses. So there are many, many solutions, but there cannot be a solution lesser than this.
Edit: In these types of questions, we only take the worst case scenario, not that the person may get lucky. If this was true, the answer would obviously be $0$. And I assumed that you know all this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.