How many subsets of set $\{1,2,\ldots,10\}$ contain at least one odd integer?

Question

How many subsets of set $\{1,2,\ldots,10\}$ contain at least one odd integer?

My Working:
What I can think of is subtracting the no. of subsets that don't contain a single odd number from the total number of subsets as if we calculate it for single cases (like $1$ odd integer, $2$ odd integers, $\ldots$) it would be pretty long.

As there needs to be no odd integer, the maximum number of elements in the set is $5$ (only $5$ even integers are there in the superset).

Case 1: $0$ elements: $1$ set

Case 2: $1$ element: $5$ sets ($1$ even integer in each set)

Case 3: $2$ elements: $(5)(5)$ sets ($1$ element odd and $1$ even) $+\binom{5}{2}$ sets (both elements even)
which gives $35$ sets

Case 4: $3$ elements: $\cdots$

Problem:
This is getting complicated and I'm pretty sure I'll mess up if I proceed further. Is there any other way of solving this question?

Answer 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.

Answer 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$

Answer 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$.

Answer 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$