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