3
$\begingroup$

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:

  1. 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$.
  2. 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 > a_2 > a_3 > a_4 > a_5$.
  3. One race for $a_1, b_1, c_1, d_1, e_1$ and get $a_1 > b_1 > c_1 > d_1 > e_1$. Thus, $a_1$ is the fastest horse.
  4. 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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Do you know what an adversary argument is in general? $\endgroup$
    – Yuval Filmus
    Oct 25, 2013 at 6:58
  • $\begingroup$ @YuvalFilmus Yes, I know the concept of adversary argument and understand the textbook-style examples such as finding max and min, finding the second-largest key and finding the median. To this horse-racing problem, I failed to state the adversary strategy formally. I will try again based on your answer. $\endgroup$
    – hengxin
    Oct 25, 2013 at 7:40

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Following your instructions, I can now formally prove its lower bound using adversary argument. To repeat (for other interested people): 1) at least 5 races; 2) 5 races are not enough to tell which one is the fastest because you can only do step 2) in the algorithm; 3) If you want to know the fastest one, you have to compare all the first ranked horses; 4) When you know the fastest one according to 3), you cannot tell which is the second ranked horse, because both $a_2$ and $b_1$ could be the second one (see the algorithm) and we know nothing about them. $\endgroup$
    – hengxin
    Oct 27, 2013 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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