Subset 2: Sum

How many subsets of the set $\{1,2,3,\ldots,30\}$ have the property that the sum of the elements is greater than 232?

Answer

The sum of all numbers from 1 to 30 is

1 + 2 + \cdots + 30 \;=\; \frac{30 \times 31}{2} \;=\; 465.

Notice that $$465$$ is odd, so the “halfway” point is $$232.5$$ . Every subset $S\subseteq\{1,\dots,30\}$ has a complement $$S^c$$ whose sum is $465 - \sum(S)$ . This creates a one‐to‐one pairing between subsets with sums above $$232.5$$ and those below $$232.5$$ . Because no subset can sum to $$232.5$$ exactly (since sums are integers), exactly half of the subsets have sum $\le 232$ and the other half have sum $\ge 233$ .

Hence, the number of subsets with sum $$>232$$ (i.e. sum $\ge233$ ) is precisely half of all $2^{30}$ subsets:

\boxed{2^{29}}.

Notes and comments

Comment 1: If the question were “How many subsets have sum $$> 233$$ ?”, we would look at subsets with sum $\ge 234$ . By the same complement argument, these are in one‐to‐one correspondence with subsets whose sum is $\le 231$ . But in this case the subsets that sum to 232 and 233 would have to be excluded, resulting in a count slightly different from $\tfrac12\,2^{30}$ .