27 Aug
2004
27 Aug
'04
9:44 a.m.
Given n candidates trying out for a tennis team of t players. Find the minimum number of matches needed to pick out the top t. I don't expect anyone to solve this. The related problem of picking the t'th best player remains unsolved for n >7. (see Knuth, vol. 3)What I noticed is, 1). The top t problem is strictly "easier" than the t'th best problem. Example. You can find the top 2 out of 5 in only 5 matches, (try it), whereas finding the second best requires 6 matches. 2).There doesn't seem to be any treatment of the top t problem in the literature. Knuth doesn't even mention it. References, anyone?