Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Principle of Inclusion-Exclusion Help

  1. Apr 11, 2004 #1
    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! :biggrin: thanks in advance.
  2. jcsd
  3. Apr 11, 2004 #2
    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...
  4. Apr 11, 2004 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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
  5. Apr 11, 2004 #4


    User Avatar

    i don't see how that could be wrong :/
  6. Apr 11, 2004 #5
    ohh thanks Matt...wait im confused..how do I express |CnMnE| in terms of |CnE|, |CnM| and |MnE|...?

    thanks everyone~
  7. Apr 11, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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....
  8. Apr 12, 2004 #7


    User Avatar
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook