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
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Inclusion-exclusion problem
Loading...