Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2015 October 12

From Wikipedia, the free encyclopedia
Mathematics desk
< October 11 << Sep | October | Nov >> October 13 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


October 12

[edit]

Worst possible champion record in a multiple round-robin tournament

[edit]

(Trying to figure out how good a chance some teams I'm following can win their tournaments...) Consider a multiple round-robin tournament with n players/teams and r rounds, so that each player/team plays each other player/team exactly r times, for a total of r(n - 1) matches per player/team. Assuming no tied games/matches are possible, at the conclusion of the tournament, what is the least possible number of wins sufficient to be an untied champion? —SeekingAnswers (reply) 21:25, 12 October 2015 (UTC)[reply]

Not 100% clear on what you mean. For a round robin tournament with 5 teams there are 10 games and you can have win records of 3-2-2-2-1 in which the first team wins the tournament with 3 wins. But 3 wins does not guarantee winning the tournament since you can also have 3-4-2-1-0. So are you asking what is the the smallest number of wins you can have while winning the tournament or what is the number of wins needed to guarantee winning the the tournament? In the first case, if r(n-1) is even then it's fairly easy to come up with an n-way tie of r(n-1)/2 wins each, and by reversing one game you could have a tournament winner with r(n-1)/2+1 wins. If all teams have less than that then it must an n-way tie so the answer is r(n-1)/2+1. If r(n-1) is odd and every team has at most (r(n-1)+1)/2 wins then you must have an n/2-way tie and again it's easy to come up with a way that this is possible. So you can win the tournament with (r(n-1)+3)/2 but not less assuming n>2. If n=2 then the tournament is just a best of r series and the answer is obvious. The second interpretation of the question seems a bit more tricky. If there is only one round then it's pretty clear a team would need to win all n-1 games to guarantee a win, otherwise another team could win all of its games and still win the tournament. --RDBury (talk) 22:22, 12 October 2015 (UTC)[reply]
Thanks. I was originally asking about the first/former interpretation, but now that you've mentioned it, I've given some thought to the second/latter interpretation, along lines suggested by your explanation above, and here follows what I think is the answer to the second/latter interpretation. Call our potential champion Team A, and label a potential rival as Team B. In the worst case for Team A, Team B wins all games against the other teams besides Team A. This means Team A must also win all games against all opponents other than Team B, so that means Team A must win at least (r - 1)(n - 1) games. Added to that, to be an untied champion, Team A must win over half of its games against Team B, which is n / 2 games if n is even and (n + 1) / 2 games if n is odd. So I think the answer to the second/latter interpretation is (r - 1)(n - 1) + n / 2 if n is even and (r - 1)(n - 1) + (n + 1) / 2 if n is odd. —SeekingAnswers (reply) 00:06, 14 October 2015 (UTC)[reply]