0
$\begingroup$

In a quiz there are $12$ questions and $100$ participants. For every question, at least $56$ participants knows the correct answer. How can I show that there are three participants who knows answers to all of the questions?

$\endgroup$
2
  • $\begingroup$ Try some double counting. $\endgroup$ – Aqua Oct 11 '17 at 7:50
  • $\begingroup$ @JohnWatson That seems not to work (at least with naive person-answer incidece counting) as the average person knows only 7 correct answers. A bit more combinatoric is needed. $\endgroup$ – Hagen von Eitzen Oct 11 '17 at 7:53
2
$\begingroup$

A different method:

Here is a much quicker method, which use probabilistic method:

Pick $3$ participants uniform randomly among $100$ participants. Since there is at most $100-56=44$ participants who don't know answer for question $i$, the probability that none of those $3$ participants know the answer for question $i$ is at most $\frac{\binom{44}{3}}{\binom{100}{3}}$. Hence, the expected number of questions that all those $3$ participants don't know is $$\mathbf{E}[X]=12 \cdot \frac{\binom{44}{3}}{\binom{100}{3}}= \frac{172}{175}<1.$$ Hence, there exists $3$ participants who know all answers for $12$ questions.

$\endgroup$
2
$\begingroup$

Let $a_i$ be number of participants who know answer for question $i$. We have $a_i \ge 56$. Let $b_i$ be number of questions that the $i$th participant knows the answers. We have $$a_1+ \ldots + a_{12}=b_1+ \ldots +b_{100}.$$ Without loss of generality, say that $b_i<b_j$ for $i<j$. Then we find $$56 \cdot 12 \le a_1+ \ldots + a_{12}=b_1+ \ldots +b_{100} \le 100 \cdot b_{100}.$$ Thus, $b_{100}>6$, which means the $100$th participant knows answers for at least $7$ questions.


Repeat the whole process above for the remaining $5$ questions and $99$ participants, which we will have $$a_1+ \ldots +a_5=b_1+ \ldots+b_{99}.$$ In here, note that $a_i \ge 55$ since one participant is not taken into account. Hence, we obtain $55 \cdot 5 \le 99 \times b_{99}$, or $b_{99}>2$, i.e. there is one participant among the remaining $99$ participants who knows answers for at least $3$ questions among the remaining $5$ questions.


We do the similar thing for the remaining $2$ questions and $98$ participants. We have $a_1+a_2=b_1+ \ldots+b_{98}$ and $a_i \ge 54$. Hence, $54 \cdot 2 \le 98 \cdot b_{98}$ or $b_{98}>1$. This means among the remaining $98$ participants, there is one that knows the answer to the remaining $2$ questions.


Thus, three participants are picked. We are done.

$\endgroup$
4
  • $\begingroup$ Is not that ${44\choose 3}$ instead ${56\choose 3}$? $\endgroup$ – Aqua Oct 11 '17 at 8:21
  • $\begingroup$ @JohnWatson You're right. Thanks. I edited. $\endgroup$ – Tengu Oct 11 '17 at 8:22
  • $\begingroup$ I 'd like to up vote the second solution. Could you post it as another answer. $\endgroup$ – Aqua Oct 11 '17 at 8:26
  • $\begingroup$ @JohnWatson Sure :) Done. $\endgroup$ – Tengu Oct 11 '17 at 8:28
0
$\begingroup$

I think something is missing from your proposition.

EDIT: I think what you meant in fact is that, there exists a team of three people that have the answer to every question, AS A TEAM, and not three people knowing the answer of all question...

let'st ake an example fitting your statement (at least 56 people, of course I am going to take the least positive situation).

Let's take question 1, from which the first 56 people know the answer, and not the last 44.

Take then question 2, from which the last 56 people know the answer, and not the first 44.

You have now only the middle 12 person that know the answer to the first two questions.

You can take qestion 3, and if the first 28 and the last 28 know the answer, and not the other '' (including the middle 12), no one know the answer to the three first questions, let alone the 12...

$\endgroup$

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.