Thread: 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.

Originally Posted by veronicak5678

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 . How can we apply this to our problem?

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?

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.