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 can play. Each of the five players chooses two of five roles they wish to play. If each player chooses their roles 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 can play. Each of the five players chooses two of five roles they wish to play. If each player chooses their roles 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 vertices if 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 graph is 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 to choose 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 the 2 edges in this cycle to people, giving a total contribution of 12 · 5! . The second case is when the graph is composed of a 2-cycle and a 3-cycle, which only requires choosing ( ) 5 the two vertices to be the 2-cycle, and so there are = 10 ways. To assign the players to edges, there 2 ( ) 5 are = 10 ways to assign the players to the 2-cycle. For the 3-cycle, any of the 3! = 6 permutations 2 of the remaining 3 players work. The total contribution is 10 · 10 · 6 . Therefore, out answer is 12 · 120 + 10 · 10 · 6 51 = . 5 10 2500