Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
$200$ students take a test with $6$ questions. For each question, at least $120$ students got it correct. Show that for some two students, every question is done correctly by at least one of them.
From the given, the average number of questions that a student got correct is at least $\dfrac{120\cdot 6}{200}=3.6$. But how does this imply the desired conclusion?
Since each question got at least 120 correct answers there were at least 720 correct answers, this means the average number of correct answers per student was 3.6. It follows there are students who got more than 3 correct answers.
If any student got 6 correct answers, they can be paired with any other student.
If any student got 5 correct answers, then we know there at least 120 others who got the question they missed, and that they can be paired with.
If any student got 4 correct answers, then of the 200 students no more than 80 got each of the questions that that student missed wrong. Hence at least 200 - 80 - 80 = 40 must've got both right. So there are at least 40 students that student can be paired with.
The meaning of the question seems to be "prove that a pair exists", since it is clear that a pair can be constructed where neither person has answered both questions. For example, if there are 120 students with 100% and 80 students with 0% we pick a pair of the 0% students.
So assuming our job is to prove that such a pair must exist, we use proof by contradiction. Assume that there is no pair of students such that together they have the right answers to all the questions. Then the maximum number of questions answered correctly by any one student is less than or equal to three, which contradicts that the total number of questions answered corresponds to 3.6.
For each question, suppose we pick two arbitrary students (not necessarily distinct students) randomly (i.e., pick 2 students "with replacement"). What is the probability that at least one of them answers the question correctly? Let the two students be denoted by $i$ and $j$, and let $X_i$ be the random variable denoting whether student $i$ answers the question correctly, and similarly $X_j$. By the inclusion exclusion principle, it is equal to:
$$\text{Pr}(X_i \cup X_j) = \text{Pr}(X_i) + \text{Pr}(X_j) - \text{Pr}(X_i \cap X_j) \ge 0.6 + 0.6 - 0.36 = 0.84$$
Thus, for $6$ questions, by the linearity of expectation, the expected number of questions that are correct for two randomly picked non necessarily distinct students is at least $0.84 \times 6 = 5.04 > 5$. Thus, by the probabilistic method, there must exist a pair of (non necessarily distinct) student that jointly answer all 6 questions.
Not all students can be below average -- thus some student got at least 4 correct. Now consider the remaining 2 questions. Can you show that some student got both of them?
