Results 1 to 4 of 4

Math Help - Inclusion/Exclusion

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

    Inclusion/Exclusion

    I know the formula for finding the total and I know why this is not enough info, but I guess I don't really understand how to prove this with an example.

    There is a class of all boys. We know that there are a boys who like to
    play chess, b who like to play soccer, c who like biking and d who like hiking. The
    number of those who like to play both chess and soccer is x. There are y boys
    who like chess and biking, z boys who like chess and hiking, u who like soccer
    and biking, v boys who like soccer and hiking, and finally w boys who like biking
    and hiking. We don’t know how many boys like, e.g.,chess, soccer and hiking, but
    we know that everybody likes at least one of these activities. We would like to
    know how many boys are in the class.

    (a) Show by an example that this is not determined by what we know.
    (b) Prove that we can at least conclude that the number of boys in the class
    is at most a + b + c + d, and at least a + b + c + d - x - y- z - u - v- w.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by veronicak5678 View Post
    I know the formula for finding the total and I know why this is not enough info, but I guess I don't really understand how to prove this with an example.

    There is a class of all boys. We know that there are a boys who like to
    play chess, b who like to play soccer, c who like biking and d who like hiking. The
    number of those who like to play both chess and soccer is x. There are y boys
    who like chess and biking, z boys who like chess and hiking, u who like soccer
    and biking, v boys who like soccer and hiking, and finally w boys who like biking
    and hiking. We don’t know how many boys like, e.g.,chess, soccer and hiking, but
    we know that everybody likes at least one of these activities. We would like to
    know how many boys are in the class.

    (a) Show by an example that this is not determined by what we know.
    (b) Prove that we can at least conclude that the number of boys in the class
    is at most a + b + c + d, and at least a + b + c + d - x - y- z - u - v- w.
    Work through it line by line. Recall that the inclusion-exclusion principle says that \displaystyle \#\left(\bigcup_{j=1}^{n}S_j\right)=\sum_{j=1}^{n}  (-1)^{j+1}\sum_{J\subseteq[j]:\#(J)=j}\#\left(\bigcap_{\alpha\in J}S_\alpha\right). How can we apply this to our problem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    225
    Total = a + b + c + d -x - z - u - v - w -....
    we need to intersection of 3 to add and intersections of 4 to subtract. How do I show this with an example?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    So, let C, S, B, H be the sets of boys who like chess, soccer, biking and hiking, respectively. Then the size of the class is (I'll omit the intersection symbols and the vertical bars)

    C + S + B + H - CS - CB - CH - SB - SH - BH + CSB + CSH + CBH + SBH - CSBH.

    Given some number of elements in C, S, B, H, it is easy to find examples where the class is the the largest or the smallest. In the first case, make C, S, B, H disjoint. In the second case, make all pairwise intersections nonempty, but all triple intersections (and thus CSBH) empty, like this:



    To prove that C + S + B + H - CS - CB - CH - SB - SH - BH is the smallest class size, note that CSBH is less than each of CSB, CSH, CBH, SBH, so CSBH < CSB + CSH + CBH + SBH. To prove that C + S + B + H is the largest class size, note that CSB + CSH + CBH + SBH < CS + CB + CH + SB + SH + BH because for each term in the left-hand side there is its own greater term in the right-hand side.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2011, 11:38 AM
  2. inclusion & exclusion help
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 14th 2010, 10:57 AM
  3. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2009, 09:46 AM
  4. Inclusion-exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 28th 2009, 03:45 AM
  5. inclusion/exclusion
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 18th 2008, 11:31 PM

Search Tags


/mathhelpforum @mathhelpforum