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

Inclusion-exclusion problem

  1. Sep 14, 2015 #1
    Can someone give me general guidance on how to solve this problem (it's not homework):
    There were 100 students taking a math contest consisting of four questions. 90 of them got problem 1 correct. 85 of them got problem 2 correct. 60 of them got problem 3 correct. 40 of them got problem 4 correct. Anyone who got 3 or more problems correct advanced to the next round. At least how many students advanced to the next round?
     
  2. jcsd
  3. Sep 14, 2015 #2

    Bystander

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    What's the largest number who can miss at least two?
     
  4. Sep 15, 2015 #3
    There is no general method for finding the optimal solution to problems of this type, however a good start is often to find an upper and/or lower bound. It is also usually a good idea to look at both sides of the data - the question is phrased in terms of passing by getting at least 3 questions right; try looking at the number that fail by getting 2 questions wrong. How many questions are answered wrong overall?
     
  5. Sep 15, 2015 #4
    Thanks for your helps. I got it. There are 275 right answers. Each student gets two right answers. The remaining 75 are distributed so that the number that pass is minimized, 2 question to 37 students and the remaining question to the 38th student.
     
  6. Sep 15, 2015 #5

    verty

    User Avatar
    Homework Helper

    Is this a solution, have you checked that it satisfies the constraints?

    I was definitely thinking there wasn't an easy way to solve this.
     
  7. Sep 15, 2015 #6
    I totally thought there was no easy solution and started doing inclusion-exclusion and stuff, but apparently it is easy. And I double checked that there exists a distribution satisfying 38 students advancing i.e 37 students get 4 right, 1 student gets 3 right and 62 students get 2 right. You can also do 38 students get 4 right, 61 students get 2 right, and 1 student gets 1 right which doesn't change the number of students that advance. From these arrangements you can verify case by case e.g. taking a right answer from a student that has four correct and giving it to a student that has 2 correct will increase the number advancing, and so forth.
     
  8. Sep 15, 2015 #7
    To prove that this is an optimal solution you need to answer my question - how many questions are answered incorrectly?
     
  9. Sep 15, 2015 #8
    ... from which you can get the answer to Bystander's question
     
  10. Sep 15, 2015 #9
    Deleted
     
  11. Sep 15, 2015 #10

    verty

    User Avatar
    Homework Helper

    I'm bowing out of this question. When I look at it, I see a problem with 16 variables and 5 constraints, and as much as I try to convince myself that it is actually is easy, something niggles at me saying, nah, it's not.

    I agree with the analysis that says 38 is a lower bound. I still struggle to show that it is a solution. I'm good at puzzles but this has me stumped. So best of luck to those who can solve it.
     
    Last edited: Sep 15, 2015
  12. Sep 15, 2015 #11
    Yes, there are 125 wrong answers, so the most you can fail is 62, so the least that can advance is 38.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook