16
$\begingroup$

How many subsets of set $\{1,2,...,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, ....) 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- ....

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$
  • 12
    $\begingroup$ The number of subsets with no odd integers is just the number of subsets of $\left\{2, 4, 6, 8, 10\right\}$. $\endgroup$ – symplectomorphic Jan 15 '17 at 4:43
  • 3
    $\begingroup$ @symplectomorphic Oh right, what rubbish have I been doing! $\endgroup$ – Osheen Sachdev Jan 15 '17 at 4:44
48
$\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$
  • $\begingroup$ Could you elucidate on the single, empty, odd subset? (Thanks for providing such an interesting, alternate solution, btw!) $\endgroup$ – DukeZhou Jan 15 '17 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$ – Osheen Sachdev Jan 16 '17 at 2:43
3
$\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$
  • $\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$ – symplectomorphic Jan 15 '17 at 4:51
  • $\begingroup$ @symplectomorphic sorry that's what I meant. $\endgroup$ – Osheen Sachdev Jan 15 '17 at 4:53
  • 1
    $\begingroup$ Ah you got it, good, well done $\endgroup$ – Joffan Jan 15 '17 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.