HMMT 二月 2017 · 冲刺赛 · 第 31 题

HMMT February 2017 — Guts Round — Problem 31

[ 17 ] A baseball league has 6 teams. To decide the schedule for the league, for each pair of teams, a coin is flipped. If it lands head, they will play a game this season, in which one team wins and one team loses. If it lands tails, they don’t play a game this season. Define the imbalance of this schedule to be the minimum number of teams that will end up undefeated, i.e. lose 0 games. Find the expected value of the imbalance in this league.

解析

[ 17 ] A baseball league has 6 teams. To decide the schedule for the league, for each pair of teams, a coin is flipped. If it lands head, they will play a game this season, in which one team wins and one team loses. If it lands tails, they don’t play a game this season. Define the imbalance of this schedule to be the minimum number of teams that will end up undefeated, i.e. lose 0 games. Find the expected value of the imbalance in this league. Proposed by: Yang Liu Let n denote the number of teams. Lemma: Given a connected graph G , the imbalance of G is 1 iff G is a tree. Let’s just talk in terms of directed graphs and indegree/outdegree. Proof. If there is a cycle, direct the cycle such that it is a directed cycle. Then from this cycle, point all remaining edges outwards. If G is a tree, induct on the size. Take any leaf. If it wins its game, it is undefeated. Otherwise, it must lose to its neighbor. Then induct on the tree resulting after deleting the leaf. Now the finish is a simple counting argument using expected values. Using Cayley’s formula, for each subset of vertices, we compute the probability that it is a maximal connected component and is a tree. This ends up being ( ) n ∑ n n − i n − i − 2 ( ) ( ) 2 2 2 · i · 2 . i i =1 5055 This evaluates to for n = 6. 15 2