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

HMMT February 2005 — Guts Round — Problem 40

[18] In a town of n people, a governing council is elected as follows: each person casts one vote for some person in the town, and anyone that receives at least five votes is elected to council. Let c ( n ) denote the expected number of people elected to council if everyone votes randomly. Find lim c ( n ) /n . n →∞

解析

In a town of n people, a governing council is elected as follows: each person casts one vote for some person in the town, and anyone that receives at least five votes is elected to council. Let c ( n ) denote the average number of people elected to council if everyone votes 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. We k will show that lim c ( n ) /n = 1 / ( e · k !). The probability that any given person n →∞ k receives exactly k votes, which is the same as the average proportion of people that receive exactly k votes, is ( ) ( ) ( ) ( ) k n − k n n 1 n − 1 n − 1 n ( n − 1) · · · ( n − k + 1) · · = · . k k n n n k ! · ( n − 1) ( ) n 1 1 Taking the limit as n → ∞ and noting that lim 1 − = gives that the limit n →∞ n e is 1 / ( e · k !), as desired. Therefore, the limit of the average proportion of the town that receives at least five votes is ( ) 1 1 1 1 1 1 65 1 − + + + + = 1 − . e 0! 1! 2! 3! 4! 24 e