2
$\begingroup$

What is the number of subsets of $A=\{1 ,2 ,3,...,8,9\}$ such that the maximum is in $B = \{1,3,5,7,9 \}$?

For example :

Subset {1, 2} is not in context, since the maximum is not in $B$.


Attempt : I have solved this in a tedious way.

First, I calculate the number of subsets such that it contains even numbers :

Let $\{2, (3,5,7,9) \}$ means that we can put 3, 5, 7, 0r, 9 in $\{ 2, \_ \}$

  • For two-element subsets with one only even number :

$\{2, (3,5,7,9) \}$ means that there are 4 subsets

$\{4, (5,7,9) \}$ means that there are 3 subsets

$\{6, (7,9) \}$ means that there are 2 subsets

$\{8, 9 \}$ means that there is 1 subset

in total 10 subsets.

  • For three-element subsets with one only even number :

$\{2, (3,5,7,9), \_ \}$ the empty gap can be filled by 9-2-3 = 4 possible elements (because we cannot have 4, 6, and 8 in there). There are 4 $\times$ 4 subsets.

$\{4, (5,7,9), \_ \}$ same reasoning as above. There are $3 \times 4$ subsets.

$\{6, (7,9), \_ \}$ There are $2 \times 4$ subsets.

$\{8, 9, \_ \}$ means that there is 4 subsets.

So it is just $10 \times 4 = 40$, the previous times 4.

And so on....

Without even numbers, the number subsets are from $B$, which is $2^{5} = 32$.

In total, i have counted the number of subsets is $1722$. I am quite sure this is correct, but this is quite tedious, are there better ways? Thanks.

$\endgroup$
  • $\begingroup$ The number of subsets in which $1$ is the maximum: $\{1\}$. The number in which $a$ is the maximum should be subsets of $\{1,2,...,a\}$ containing $a$. That is equinumerous to the subsets of $\{1,2,...,a-1\}$. That is $2^{a-1}$. $\endgroup$ – saltandpepper Mar 30 '18 at 17:24
  • 1
    $\begingroup$ In your case $a=3,5,7,9$. Therefore, the total is $1+2^{3-1}+2^{5-1}+2^{7-1}+2^{9-1}=341$. $\endgroup$ – saltandpepper Mar 30 '18 at 17:31
7
$\begingroup$

The answer that you've gotten can't possibly be correct; after all, there are only $2^9=512$ TOTAL subsets of $\{1,2,\ldots,9\}$. So, there's some definite over-counting happening here.

A simpler way to go about things: you can break this up more easily by partitioning the subsets based on the maximum.

How many choices have maximum element $1$? Well, there's only one such subset: $\{1\}$.

How many subsets have maximum element $3$? You must include $3$, and can choose whether or not to include $1$ and $2$. So, there are $4$ possibilities.

For maximum element $5$, you must include $5$; you can choose whether or not to include the elements $1,2,3,4$. So, there are $2^4=16$ possibilities.

Continuing in this way, the total number of subsets is $$ 2^0+2^2+2^4+2^6+2^8=341. $$

$\endgroup$
  • $\begingroup$ Thanks Nick. Much more concise and compact.. i even forgot to calculate the total number of subsets from $A$. $\endgroup$ – Arief Anbiya Mar 30 '18 at 17:44

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.