# $2^{49}$ ways to choose a set of integers $\leq 50$ with odd sum

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?

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