HMMT 二月 2019 · COMB 赛 · 第 7 题
HMMT February 2019 — COMB Round — Problem 7
题目详情
- In an election for the Peer Pressure High School student council president, there are 2019 voters and two candidates Alice and Celia (who are voters themselves). At the beginning, Alice and Celia both vote for themselves, and Alice’s boyfriend Bob votes for Alice as well. Then one by one, each of the remaining 2016 voters votes for a candidate randomly, with probabilities proportional to the current 2 number of the respective candidate’s votes. For example, the first undecided voter David has a 3 1 probability of voting for Alice and a probability of voting for Celia. 3 What is the probability that Alice wins the election (by having more votes than Celia)?
解析
- In an election for the Peer Pressure High School student council president, there are 2019 voters and two candidates Alice and Celia (who are voters themselves). At the beginning, Alice and Celia both vote for themselves, and Alice’s boyfriend Bob votes for Alice as well. Then one by one, each of the remaining 2016 voters votes for a candidate randomly, with probabilities proportional to the current 2 number of the respective candidate’s votes. For example, the first undecided voter David has a 3 1 probability of voting for Alice and a probability of voting for Celia. 3 What is the probability that Alice wins the election (by having more votes than Celia)? Proposed by: Yuan Yao 1513 Answer: 2017 Let P ( m ) be the probability that after n voters have voted, Alice gets m votes. We show by induction n that for n ≥ 3, the ratio P (2) : P (3) : · · · : P ( n − 1) is equal to 1 : 2 : · · · : ( n − 2). We take a n n n base case of n = 3 , for which the claim is obvious. Then suppose the claim holds for n = k. Then 2 m − 2 P ( m ) = . Then k ( k − 1)( k − 2) k − i i − 1 ( k − i )(2 i − 2) + ( i − 1)(2 i − 4) 2 i − 2 P ( i ) = P ( i ) + P ( i − 1) = = . k +1 k k k k k ( k − 1)( k − 2) k ( k − 1) 2 2 Also, we can check P (2) = and P ( k ) = , so indeed the claim holds for n = k + 1 , and k +1 k +1 k ( k − 1) k thus by induction our claim holds for all n ≥ 3 . The probability that Ceila wins the election is then 1009 ∑ P ( m ) 2019 1008 · (1 + 1008) / 2 504 m =2 = = , 2018 ∑ 2017 · (1 + 2017) / 2 2017 P ( m ) 2019 m =2 1513 and thus the probability that Alice wins is . 2017