How many distinct subsets of the set $S=\{1,8,9,39,52,91\}$ have odd sums?

Question

How many distinct subsets of the set $S=\{1,8,9,39,52,91\}$ have odd sums?

Let, $O = $ Odd, and $E = $ Even. I figured, that only $\text{odd}+\text{even}=\text{odd}$, so I divided up the problem into 5 cases:

Case 1: ${O}$

Case 2: ${O,E}$

Case 3: ${O,O,O}$ and ${O,E,E}$

Case 4: ${O,O,O,E}$

Case 5: ${O,O,O,E,E}$

and I found $28$ such subsets, but that's incorrect.

Answer 1

As suggested by @LordSharktheUnknown, you can pair up the subsets of $S$ as follows. If $A \subset S$ and $1 \notin A$, then $A$ is paired up with $A \cup \{ 1 \}$.

For each pair, only one of the sets in the pair has an odd sum.

Thus, half of the subsets of $S$ have an odd sum.

Answer 2

There is a bijection between the odd-summed subsets of $S$ and the set of subsets of $\{1,8,9,39,52\}$ given by removing $91$ from any set which contains it.

It's inverse is given by taking any subset, and if it has odd sum, don't do anything to it, and if it has even sum, include $91$.

Answer 3

You have the right idea, but since you have 4 odd numbers and 2 even numbers, the number of such subset is $$ {4 \choose 1}+{4 \choose 1}{2 \choose 1}+{4 \choose 3}+{4 \choose 1}{2 \choose 2}+{4 \choose 3}{2 \choose 1}+{4 \choose 3}{2 \choose 2}=32 $$ This is half of the subsets as mentioned by @LordSharktheUnknown and @littleO.

Answer 4

There are 4 odd numbers in your set. A subset of $S$ has an odd sum if and only if the number of odd elements of the subset is odd. The number of ways of choosing an odd number of odd numbers from $S$ is $$c(4,1) + c(4, 3) = 8$$ For each of these possibilities there are 4 subsets that have sums that are odd numbers. This can be seen by adding 0 even numbers, add in {8}, add in {52}, or add in {8, 52}. Thus there are 32 possibilities.

Answer 5

We can use parity to approach this problem. Note that in this set ${1,8,9,39,52,91}$, one is odd, and five are even. Let's list the ways in which we will sum up to an odd number:

$$[odd]$$ $$[odd,odd,odd]$$ $$[odd,even]$$ $$[odd,even,even]$$ $$[odd,odd,odd,even]$$ $$[odd,odd,odd,even,even]$$

In these cases, we have $\binom{4}{1}+\binom{4}{3}+\binom{4}{1} \binom{2}{1}+\binom{4}{1} \binom{2}{2}+\binom{4}{3} \binom{2}{1}+\binom{4}{3} \binom{2}{2}$, respectively. Like everyone who answered, I also get $\boxed{32}$.