0
$\begingroup$

A midterm exam consists of $5$ problems. Students who solve two of those problems correctly get a passing grade. There are $32$ students in the class, and only $8$ students passed. Prove that one of the problems was solved correctly by at most $12$ students.

So $16$ questions were solved correctly, so at least one problem was solved at least $3$ times by the pigeon hole principle. Where do the $12$ students come from? I mean can't the $24$ students solve $0$ questions or do I assume that at least each student solve one question? Thanks.

$\endgroup$
4
  • $\begingroup$ The assumption that $16$ questions were solved correctly is incorrect. What if some people only got $1$ question correct? They still would've failed. $\endgroup$ – Landuros Oct 2 '19 at 2:04
  • $\begingroup$ 8 students passed and they need to solve two correctly, so 16 questions must be correct or am I misunderstanding? $\endgroup$ – Jimmy Ceh Oct 2 '19 at 2:06
  • 1
    $\begingroup$ You need to consider the worst case scenario. E.g. If all 8 students who passed answered all 5 problems correctly, can we still find a problem that was solved correctly by at most 12 students? $\endgroup$ – Calvin Lin Oct 2 '19 at 2:15
  • $\begingroup$ If the conclusion is false, what is the smallest number of correct answers that could have been given? $\endgroup$ – saulspatz Oct 2 '19 at 2:21
2
$\begingroup$

Suppose not. Then all problems were solved by atleast $13$ students and therefore, the class solved atleast $65$ problems.

But only $8$ students passed, hence maximum number of problems that were done correctly are $8\times 5+24=64$, we have reached the desired contradiction.

$\endgroup$
0
$\begingroup$

Based on what you wrote, it is not true that "only 16 questions were solved correctly". What we know is that "at least 16 questions were solved correctly".

It might be possible that $8\times5 = 40$ questions were solved correctly, like if those who passed got all questions correct.


Hint: Consider the $32-8=24$ people who failed. Can we guarantee that there is a problem that is solved by at most 4 people?

Corollary: That problem is solved by at most $4+8=12$ people.

$\endgroup$
3
  • $\begingroup$ What if the 24 people solved 0 questions. Then wouldn't one problem be solved by at most 8 students? $\endgroup$ – Jimmy Ceh Oct 2 '19 at 2:49
  • 1
    $\begingroup$ So what? There being a problem solved by at most 8 students does not contradict the fact that there is a problem solved by at most 12 students. $\endgroup$ – Calvin Lin Oct 2 '19 at 2:50
  • $\begingroup$ Do you understand my comment of "You need to consider the worst case scenario"? Currently, you are proving the statement for the best case scenario. $\endgroup$ – Calvin Lin Oct 2 '19 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.