3
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.