HMMT 二月 2005 · 冲刺赛 · 第 40 题

英文解析

40. In a town of n people, a governing council is elected as follows: each person casts onevote for some person in the town, and anyone that receives at least five votes is electedto council. Let c ( n ) denote the average number of people elected to council if everyonevotes randomly. Find lim c ( n ) /n .
    n →∞
    Solution: 1 − 65 / 24 e
    Let c ( n ) denote the expected number of people that will receive exactly k votes. Wekwill show that lim c ( n ) /n = 1 / ( e · k !). The probability that any given personn →∞ kreceives exactly k votes, which is the same as the average proportion of people thatreceive exactly k votes, is
    ( ) ( ) ( ) ( )
    k n − k nn 1 n − 1 n − 1 n ( n − 1) · · · ( n − k + 1)
    · · = · .
    k n n n k ! · ( n − 1)k
    ( )
    1 1 n
    Taking the limit as n → ∞ and noting that lim 1 − = gives that the limitn →∞
    n eis 1 / ( e · k !), as desired. Therefore, the limit of the average proportion of the town thatreceives at least five votes is
    ( )
    1 1 1 1 1 1 65
    1 − + + + + = 1 − .
    e 0! 1! 2! 3! 4! 24 e