# Need help using the Inclusion-Exclusion Principle to count the overlaps between 4 sets?

In a class, 18 students like to play chess, 23 like to play soccer, 21 like biking, and 17 like jogging. The number of those who like to play both chess and soccer is 9. We also know that 7 students like chess and biking, 6 students like chess and jogging, 12 like soccer and biking, 9 like soccer and jogging, and finally 12 students like biking and jogging. There are 4 students who like chess, soccer, and biking, 3 who like chess, soccer, and jogging, 5 who like chess, biking, and jogging, and 7 who like soccer, biking, and jogging. Finally, there are 3 students who like all four activities. In addition, we know that every student likes at least one of these activities. How many students are there in the class?

I know this is a case of using the inclusion-exclusion principle, but I'm a little overwhelmed, given that there are 4 sets. Can someone please explain this to me? Thanks!

-
This is absolutely not something to be tagged under set-theory. At most it might fit under elementary-set-theory. I would still protest, as this is a question about discrete mathematics more than it is about set theory. – Asaf Karagila May 3 '11 at 18:42
Oh that was my mistake. I started filling in a tag about sets and clicked the wrong one. Sorry! – Chloe May 3 '11 at 18:43
It's fine, just try not to be so harsh on the Save Edits the next time. :-) – Asaf Karagila May 3 '11 at 18:44

Take $S$ to be the set of kids who play soccer; $C$ of kids who play chess; $B$ for biking; and $J$ for jogging.

If you just add up $|S|+|C|+|J|+|B|$, then you are overcounting: any kid who likes more than one sport is getting counted as many times as there are sports he likes. So you need to compensate for that.

You can compensate for those who like exactly two sports by subtracting the six pairwise intersections: $|S\cap C|$, $|S\cap J|$, $|S\cap B|$, $|C\cap J|$, $|C\cap B|$, and $|J\cap B|$. Now, you've counted everyone who likes just one sport once, everyone who likes exactly two sports once (you counted them twice to begin with, and have subtracted them once now).

But you've overcompensated for kids who like three or more sports: for kids who like three sports, you counted them three times when you counted $|S|+|C|+|J|+|B|$, and then you subtracted them three times when you subtracted the pairwise intersections (since they are in all three pairwise intersections). For kids who like all four sports, you counted them 4 times to begin with but now you subtracted them six times... we'll deal with those later...

To compensate for kids who like exactly three sports, which you have now not counted at all, we just need to add the four 3-fold intersections; $|S\cap C\cap J|$, $|S\cap C\cap B|$, $S\cap J\cap B|$ and $|C\cap J\cap B|$. We counted them 3 times first, then subtracted them three times, now add them once. Great.

But now what about the kids who like all four sports? You counted them four times at first; then you subtracted them six times when you dealt with pairs; and now you've added them four times when you counted 3-fold intersections; that means that you've counted them 8 times and subtracted them six times, so they are still overcounted. You need to count how many kids like all four sports and subtract them to get the right total. So you need to subtract $|S\cap C\cap J\cap B|$.

-
Thank you. I really just needed it laid out like that. Working on solving it now. – Chloe May 3 '11 at 18:57
@Chloe: Inclusion-Exclusion just goes like that. First add the 1-folds; then subtract the 2-folds; then add the 3-folds; then subtract the 4-folds; then add the 5-folds; then subtract the 6-folds. Etc. The number of $k$-folds when you have $n$ categories to begin with is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$, the number of ways of choosing $k$ out of $n$ possibilities. – Arturo Magidin May 3 '11 at 19:01
+1: This is a great answer. It's funny how the math works out so that you just go +/- down the line. – Michael Chen May 3 '11 at 23:47

given sets $X_1, X_2, X_3, X_4$ we have $$|\cup X_i|=\sum_i|X_i|-\sum_{i\neq j}|X_i\cap X_j|+\sum_{i\neq j\neq k}|X_i\cap X_j\cap X_k|-|\cap X_i|$$ so in your example this is $$(18+23+21+17)-(9+7+6+12+9+12)+(4+3+5+7)-3=40$$

-