HMMT 十一月 2013 · 冲刺赛 · 第 24 题

英文解析

24. [ 12 ] Find the number of subsets S of { 1 , 2 , . . . 6 } satisfying the following conditions:
    • S is non-empty.
    • No subset of S has the property that the sum of its elements is 10.
    Answer: 34 We do casework based on the largest element of S . Call a set n -free if none of itssubsets have elements summing to n .
    Case 1: The largest element of S is 6 . Then 4 ∈ / S . If 5 ∈ / S , then we wish to find all 4-free subsetsof { 1 , 2 , 3 } (note that 1 + 2 + 3 = 6 < 10). We just cannot include both 1 , 3, so we have 2(2 − 1) = 62
    choices here.
    If 5 ∈ S , then we want 4 , 5-free subsets of { 1 , 2 , 3 } . The only 4-but-not-5-free subset is { 2 , 3 } , so wehave 6 − 1 choices here, for a case total of 6 + 5 = 11.
    Case 2: The largest element of S is 5 . We seek 5 , 10-free subsets of { 1 , 2 , 3 , 4 } . We just cannot
    2 2
    have both 1 , 4 or both 2 , 3 (note that getting 10 requires the whole set), so we have (2 − 1) = 9
    subsets in this case.
    Case 3: The largest element of S is at most 4 . (So we want a 4-free subset of { 1 , 2 , 3 , 4 } .) Theonly way to sum to 10 with 1 , 2 , 3 , 4 is by using all the terms, so we simply discount the empty set and
    { 1 , 2 , 3 , 4 } , for a total of 2 − 2 = 14 subsets.4
    In conclusion , the total number of subsets is 11 + 9 + 14 = 34. 1