How to analyze the lower bound of the horse racing problem using adversary argument? Consider the following problem:


  Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of these horses. Analyze the lower bound of this problem using adversary argument. One race is considered as one critical operation.


I can figure out a solution using 7 races:


  
  Divide 25 horses into 5 groups with 5 horses for each: $A: a_1, a_2, a_3, a_4, a_5$; $B: b_1, b_2, b_3, b_4, b_5$; $C: c_1, c_2, c_3, c_4, c_5$; $D: d_1, d_2, d_3, d_4, d_5$; and $E: e_1, e_2, e_3, e_4, e_5$.
  One race within each group. Suppose that the position of each horse in each group is consistent with its index: e.g., $A: a_1 &gt; a_2 &gt; a_3 &gt; a_4 &gt; a_5$.
  One race for $a_1, b_1, c_1, d_1, e_1$ and get $a_1 &gt; b_1 &gt; c_1 &gt; d_1 &gt; e_1$. Thus, $a_1$ is the fastest horse.
  The second and third ones are among $a_2, a_3, b_1, b_2, c_1$. So one more race is enough.
  


However I have difficulty in analyzing its lower bound using adversary argument.
So my problem is:


  How to analyze its lower bound using adversary argument? What is the adversary strategy?
Intuitively, the reason you need $7$ comparisons is that (1) you need $5$ comparisons just to see all the horses, (2) you need to compare all the first ranked horses to see which one is the fastest, (3) at this point you can't tell which is the second ranked horse.

Of course, this is not quite an adversary argument, and some work will be needed, though it is easy to use an adversary argument to show that (1) is correct: suppose that the strategy involves less than $5$ comparisons; then you don't see all the horses; so you can't tell whether the fastest horse is one of those you've seen or not. (Formally, if the algorithm states that a horse it's seen is the fastest, then you arrange for one of the one it didn't see to be the fastest; and vice versa in the other case.)

The same argument can be extended to show that $5$ comparisons are not enough: the only way that $5$ comparisons could be enough is by executing step 2 of your algorithm, and then you cannot tell which horse is the fastest. (I'll let you formalize that.)

I'll let you complete the argument and show that $6$ comparisons are also not enough.