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

HMMT November 2013 — Guts Round — Problem 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT NOVEMBER 2013, 9 NOVEMBER 2013 — GUTS ROUND 1

解析

[ 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 its subsets 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 subsets 2 of { 1 , 2 , 3 } (note that 1 + 2 + 3 = 6 < 10). We just cannot include both 1 , 3, so we have 2(2 − 1) = 6 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 we have 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 } .) The only way to sum to 10 with 1 , 2 , 3 , 4 is by using all the terms, so we simply discount the empty set and 4 { 1 , 2 , 3 , 4 } , for a total of 2 − 2 = 14 subsets. In conclusion , the total number of subsets is 11 + 9 + 14 = 34. 1