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.