16
$\begingroup$

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?

$\endgroup$
0

4 Answers 4

54
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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$

$\endgroup$
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Could you elucidate on the single, empty, odd subset? (Thanks for providing such an interesting, alternate solution, btw!) $\endgroup$
    – DukeZhou
    Commented Jan 15, 2017 at 20:52
  • 1
    $\begingroup$ @DukeZhou because we want at least 1 odd integer to be a part of the set AUB. If there is 1 empty set possible then taking B={$\phi$} AUB won't contain any element of the second set which doesn't satisfy the question's requirement. We will end up counting more possibilities than the actual ones. $\endgroup$
    – oshhh
    Commented Jan 16, 2017 at 2:43
4
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Well, no. The subsets with no odd integers are subsets of $\color{blue}{\left\{2, 4, 6, 8, 10\right\}}$. Of course the number of them is the same as the number of subsets of $\color{red}{\left\{1, 2, 3, 4, 5\right\}}$, but that is not what you wrote. $\endgroup$ Commented Jan 15, 2017 at 4:51
  • $\begingroup$ @symplectomorphic sorry that's what I meant. $\endgroup$
    – oshhh
    Commented Jan 15, 2017 at 4:53
  • 1
    $\begingroup$ Ah you got it, good, well done $\endgroup$
    – Joffan
    Commented Jan 15, 2017 at 4:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .