Set theory question

May 2010
4
0
Let S = {0, 1, ... , 20}.
a) How many subsets of S are there?
b) How many subsets of S contain numbers divisible by 3?
c) How many subsets of S contain 7, 9 and 15?
d) How many subsets of S do not contain 7, 9 and 15?
e) How many subsets of S contain 7, 9, and 15 but not 11 and 12?

a) 2^21
b) stuck!
c) Stuck!
d) answer from a) - answer from c)
e) stuck

If anyone could help out it would be greatly appreciated!
Thanks in advance
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Let S = {0, 1, ... , 20}.
a) How many subsets of S are there?
b) How many subsets of S contain numbers divisible by 3?
c) How many subsets of S contain 7, 9 and 15?
d) How many subsets of S do not contain 7, 9 and 15?
e) How many subsets of S contain 7, 9, and 15 but not 11 and 12?

a) 2^21
b) stuck!
c) Stuck!
d) answer from a) - answer from c)
e) stuck

If anyone could help out it would be greatly appreciated!
Thanks in advance
b) I'll assume this means "How many subsets of S contain at least one number divisible by 3?"

We can count how many elements of S are divisible by 3 without enumerating (listing) them. This is given by \(\displaystyle \bigg\lfloor\frac{20}{3}\bigg\rfloor+1=7\).

\(\displaystyle 2^7-1\) is the number of ways to choose at least one of these 7 elements. We can choose the remaining 14 elements in \(\displaystyle 2^{14}\) ways. So the answer is \(\displaystyle (2^7-1)(2^{14})\).

Equivalently, note that there are \(\displaystyle 2^{14}\) subsets that do not contain any of those seven elements, then subtract that from \(\displaystyle 2^{21}\).

c) Do you see why this is simply \(\displaystyle 2^{18}\)?

d) I actually think the wording on this problem could be better. If a subset contains 7 but not 9 or 15, do we count it or not? If yes, then we take (answer from a) - (answer from c) like you said. If no, then the answer is again \(\displaystyle 2^{18}\).

e) Can you see how to do this now?
 

Grandad

MHF Hall of Honor
Dec 2008
2,570
1,416
South Coast of England
Hello quaz
Let S = {0, 1, ... , 20}.
a) How many subsets of S are there?
b) How many subsets of S contain numbers divisible by 3?
c) How many subsets of S contain 7, 9 and 15?
d) How many subsets of S do not contain 7, 9 and 15?
e) How many subsets of S contain 7, 9, and 15 but not 11 and 12?

a) 2^21
b) stuck!
c) Stuck!
d) answer from a) - answer from c)
e) stuck

If anyone could help out it would be greatly appreciated!
Thanks in advance
Your answer to (a) is correct.

For (b), find how many subsets do not contain any multiples of 3, and subtract from the answer to (a). That is, find the number of subsets of
\(\displaystyle S - \{0,3,6,9,12,15,18\}\)
\(\displaystyle =\{1,2,4,5,7,8,10,11,13,14,16,17,19,20\}\)
That's easy enough, isn't it?

For (c), find the number of subsets there are of \(\displaystyle S -\{7,9,15\}\). That's your answer. Can you see why?

Grandad
 
Sep 2008
14
0
a)Since cardinality of the set is 21 .There are 2^21 subsets in total for the given set .Such a collection of all the subsets of the set is also known as power set .
b)There are in total 7 numbers in the given set which are divisible by 7 namely{0,3,6,9,12,15,18}So there is only one way in which all these seven elements can be dealt with . Rest 14 elements have two ways in which they can be dealt with .Either they are present in the subset or not present in the subset .Therefore there are 2^14 subsets in total which contain all the numbers divisible by three of the given set .
Alternatively this sum is 14C0 +14C1 +14C2 +.....14C14 =2^14 (BECAUSE ..you take either no element from the remaining 14elements or one or two and so on )

c)Similarly,7,9 and 15 are already there in the subsets we are left with 18 elements which can be dealt in two ways ..so answer becomes 2^18.

d)answer to this is total nu,mber of subsets -those subsets which contain 7,9and 15=2^21-2^18.
e)Answer to this is 2^16.Since elements {7,9,15} and {11 and 12 }can be dealt only in one way ..rest 16 elements in two ways ..either present or not present .
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
a)Since cardinality of the set is 21 .There are 2^21 subsets in total for the given set .Such a collection of all the subsets of the set is also known as power set .
b)There are in total 7 numbers in the given set which are divisible by 7 namely{0,3,6,9,12,15,18}So there is only one way in which all these seven elements can be dealt with . Rest 14 elements have two ways in which they can be dealt with .Either they are present in the subset or not present in the subset .Therefore there are 2^14 subsets in total which contain all the numbers divisible by three of the given set .
Alternatively this sum is 14C0 +14C1 +14C2 +.....14C14 =2^14 (BECAUSE ..you take either no element from the remaining 14elements or one or two and so on )

c)Similarly,7,9 and 15 are already there in the subsets we are left with 18 elements which can be dealt in two ways ..so answer becomes 2^18.

d)answer to this is total nu,mber of subsets -those subsets which contain 7,9and 15=2^21-2^18.
e)Answer to this is 2^16.Since elements {7,9,15} and {11 and 12 }can be dealt only in one way ..rest 16 elements in two ways ..either present or not present .
You've demonstrated how I thought the wording in this problem could be better.

Let \(\displaystyle A \subseteq S\).

For d) you interpreted "...do not contain 7, 9 and 15" as "do not contain all of 7, 9, and 15" or in notation \(\displaystyle A \cap \{7,9,15\} \neq \{7,9,15\}\).

For e) you interpreted "...but not 11 and 12" as "but neither 11 nor 12" or in notation \(\displaystyle A \cap \{11,12\} = \emptyset\).

Note how these are two very different interpretations of essentially the same wording.
 
Sep 2008
14
0
Yeah I see your point .
Actually ,What I did was ..according to demorgan's law ..complement of intersection of set A and Set B is union of complement of A and complement of B.
So if set does not contain 7,9 and 12 can be read as it does not contain none of 7 ,9 and 12 .That is how i worked it out .
 
May 2010
4
0
Thank you for all your input but suppose it did say ALL of 7, 9 & 15
I got for c) an answer of 2^21 - 2^18 - 2^3 + 1 + 1
I take away 2^3 because of the subsets of {7,9,15} because they include {7} {9} {7,15} etc
But I've taken away {7,9,15} which fits the requirements so thats why its +1
I've added another 1 because there is phi(set of nothing) since the phi from 2^21 - 2^18 cancel but then 2^3 is taking another phi. Hence add one?

also I'm still having troubles with e)
 
May 2010
4
0
Inclusion and exclusion question

edit: sorry for double post, this was supposed to be in a new thread topic
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Thank you for all your input but suppose it did say ALL of 7, 9 & 15
I got for c) an answer of 2^21 - 2^18 - 2^3 + 1 + 1
I take away 2^3 because of the subsets of {7,9,15} because they include {7} {9} {7,15} etc
But I've taken away {7,9,15} which fits the requirements so thats why its +1
I've added another 1 because there is phi(set of nothing) since the phi from 2^21 - 2^18 cancel but then 2^3 is taking another phi. Hence add one?

also I'm still having troubles with e)
I don't know why you're asking about (c) since the wording of (c) is perfectly clear and the answer is \(\displaystyle 2^{18}\) as described above.

As for (e), sid_178 gave the answer for one interpretation already. For the other interpretation, the answer would be 2^18 - 2^16.