HMMT 二月 2014 · 冲刺赛 · 第 23 题

英文解析

23. [ 14 ] Let S = {− 100 , − 99 , − 98 , . . . , 99 , 100 } . Choose a 50-element subset T of S at random. Find theexpected number of elements of the set {| x | : x ∈ T } .
    8825
    Answer: Let us solve a more generalized version of the problem: Let S be a set with 2 n + 1
    elements, and partition S into sets A , A , . . . , A such that | A | = 1 and | A | = | A | = · · · = | A | = 2.201
    0 1 n 0 1 2 n
    (In this problem, we have A = { 0 } and A = { k, − k } for k = 1 , 2 , . . . , 100.) Let T be a randomly
    0 kchosen m -element subset of S . What is the expected number of A ’s that have a representative in T ?
    For k = 0 , 1 , . . . , n , let w = 1 if T ∩ A 6 = ∅ and 0 otherwise, so that the number of A ’s that havekk k k
    ∑
    a representative in T is equal to w . It follows that the expected number of A ’s that have ank kk =0
    representative in T is equal to
    E[ w + w + · · · + w ] = E[ w ] + E[ w ] + · · · + E[ w ] = E[ w ] + n E[ w ] ,
    0 1 n 0 1 n 0 1
    since E[ w ] = E[ w ] = · · · = E[ w ] by symmetry.
    1 2 n
    Now E[ w ] is equal to the probability that T ∩ A 6 = ∅ , that is, the probability that the single element
    0 0
    of A is in T , which is T | / | S | = m/ (2 n + 1). Similarly, E[ w ] is the probability that T ∩ A 6 = ∅ , that is,
    0 1 1
    ( )
    2 n − 1
    the probability that at least one of the two elements of A is in T . Since there are m -elementm 1
    ( )
    2 n +1
    subsets of S that exclude both elements of A , and there are m -element subsets of S in total,
    m 1
    we have that
    ( )
    2 n − 1
    (2 n − m )(2 n − m + 1)
    ( )m
    E[ w ] = 1 − = 1 − .
    2 n +11
    2 n (2 n + 1)
    Putting this together, we find that the expected number of A ’s that have a representative in T ismkm (2 n − m + 1)(2 n − m ) + n − .
    2 n + 1 2(2 n + 1)
    In this particular problem, we have n = 100 and m = 50, so substituting these values gives our answer
    8825
    of .
    201