Yrurtj

Let $S$ be a set of twelve integers ${1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}$. How many subsets of $S$ are there such that the sum of all the elements in the subset is an odd number?

Here's what I tried. There are $2^{12}=4096$ ways to create a subset from $S$. I tried to find the number of what I call "even" subsets, or subsets whose elements only summed to even numbers. I divided $S$ into two subsets, one for all even numbers, and one for all odd numbers, knowing that all the subsets of those two subsets must have an even sum. Counting the sum and subtracting from $4096$, I get $2^{12}-2^6-2^6=3968$. However, now I realize that there are more ways to create "even" subsets, for example, two odds, four evens. I am now stuck. Can someone help?

Split $S$ into the set of even numbers of $S$ and the set of odd numbers of $S$, what I'll call $E = {2,4,6,8,10,12}$ and $O = {1,3,5,7,9,11}$

Form your arbitrary subset of $S$ where the sum of elements is odd by selecting any subset of $E$ and unioning that with with any subset of an odd number of elements from $O$.

Apply the rule of product and conclude.

There are $2^6$ possible subsets of $E$ and there are $binom{6}{1}+binom{6}{3}+binom{6}{5} = 2^5$ subsets with an odd number of elements of $O$

Alternate explanation. First choose any subset of ${2,3,4,dots,12}$. If the sum is currently even, then include also $1$ with it. If the sum is currently odd, then don't include $1$. Convince yourself that you cover all cases exactly once each.

Hint:

If we sum up an odd number of odd integers, and however many even ones we wish with them, then the sum is always odd.

This can be justified by considering arithmetic and congruences modulo $2$ if you want to formally see this, but I feel like it's relatively self-evident just by trying a few examples.

Thus, you need to find the number of subsets of $S$ which contain an odd number of odd integers in them.

The credit for this strategy goes entirely to JMoravitz.

What I didn't realize earlier is that as long as there are an odd number of odd numbers in our subset, then we can get an odd numbers, no matter how many even numbers are in the subset. I will make the even and odd subsets separately to be $E={2, 4, 6, 8, 10, 12}$ and $O={1, 3, 5, 7, 9, 11}$. There are ${6choose1} + {6choose3} + {6choose5}=2^{5}=32$ ways to pick odd numbers. We can now pick as many evens as we wish, so we have $2^6$ ways to pick a subset. The union of the subset will just be the product of the two values, so we have $2^5 times 2^6=2^{11}=boxed{2048}$ subsets.

Thank you all so much for the help!

The number of such subsets is half the number of all subsets of $S$, i.e. $frac{1}{2}cdot2^{12}=2^{11}$.

Let $P_e(S)$ (respectively, $P_o(S)$) be the sets of subsets of $S$, where the sum of the elements is even (respectively, odd). Consider a map $f:P_e(S)to P_o(S)$ defined as follows: for a subset $Asubseteq S$ such that $Ain P_e(S)$, let
$$
f(A)=
begin{cases}
Asetminus{1}, &text{ if } 1in A,\
Acup{1}, &text{ if } 1notin A.
end{cases}
$$
In other words, if $1$ is in $A$, delete it; if $1$ is not in $A$, adjoin it.

This changes the parity of the sum of elements of $A$, so $f(A)in P_o(S)$. Moveover, $f$ is a bijection since $f^{-1}=f$ (i.e. to undo $f$, apply $f$ again). Therefore, $P_e(S)$ or $P_o(S)$ have the same number of elements. But every subset of $S$ belongs to exactly one of $P_e(S)$ or $P_o(S)$, so each of $P_e(S)$ and $P_o(S)$ has half the total number of subsets of $S$, i.e. $2^{|S|-1}=2^{11}$.

Suppose we choose a random set $Asubset S$ by flipping a fair coin 12 times. We let $iin A$ if $i$-th flip is head. Then the parity of the sum of elements of $A$ is determined by $11$-th flip, hence the probability that the sum of elements of $A$ is even is $frac 12$. This can give the number of such subsets $2^{12}times frac 12 =2^{11}$.