HMMT 二月 2003 · COMB 赛 · 第 8 题

HMMT February 2003 — COMB Round — Problem 8

For any subset S ⊆ { 1 , 2 , . . . , 15 } , a number n is called an “anchor” for S if n and n + | S | are both members of S , where | S | denotes the number of members of S . Find the average number of anchors over all possible subsets S ⊆ { 1 , 2 , . . . , 15 } .

解析

For any subset S ⊆ { 1 , 2 , . . . , 15 } , a number n is called an “anchor” for S if n and n + | S | are both members of S , where | S | denotes the number of members of S . Find the 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 to finding, for each n , the number of sets for which n is an anchor, and then summing over 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 ( ) 13 { 1 , 2 , . . . , 15 } , so we get possible sets S . Summing over all allowed values of k , k − 2 ( ) ( ) ( ) ( ) 13 13 13 13 we then have + + + · · · + sets with n as an anchor. If we sum 0 1 2 13 − n over all n = 1 , 2 , . . . , 13 (since there are no possible values of k when n > 13), we get a 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 + + + · · · + + = 13 · 2 . 0 1 2 12 13 12 So A = 13 · 2 is the total number of anchors over all possible sets S . Finally, to find 15 the average number of anchors, we divide by the number of sets, which is 2 ; thus, 12 15 the answer is 13 · 2 / 2 = 13 / 8.