Determine the number of subsets of $\{1,2,3,4,…,50\}$ whose sum of elements is larger than or equal to $638$.

Determine the number of subsets of $\{1,2,3,4,…,50\}$ whose sum of elements is larger than or equal to $638$.

Let $U=\{1,2,3,4,…,50\}$. I know the sum of all of the elements in $U$ is $25 \cdot 51=1275$ and $U$ has $2^{50}$ subsets. We can group all of these subsets into pairs, each pair is paired with its compliment, therefore we have $\frac{2^{50}}{2}$ pairs. The sum of the elements of both subsets in each group is $1275$, therefore each group will contain one subset whose sum of all elements is larger than or equal to $638$ because $1275/2=637.5$. So I think the number of subsets of $\{1,2,3,4,…,50\}$ whose sum of elements is larger than or equal to $638$ is $\frac{2^{50}}{2}$ subsets.

The answer key says the answer is $2^{49}$, I do not understand why?

• $2^{50}/2=2^{49}$ – kingW3 Dec 17 '16 at 18:21
• Your answer is correct – Kanwaljit Singh Dec 17 '16 at 18:22
• @kingW3, thanks, sometimes I don't realize the simplest things – idknuttin Dec 17 '16 at 18:23