HMMT 二月 2014 · COMB 赛 · 第 7 题

英文解析

7. Six distinguishable players are participating in a tennis tournament. Each player plays one match oftennis against every other player. There are no ties in this tournament—each tennis match resultsin a win for one player and a loss for the other. Suppose that whenever A and B are players in thetournament such that A wins strictly more matches than B over the course of the tournament, it is alsotrue that A wins the match against B in the tournament. In how many ways could the tournamenthave gone?
   Answer: 2048 We first group the players by wins, so let G be the set of all players with the mostwins, G be the set of all players with the second most wins, ..., G be the set of all players with the 1
   2 nleast wins. By the condition in the problem, everyone in group G must beat everyone in group G fori jall i < j . Now, consider the mini-tournament consisting of the matches among players inside a single
   ( )
   | G |
   group G . Each must have the same number of wins, say x . But the total number of games isii i
   ( )2
   | G |
   and each game corresponds to exactly one win, so we must have = | G | x = ⇒ | G | = 2 x + 1.ii i i i
   Therefore, the number of players in each G is odd.2
   ∑i
   We now have | G | = 6 and all | G | are odd, so we can now do casework on the possibilities.
   i i
   Case 1: G ’s have sizes 5 and 1. In this case, there are 2 ways to permute the groups (i.e. eitheri
   | G | = 5 , | G | = 1 or | G | = 1 , | G | = 5). There are 6 ways to distribute the players into the two
   1 2 1 2
   groups. There are 24 possible mini-tournaments in the group of size 5; to prove this, we label theplayers p , . . . , p and note that each player has 2 wins. Without loss of generality, let p beat p
   1 5 1 2
   and p , and also without loss of generality let p beat p . It’s easy to verify that there are 2 possible
   3 2 3
   ( )
   mini-tournaments, depending on whether p beats p or p beats p . Since there are · 2 = 12 ways 4
   4 5 5 4
   to pick the two players p defeats and choose which one beats the other, there are indeed 12 · 2 = 242
   tournaments. Then the total number of possible tournaments in this case is 2 · 6 · 24 = 288.1
   ( )
   Case 2: The sizes are 3, 3. In this case, there are = 20 ways to distribute the players into the 6
   groups, and 2 possible mini-tournaments in either group, so the total here is 20 · 2 · 2 = 80.3
   ( )
   Case 3: The sizes are 3, 1, 1, 1. In this case, there are 4 ways to permute the groups, · 6 = 1206
   ways to distribute the players into groups, and 2 possible mini-tournaments in the group of size 3, for 3
   a total of 4 · 120 · 2 = 960.
   Case 4: The sizes are 1, 1, 1, 1, 1, 1. There are 720 ways to distribute the players into groups.
   The final answer is 288 + 80 + 960 + 720 = 2048.