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, acoin is flipped. If it lands head, they will play a game this season, in which one team wins and oneteam loses. If it lands tails, they don’t play a game this season. Define the imbalance of this scheduleto be the minimum number of teams that will end up undefeated, i.e. lose 0 games. Find the expectedvalue 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, acoin is flipped. If it lands head, they will play a game this season, in which one team wins and oneteam loses. If it lands tails, they don’t play a game this season. Define the imbalance of this scheduleto be the minimum number of teams that will end up undefeated, i.e. lose 0 games. Find the expectedvalue 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 ofdirected graphs and indegree/outdegree.
Proof. If there is a cycle, direct the cycle such that it is a directed cycle. Then from this cycle, pointall remaining edges outwards. If G is a tree, induct on the size. Take any leaf. If it wins its game, itis undefeated. Otherwise, it must lose to its neighbor. Then induct on the tree resulting after deletingthe leaf.
Now the finish is a simple counting argument using expected values. Using Cayley’s formula, for eachsubset of vertices, we compute the probability that it is a maximal connected component and is a tree.
This ends up being
( )
∑nn n − i −ni − 2
( ) ( )
2 2
2 · i · 2 .
i =1 i
5055
This evaluates to for n = 6.
215