How many subsets of set $\{1,2,\ldots,10\}$ contain at least one odd integer?
Solution 1:
This is a classic case where looking at the excluded space is far easier.
Any subset without at least one odd integer is a subset of $\{2,4,6,8,10\}$.
There are $2^{10}$ subsets of $\{1,2,3,4,5,6,7,8,9,10\}$ and $2^5$ subsets of $\{2,4,6,8,10\}$. So there are $2^{10}-2^5$ $=1024-32$ $=992$ subsets of $\{1,2,3,4,5,6,7,8,9,10\}$ which include at least one odd number.
Solution 2:
Others have already explained the easy solution, here is an alternative more similar to what you tried.
We want to know how many subsets contain exactly $k$ odd integers, from $k = 1$ to $5$, and sum.
- $k = 1$: $\binom{5}{1} = 5$ possible subsets of $\{1,3,5,7,9\}$
- $k = 2$: $\binom{5}{2} = 10$ possible subsets of $\{1,3,5,7,9\}$
- $k = 3$: $\binom{5}{3} = 10$ possible subsets of $\{1,3,5,7,9\}$
- $k = 4$: $\binom{5}{4} = 5$ possible subsets of $\{1,3,5,7,9\}$
- $k = 5$: $\binom{5}{5} = 1$ possible subsets of $\{1,3,5,7,9\}$
In each case, we can add some even integers, so we multiply by $2^5 = 32$. Then,
$2^5 \sum_{k=1}^5 \binom{5}{k} = 32 (5+10+10+5+1) = 992$
But effectively this can be simpler:
$2^5 \sum_{k=1}^5 \binom{5}{k} = 2^5 \left( \sum_{k=0}^5 \binom{5}{k} - \binom{5}{0} \right) = 2^5 \left( 2^5 - 1 \right) = 2^{10} - 2^5 = 992$
Solution 3:
A subset of $\{1,2,\ldots,10\}$ that contains at least one odd number is of the form $A \cup B$, where $A$ is a subset of $\{2,4,6,8,10\}$ and $B$ is a non-empty subset of $\{1,3,5,7,9\}$. The set $\{2,4,6,8,10\}$ has $2^5=32$ subsets. The set $\{1,3,5,7,9\}$ has $2^5=32$ subsets, of which $31$ are nonempty. Therefore, the answer is $32 \cdot 31 = 992$.
Solution 4:
Never mind, got it...thanks sumplectomorphic!
Total number of subsets= $2^{10}$
Total number of subsets with no odd integer are subsets of $\{ 2,4,6,8,10 \}$
No. of subsets with no odd integers=$2^5$
Hence total no. of subsets with at least one odd integer is given by $2^{10}-2^5$