HMMT 二月 2013 · COMB 赛 · 第 6 题
HMMT February 2013 — COMB Round — Problem 6
题目详情
英文原题
Values a1, . . . , a 2013 are chosen independently and at random from the set {1, . . . , 2013}. What is
expected number of distinct values in the set {a1, . . . , a 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 } . Sincen 1 2 2013
each a (1 ≤ i ≤ 2013) is not n with probability 2012 / 2013, the probability that n is none of thei
( ) ( )
2013 2013
2012 2012
a ’s is , so E[ X ], the probability that n is one of the a ’s, is 1 − . The exi 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