Results 1 to 9 of 9

Math Help - Set theory question

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    4

    Set theory question

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by quaz View Post
    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 \bigg\lfloor\frac{20}{3}\bigg\rfloor+1=7.

    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 2^{14} ways. So the answer is (2^7-1)(2^{14}).

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

    c) Do you see why this is simply 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 2^{18}.

    e) Can you see how to do this now?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello quaz
    Quote Originally Posted by quaz View Post
    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
    S - \{0,3,6,9,12,15,18\}
    =\{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 S -\{7,9,15\}. That's your answer. Can you see why?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2008
    Posts
    14
    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 .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by sid_178 View Post
    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 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 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 A \cap \{11,12\} = \emptyset.

    Note how these are two very different interpretations of essentially the same wording.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2008
    Posts
    14
    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 .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2010
    Posts
    4
    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)
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2010
    Posts
    4

    Inclusion and exclusion question

    edit: sorry for double post, this was supposed to be in a new thread topic
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by quaz View Post
    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 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set theory question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: November 8th 2009, 06:35 PM
  2. Set theory question..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 27th 2009, 12:56 AM
  3. Set Theory Question
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 9th 2008, 12:53 AM
  4. Theory Question
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 13th 2007, 12:24 PM
  5. Set theory question
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 9th 2007, 02:45 PM

Search Tags


/mathhelpforum @mathhelpforum