HMMT 二月 2014 · COMB 赛 · 第 7 题
HMMT February 2014 — COMB Round — Problem 7
题目详情
- Six distinguishable players are participating in a tennis tournament. Each player plays one match of tennis against every other player. There are no ties in this tournament—each tennis match results in a win for one player and a loss for the other. Suppose that whenever A and B are players in the tournament such that A wins strictly more matches than B over the course of the tournament, it is also true that A wins the match against B in the tournament. In how many ways could the tournament have gone?
解析
- Six distinguishable players are participating in a tennis tournament. Each player plays one match of tennis against every other player. There are no ties in this tournament—each tennis match results in a win for one player and a loss for the other. Suppose that whenever A and B are players in the tournament such that A wins strictly more matches than B over the course of the tournament, it is also true that A wins the match against B in the tournament. In how many ways could the tournament have gone? Answer: 2048 We first group the players by wins, so let G be the set of all players with the most 1 wins, G be the set of all players with the second most wins, ..., G be the set of all players with the 2 n least wins. By the condition in the problem, everyone in group G must beat everyone in group G for i j all i < j . Now, consider the mini-tournament consisting of the matches among players inside a single ( ) | G | i group G . Each must have the same number of wins, say x . But the total number of games is i i 2 ( ) | G | i and each game corresponds to exactly one win, so we must have = | G | x = ⇒ | G | = 2 x + 1. i i i i 2 Therefore, the number of players in each G is odd. 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. either i | 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 the players 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 ( ) 4 mini-tournaments, depending on whether p beats p or p beats p . Since there are · 2 = 12 ways 4 5 5 4 2 to pick the two players p defeats and choose which one beats the other, there are indeed 12 · 2 = 24 1 tournaments. Then the total number of possible tournaments in this case is 2 · 6 · 24 = 288. ( ) 6 Case 2: The sizes are 3, 3. In this case, there are = 20 ways to distribute the players into the 3 groups, and 2 possible mini-tournaments in either group, so the total here is 20 · 2 · 2 = 80. ( ) 6 Case 3: The sizes are 3, 1, 1, 1. In this case, there are 4 ways to permute the groups, · 6 = 120 3 ways to distribute the players into groups, and 2 possible mini-tournaments in the group of size 3, for 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.