返回题库

HMMT 二月 2019 · COMB 赛 · 第 7 题

HMMT February 2019 — COMB Round — Problem 7

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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
解析

英文解析

  1. 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