Question

How many subsets of {1, 2, 3, 4, 6, 8, 10, 15} are there for which the sum of the elements is 15?

Answer 1

Answer:

512

Step-by-step explanation:

Suppose we ask how many subsets of {1,2,3,4,5} add up to a number ≥8. The crucial idea is that we partition the set into two parts; these two parts are called complements of each other. Obviously, the sum of the two parts must add up to 15. Exactly one of those parts is therefore ≥8. There must be at least one such part, because of the pigeonhole principle (specifically, two 7's are sufficient only to add up to 14). And if one part has sum ≥8, the other part—its complement—must have sum ≤15−8=7

.

For instance, if I divide the set into parts {1,2,4}

and {3,5}, the first part adds up to 7, and its complement adds up to 8

.

Once one makes that observation, the rest of the proof is straightforward. There are 25=32

different subsets of this set (including itself and the empty set). For each one, either its sum, or its complement's sum (but not both), must be ≥8. Since exactly half of the subsets have sum ≥8, the number of such subsets is 32/2, or 16.