Find the number of subsets of satisfying the following conditions: - is non-empty. - No subset of has the property that the sum of its elements is 10.
Solution
We do casework based on the largest element of . Call a set -free if none of its subsets have elements summing to . Case 1: The largest element of is 6. Then . If , then we wish to find all 4-free subsets of (note that ). We just cannot include both 1,3, so we have choices here. If , then we want 4,5-free subsets of . The only 4-but-not-5-free subset is , so we have choices here, for a case total of . Case 2: The largest element of is 5. We seek 5,10-free subsets of . We just cannot have both 1,4 or both 2,3 (note that getting 10 requires the whole set), so we have subsets in this case. Case 3: The largest element of is at most 4. (So we want a 4-free subset of .) The only way to sum to 10 with is by using all the terms, so we simply discount the empty set and , for a total of subsets. In conclusion, the total number of subsets is .