How many distinct subsets of the set S={1,8,9,39,52,91} have odd sums?
Note that we can choose any of the "odds" for a subset = 4 subsets
And choosing any two of the elements we need a set of { even, odd} to have an odd sum
We have 2 evens and they can be paired with any of the 4 odds..so 2 * 4 = 8 subsets
And choosing any 3 of the elements we need either
{ even, even, odd} or { odd, odd, odd} to have an odd sum
In the first case....we can choose both evens and pair them with each of the 4 odds = 4 subsets
In the second case....we can choose any 3 of the 4 odds = 4C3 = 4 subsets
And choosing any 4 of the elements we can have ( even, odd, odd, odd}
We have 2 evens and again, we can choose any 3 of 4 odds = 2 * 4C3 = 2 * 4 = 8
And choosing any 5 of the elements we just need (even, even, odd, odd, odd}
The two evens will appear in any of these sets by default and, again, we only need to choose any 3 of 4 odds to complete the set = 4C3 = 4 subsets
Note that we cannot take all 6 elements as a sum.....[it would be even...]
So...the total possible subsets = 4 + 8 + 4 + 4 + 8 + 4 = 32 subsets
