Principle of Inclusion-Exclusion Help

[ilml]

Principle of Inclusion-Exclusion Help!

Hey! I came upon this problem and I have been intrigued since...it deals with the Principle of Inclusion-Exclusion (PIE):

A group of 100 students took SAT II's in Chinese, English, and Math. Among them, 90 took Chinese, 70 took English, and 60 took Math. What is the smallest number of students who took all three exams?

Ive been stumped because I don't know how to minimize the amount of students taking all three exams...especially since I am not given anything else (like the amount of students who took two of the exams etc). Help please! thanks in advance.

 

[Caldus]

Hmmm...just taking an intuitive guess here:

If there are only 100 students and 220 tests were taken:

It is not possible that every person only took one test, because 220 tests > 100 tests taken in this case.
It is not possible that every person only took two tests, because 220 tests > 200 tests taken in this case.
There are still 20 tests yet to be taken, so at the very least (assuming that every other person took two tests), 20 students took all three tests.

Probably not right though...

 

[matt grime]

If we let C E and M be the sets of those taking Chinese, English and Mathematics resp, then, if u means union and n intersection

100=|CuEuM| = |C|+|E|+|M| -|CnE|-|CnM|- |MnE| +|CnMnE|

you know |C| |E| and |M| and you can thus express the quantity you want in terms of |CnE|, |CnM| and |MnE|

and you can minimize those quite easily

 

[pig]

Probably not right though...

i don't see how that could be wrong :/

 

[ilml]

ohh thanks Matt...wait I am confused..how do I express |CnMnE| in terms of |CnE|, |CnM| and |MnE|...?

thanks everyone~

 

[matt grime]

just rearrange the formula

|CnE|+|CnM|+|EnM| = 120 +|CnMnE|

the thing on the right is what we want to "minimize"

now for example, 90 took chinese 70 took english, then it follows that of the 100, at least 60 took both so |CnE| is at least 60...

 

[verty]

This is how I (layman) would have tackled the problem.

10 didn't take Chinese. 30 didn't take English. 40 didn't take Math. This totals 80, which is the maximum number of students that didn't take some SAT. Therefore at least 20 took all three.