PUMaC 2015 · 组合（A 组） · 第 8 题
PUMaC 2015 — Combinatorics (Division A) — Problem 8
题目详情
- [ 8 ] In a tournament with 2015 teams, each team plays every other team exactly once and no ties occur. Such a tournament is imbalanced if for every group of 6 teams, there exists either a team that wins against the other 5 or a team that loses to the other 5. If the teams are indistinguishable, what is the number of distinct imbalanced tournaments that can occur? 1
解析
- [ 8 ] In a tournament with 2015 teams, each team plays every other team exactly once and no ties occur. Such a tournament is imbalanced if for every group of 6 teams, there exists either a team that wins against the other 5 or a team that loses to the other 5. If the teams are indistinguishable, what is the number of distinct imbalanced tournaments that can occur? Solution: We claim that within any subset S of T with | S | ≥ 6, there must exist a winner or a loser (i.e. someone who wins against or loses to everyone else in that subset). We show this by induction, and by assumption, it is already true for the base case | S | = 6, so assume | S | > 6. Assume the contrary, that in S , every team wins and loses at least 1 game. Let the set of teams that win exactly 1 game be A and that lose exactly 1 game be B . Now, each team v must either win against at least one team that loses exactly 1 game or lose to at least one team that wins exactly 1 game. Otherwise, take S − v , and by the inductive hypothesis, there must exist a winner or a loser. Since the winner or loser of S − v does not lose or win, respectively, to v , that team must still be a winner or loser, respectively, of S . Then, counting | A | and | B | , we have: | A | + | B | ≥ | S | > 6 This means that either | A | ≥ 4 or | B | ≥ 4. If A ≥ 4, then there must be some team a ∈ A that wins against at least 2 teams in A , which contradicts the definition of teams in A , so A ≥ 4 is impossible. Similarly, B ≥ 4 is impossible. Thus, a contradiction is reached, so there must exist a team in S that is either a winner or a loser, which completes the inductive step. We now count the number of distinct imbalanced tournaments. Given any imbalanced tourna- ment T , we proceed to repeatedly select either a winner or a loser until we run out of options. We end up with an ordering of all 2015 teams with the exception of a leftover group G of at most 5 teams. For instance, we could have: a > a > . . . > a > ( a , a , a , a , a ) > a > . . . > a 1 2 420 421 422 423 424 425 426 2015 If | G | = 0, then the only possible tournament is a > a > . . . > a , so there is 1 distinct 1 2 2015 tournament. Note that | G | 6 = 1 , 2, as we can always select one team from that group that wins against every other team from that group. For the sake of convenience, let L be the set of teams that lose to G . If | G | = 3, the only distinct G = { a , a , a } is WLOG a → a ; a → a ; a → a . Furthermore, | L | ∈ { 0 , 1 . . . , 2012 } and i j k i j j k k i any two tournaments with | L | = | L | are indistinguishable. Thus, there are 2013 distinct 1 2 imbalanced tournaments with | G | = 3. If | G | = 4, the only distinct G = { a , a , a , a } is WLOG a → a , a ; a → a , a ; a → i j k l i j k j k l k a ; a → a and | L | ∈ { 0 , 1 , . . . , 2011 } . Similarly, there are 2012 distinct imbalanced tourna- l l j ments with | G | = 4. If | G | = 5, there are 9 distinct graphs G . If each of the teams wins exactly 2 games (within G ), then there are 2 distinct G . If three win exactly 2 games, one wins 3, and one wins 1, then there are 3. Finally, if one wins exactly 2 games, two win 3, and two win 1, then there are 4. The distinct graphs G are shown below, but we will omit the procedure for determining them for the sake of clarity. Since | L | ∈ { 0 , 1 , . . . , 2010 } , there are 2011 · (2 + 3 + 4) = 18099 distinct imbalanced tournaments with | G | = 5. 5 In total, then, there are 1 + 2013 + 2012 + 18099 = 22125 distinct imbalanced tournaments. Author: Bill Huang 6