HMMT 二月 2013 · COMB 赛 · 第 6 题
HMMT February 2013 — COMB Round — Problem 6
题目详情
- Values a , . . . , a are chosen independently and at random from the set { 1 , . . . , 2013 } . What is 1 2013 expected number of distinct values in the set { a , . . . , a } ? 1 2013 2013
解析
- Values a , . . . , a are chosen independently and at random from the set { 1 , . . . , 2013 } . What is 1 2013 expected number of distinct values in the set { a , . . . , a } ? 1 2013 2013 2013 2013 − 2012 Answer: For each n ∈ { 1 , 2 , . . . , 2013 } , let X = 1 if n appears in { a , a , . . . , a } 2012 n 1 2 2013 2013 and 0 otherwise. Defined this way, E[ X ] is the probability that n appears in { a , a , . . . , a } . Since n 1 2 2013 each a (1 ≤ i ≤ 2013) is not n with probability 2012 / 2013, the probability that n is none of the i ( ) ( ) 2013 2013 2012 2012 a ’s is , so E[ X ], the probability that n is one of the a ’s, is 1 − . The ex- i n i 2013 2013 pected number of distinct values in { a , . . . , a } is the expected number of n ∈ { 1 , 2 , . . . , 2013 } 1 2013 such that X = 1, that is, the expected value of X + X + · · · + X . By linearity of expectation, n 1 2 2013 ( ) ( ) 2013 2013 2013 2012 2013 − 2012 E[ X + X + · · · + X ] = E[ X ] + E[ X ] + · · · + E[ X ] = 2013 1 − = . 2012 1 2 2013 1 2 n 2013 2013 2013