HMMT 二月 2003 · COMB 赛 · 第 8 题

英文解析

8. For any subset S ⊆ { 1 , 2 , . . . , 15 } , a number n is called an “anchor” for S if n andn + | S | are both members of S , where | S | denotes the number of members of S . Findthe average number of anchors over all possible subsets S ⊆ { 1 , 2 , . . . , 15 } .
   Solution: 13 / 8
   We first find the sum of the numbers of anchors of all subsets S ; this is equivalent tofinding, for each n , the number of sets for which n is an anchor, and then summingover all n . Suppose that n is an anchor for S , and S has k elements. Then n, n + k ∈
   S ⇒ k ≥ 2, and also n + k ≤ 15, or k ≤ 15 − n . The remaining k − 2 elements of
   S (other than n and n + k ) may be freely chosen from the remaining 13 members of
   ( )
   { 1 , 2 , . . . , 15 } , so we get possible sets S . Summing over all allowed values of k ,13
   k − 2
   ( ) ( ) ( ) ( )
   13 13 13 13
   we then have + + + · · · + sets with n as an anchor. If we sum
   0 1 2 13 − nover all n = 1 , 2 , . . . , 13 (since there are no possible values of k when n > 13), we geta total of
   ( ) ( ) ( ) ( )
   13 13 13 13
   13 + 12 + 11 + · · · + .
   0 1 2 12
   If we call this quantity A , then, by symmetry, 2 A equals
   ( ) ( ) ( ) ( )
   13 13 13 13
   13 + 12 + 11 + · · · +
   0 1 2 12
   ( ) ( ) ( ) ( )
   13 13 13 13 + + 2 + · · · + 12 + 13
   1 2 12 13
   [( ) ( ) ( ) ( ) ( )]
   13 13 13 13 13 = 13 + + + · · · + + = 13 · 2 .13
   0 1 2 12 13
   So A = 13 · 2 is the total number of anchors over all possible sets S . Finally, to find 12
   the average number of anchors, we divide by the number of sets, which is 2 ; thus,15
   12 15
   the answer is 13 · 2 / 2 = 13 / 8.