How many students advanced to the next round?

[jb235711]

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?

 

[Bystander]

What's the largest number who can miss at least two?

 

[pbuk]

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?

 

[jb235711]

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.

 

[verty]

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.

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.

 

[jb235711]

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.

 

[pbuk]

To prove that this is an optimal solution you need to answer my question - how many questions are answered incorrectly?

 

[pbuk]

... from which you can get the answer to Bystander's question

 

[pbuk]

Deleted

 

[verty]

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.

 

[jb235711]

To prove that this is an optimal solution you need to answer my question - how many questions are answered incorrectly?

Yes, there are 125 wrong answers, so the most you can fail is 62, so the least that can advance is 38.