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 andtwo candidates Alice and Celia (who are voters themselves). At the beginning, Alice and Celia bothvote for themselves, and Alice’s boyfriend Bob votes for Alice as well. Then one by one, each of theremaining 2016 voters votes for a candidate randomly, with probabilities proportional to the currentnumber of the respective candidate’s votes. For example, the first undecided voter David has a 2
probability of voting for Alice and a probability of voting for Celia.13
What is the probability that Alice wins the election (by having more votes than Celia)?3
解析
英文解析
- In an election for the Peer Pressure High School student council president, there are 2019 voters andtwo candidates Alice and Celia (who are voters themselves). At the beginning, Alice and Celia bothvote for themselves, and Alice’s boyfriend Bob votes for Alice as well. Then one by one, each of theremaining 2016 voters votes for a candidate randomly, with probabilities proportional to the currentnumber of the respective candidate’s votes. For example, the first undecided voter David has a 2
probability of voting for Alice and a probability of voting for Celia.13
What is the probability that Alice wins the election (by having more votes than Celia)?3
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 inductionnthat for n ≥ 3, the ratio P (2) : P (3) : · · · : P ( n − 1) is equal to 1 : 2 : · · · : ( n − 2). We take an n nbase case of n = 3 , for which the claim is obvious. Then suppose the claim holds for n = k. Then
2 m − 2
P ( m ) = . Thenk
( 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 kk 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 , andk +1 k +1
k ( k − 1) kthus 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