1
$\begingroup$

Let $A =\{1,2,3,4,5,6,7\}$, The how many subsets have 6 as largest element?

My approach -

Total subsets are $2^7 = 128$. Then First I have to exclude the $1$ empty subset i.e. $\{\}$, $6$ sets with $1$ element except $\{6\}$, then two elements not containing $6$ as its element(I am not getting a way to count these element) and the $2$ subsets $\{6,7\},\{7,6\}$. Then I am stuck here as I am not getting the way to count these numbers. Any help?

$\endgroup$
  • 1
    $\begingroup$ Well, none of the sets have 7 so this is the same as asking what are the subsets of B = {1.... 6} they all have 6 so all sets are equal to $C \cup \{6\}$ for some set C. C is a subset of $\{1,...., 5\}$ so we just need to find the subsets of {1,2...5} and add {6} to all of them. There are $2^5$ subset of {1,2....5} so there are the same number of subsets of {12,...5,6} that must have 6 which is the same number of subsets of {1,2,....7} that must have 6 and must not have 7. $\endgroup$ – fleablood Aug 25 '16 at 19:58
  • $\begingroup$ 128 subsets. Half have 6 as an element. 1/4, contain both 6 and 7. So 1/4 have 6 and do not have 7. $\endgroup$ – Doug M Aug 25 '16 at 20:23
3
$\begingroup$

Remember how we determined that the number of subsets was 2 to the power of the number of elements.

We did that because for each element, $a$, either $a$ could be in a subset. So the total number of sets was the product of all the choices each of which was 2.

This is the same. Either 1 is in a subset or not. That 2 choices. Either 2 is in the subset or not. That's $2*2$ choice. Keep it up EXCEPT notice $6$ must be in the subset so that is only $1$ choice and $7$ must not be in the set so that's only one set.

So the number of sets is $2*2....*2*1*1$ which is what.

....

Or

....

Don't eliminate the sets one at a time. Remove ALL the subsets that do not have $6$ in them. How many do not have $6$. Remove ALL the subsets that do have $7$. How many is that? Then to avoid double counting add back the ones that had $6$ and didn't have $7$. How many is that?

....

Or

....

Figure 1/2 of the 128 have 6 and half do not. That only leaves half of them acceptable. Then half of those have 7 and half to not. That leaves only half of those acceptable.

....

Or

....

No set has $7$. So all the elements are taken from {$1,2,3,4,5,6$}.

All sets have $6$. So all elements that aren't $6$ are taken from {$1,2,3,4,5$} and $6$ is always added to it.

There are $2^5$ subsets of {$1,2,3,4,5$} and we are only taking those and sticking a $6$ into them. There are $2^5$ such sets.

$\endgroup$
  • $\begingroup$ I like your way of dividing it up. That makes good sense! $\endgroup$ – John Aug 25 '16 at 20:16
  • 1
    $\begingroup$ You have to be careful in assuming that your condition is exactly 1/2 though. In this case you can but if you were asked say How many sets have the numbers add up to an even number and contain the number 5 you can't assume half the sets add up to an even number and of those half of them contain 5. $\endgroup$ – fleablood Aug 25 '16 at 20:23
6
$\begingroup$

Hint:

Include $6$. How many ways are there to include zero through five members of $\{1,2,3,4,5\}$?

(Order doesn't matter with sets.)

$\endgroup$
  • $\begingroup$ okay now i got. There are total subsets = 2^6 = 64. $\endgroup$ – Brij Raj Kishore Aug 25 '16 at 19:58
  • $\begingroup$ The element $6$ has to be there. The element $7$ can't be in there. But any, all, or none of $1$ through $5$ can be. In other words, if $S_5 = \{1,2,3,4,5\}$, then the union of $\{6\}$ and any subset of $S_5$ will have $6$ as the largest element. You figured out the number of subsets for a set of $7$ elements. How about for $5$ elements? $\endgroup$ – John Aug 25 '16 at 20:02
  • $\begingroup$ Regarding your answer, not quite. It's not optional whether $6$ is in there or not. $\endgroup$ – John Aug 25 '16 at 20:03
  • $\begingroup$ So the answer is 2^6 -1 - 5. Am i correct? But in option there are 4 options as - 32,31,64,128. $\endgroup$ – Brij Raj Kishore Aug 25 '16 at 20:05
  • 1
    $\begingroup$ No set has 7. All sets have 6. So all sets are a subset of {1,2,3,4,5} unioned up with {6}. How many sets are there. There is {6} = {} + {6}; there is {1,4,5,6} = {1,4,5} + {6}. They are all C + {6} where $C \subset$ {1,2,3,4,5}. How many such sets are there. $\endgroup$ – fleablood Aug 25 '16 at 20:14
1
$\begingroup$

Think about it we need $6$ as an element but we can't have $7$ because $7$ is larger than $6$, we can have anything else.

What we're looking for: How many subsets have $6$ as an element but not $7$?

We must choose to include $6$, that gives $1$ choice. We may choose to to include $1$ or not, that gives $2$ choices. We may choose to include $2$ or not, that gives $2$ choices. We may choose to include $3$ or not, that gives $2$ choices. We may choose to include $4$ or not, that gives $2$ choices. We may choose to include $5$ or not, that gives $2$ choices. We must choose not to include $7$, that gives $1$ choice. By the multiplication principle the number subsets with $6$ but not $7$ is:

$$1•2•2•2•2•2•1=2^5$$

$\endgroup$

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.