HMMT 二月 2014 · 冲刺赛 · 第 23 题
HMMT February 2014 — Guts Round — Problem 23
题目详情
- [ 14 ] Let S = { 100 , 99 , 98 , . . . , 99 , 100 } . Choose a 50-element subset T of S at random. Find the expected number of elements of the set {| x | : x 2 T } .
解析
- [ 14 ] Let S = {− 100 , − 99 , − 98 , . . . , 99 , 100 } . Choose a 50-element subset T of S at random. Find the expected 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 201 elements, and partition S into sets A , A , . . . , A such that | A | = 1 and | A | = | A | = · · · = | A | = 2. 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 k chosen m -element subset of S . What is the expected number of A ’s that have a representative in T ? k For k = 0 , 1 , . . . , n , let w = 1 if T ∩ A 6 = ∅ and 0 otherwise, so that the number of A ’s that have k k k ∑ n a representative in T is equal to w . It follows that the expected number of A ’s that have a k k k =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 -element 1 m ( ) 2 n +1 subsets of S that exclude both elements of A , and there are m -element subsets of S in total, 1 m we have that ( ) 2 n − 1 (2 n − m )(2 n − m + 1) m ( ) E[ w ] = 1 − = 1 − . 1 2 n +1 2 n (2 n + 1) m Putting this together, we find that the expected number of A ’s that have a representative in T is k m (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