Show that the number of ways one can choose a set of distinct positive integers, each smaller than or equal to $50$, such that their sum is odd, is $2^{49}$.

My attempt: Suppose set $A=\{1,2,3,...,50\}$. I need to find the number of subsets $S\subset A$ where sum of elements of $S$ is odd. There are a total $2^{50}$ subsets of $A$, including empty subset $\phi$ (with sum of elements $=0$). How can I prove that exactly half of these subsets have sum of their elements odd?

  • 4
    $\begingroup$ Hint: either add or remove the number $1$ to any subset to correct the parity of the sum. $\endgroup$ – lulu May 5 '16 at 15:51
  • $\begingroup$ Great @lulu ! I also came up with another solution myself, turns out its a rather easy problem.. $\endgroup$ – Aditya De Saha May 5 '16 at 16:01
  • $\begingroup$ Your answer looks perfect. You can accept it (and thereby close the question). $\endgroup$ – lulu May 5 '16 at 16:14

Sum of the elements of $A \text{ is }1+2+...+50 = 1275$, an odd number. Thus if I split $A$ into two subsets, one of them will always have odd sum, and the other one even!

[Sorry for answering my own question, I just came up with this after posting the question]


$A=(1,2,・・・,50)=(1,2,1,2,・・・,1,2)$ $mod 2$

First 1 or 0 changes even or odd.Next 2 or 0 doesn't changes.・・・ so problem is even if all are odd numbers$(1,3,5,・・・49),$ their sum is $2^{n-1}$

  • $\begingroup$ Serial voting come. help. $\endgroup$ – Takahiro Waki Jul 29 '18 at 12:06
  • $\begingroup$ This is a well deserved downvote. The answer is completely incomprehensible. $\endgroup$ – Batominovski Jul 29 '18 at 14:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.