[math-fun] The top t tennis team.
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?
This assumes deterministic transitivity among the players, which is fine for a math problem, but may not be the best model for a tennis coach. Paul At 10:44 AM -0500 8/27/04, David Gale wrote:
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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is a good point. When I was a schoolboy, there were three of us who used to rotate fairly regularly at the top of the chess ladder. This was because our styles and knowledge (e.g., of openings, endgames, etc.) were such that almost invariably B beat C, C beat A and A beat B. R. On Fri, 27 Aug 2004, Paul R. Pudaite wrote:
This assumes deterministic transitivity among the players, which is fine for a math problem, but may not be the best model for a tennis coach.
Paul
At 10:44 AM -0500 8/27/04, David Gale wrote:
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?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There doesn't seem to be any treatment of the top t problem in the literature. Knuth doesn't even mention it. But he does mention it. See TAOCP Volume III, section 5.3.3, problem 14; and especially the answer. -- Don Reble djr@nk.ca
Thanks, Don, for the highly relevant reference. In fact, my great discovery that it's easier to find the top t players than the t'th highest player turns out not to be as profound as I'd thought. A bright fifth grader could probably see that you only need two matches to select the top 2 players from a set of 3, whereas it may take three matches to find the second best. In fact, (this may be tenth grade level), the latter will happen two thirds of the time assuming the first matching pair is chosen at random. Oh well, David At 03:17 PM 8/27/2004 -0600, you wrote:
There doesn't seem to be any treatment of the top t problem in the literature. Knuth doesn't even mention it. But he does mention it. See TAOCP Volume III, section 5.3.3, problem 14; and especially the answer. -- Don Reble djr@nk.ca
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Even in a case of transitivity and stability (A beats B either 100% of the time, or 0% of the time), a "single elimination" tournament will only find the best, not the second best. "Double elimination" is required to find the second best, and even then, the third best won't necessarily be known. I think that this may have some applicability to the Olympics, where sometimes the bronze (3rd place) medal may not go to the 3rd best. If stability and/or transitivity is thrown out, then things get a lot more complicated, and you have to be much more precise about what you mean by "best", etc. At 09:14 AM 8/30/2004, David Gale wrote:
Thanks, Don, for the highly relevant reference. In fact, my great discovery that it's easier to find the top t players than the t'th highest player turns out not to be as profound as I'd thought. A bright fifth grader could probably see that you only need two matches to select the top 2 players from a set of 3, whereas it may take three matches to find the second best. In fact, (this may be tenth grade level), the latter will happen two thirds of the time assuming the first matching pair is chosen at random. Oh well, David
At 03:17 PM 8/27/2004 -0600, you wrote:
There doesn't seem to be any treatment of the top t problem in the literature. Knuth doesn't even mention it. But he does mention it. See TAOCP Volume III, section 5.3.3, problem 14; and especially the answer. -- Don Reble djr@nk.ca
A modern take on an ancient art of drawing really big pictures: http://www.gpsdrawing.com/gallery.htm
participants (5)
-
David Gale -
Don Reble -
Henry Baker -
Paul R. Pudaite -
Richard Guy