HMMT 二月 2017 · 冲刺赛 · 第 13 题
HMMT February 2017 — Guts Round — Problem 13
题目详情
英文原题
- [ 9 ] The game of Penta is played with teams of five players each, and there are five roles the players canplay. Each of the five players chooses two of five roles they wish to play. If each player chooses theirroles randomly, what is the probability that each role will have exactly two players?
解析
英文解析
- [ 9 ] The game of Penta is played with teams of five players each, and there are five roles the players canplay. Each of the five players chooses two of five roles they wish to play. If each player chooses theirroles randomly, what is the probability that each role will have exactly two players?
Proposed by: Alexander Katz
Consider a graph with five vertices corresponding to the roles, and draw an edge between two verticesif a player picks both roles. Thus there are exactly 5 edges in the graph, and we want to find the probability that each vertex has degree 2. In particular, we want to find the probability that the graphis composed entirely of cycles.
Thus there are two cases. The first case is when the graph is itself a 5-cycle. There are 4! ways tochoose such a directed cycle (pick an arbitrary vertex A and consider a vertex it connects to, etc.),
4!
and thus = 12 ways for the undirected graph to be a 5-cycle. Now, there are 5! ways to assign theedges in this cycle to people, giving a total contribution of 12 · 5! .2
The second case is when the graph is composed of a 2-cycle and a 3-cycle, which only requires choosing
( )
the two vertices to be the 2-cycle, and so there are = 10 ways. To assign the players to edges, there 5
( )2
are = 10 ways to assign the players to the 2-cycle. For the 3-cycle, any of the 3! = 6 permutations 5
of the remaining 3 players work. The total contribution is 10 · 10 · 6 .2
Therefore, out answer is
12 · 120 + 10 · 10 · 6 51 = .
10 25005