Eight students solved $8$ problems. a) It turned out that each problem was solved by $5$ students. Prove that there are two students such that each problem is solved by at least one of them. b) If it turned out that each problem was solved by $4$ students, it can happen that there is no pair of students such that each problem is solved by at least one of them. (Give an example.) Proposed by S. Tokarev
Problem
Source:
Tags: pigeonhole principle, linear algebra, matrix
SZRoberson
18.05.2014 08:59
For some reason, Question a) says something about Piegonhole. But I'm not sure what.
whyhavealife
18.05.2014 21:17
a)For each question, 5 students solve it, so the number of theoretical pairs of students where one of them solve it is $5\times 3+ {{5}\choose {2}} =25$. Since there are $8$ questions, the total number of times there is a pair of students so that one of them solves any question is $25*8=200$. The total number of pairs of students is ${8\choose 2}=28$. We now apply pigeonhole principle where the "holes" are the number of pairs of students and the "pigeons" are the number of times a questions is solved by at least one person in a pair. We quickly see that one "hole" must contain $8$ questions solved, which thus proves our answer.
b)We use the same method, except we see that our total pigeons won't necessarily fill up the a hole to $8$.
PlatinumFalcon
11.08.2014 01:59
Alternate Solution (for Part A): We use an Incidence Matrix. Assume, for the sake of contradiction, that for any two students, there exists at least one problem that was not solved between both. Let each $1$ in the matrix denote a problem not solved by a participant, and let a $0$ be defined oppositely. Counting by rows, we have that the maximum number of $1$'s is $8\cdot\binom{3}{2}$, since at most $5$ participants solved each problem. Counting by columns, our lower bound is $\binom{8}{2}$, since between any two participants, at least one problem is not solved. Hence $\binom{8}{2}=28\le 8\cdot\binom{3}{2}=24$, a clear contradiction. We are done. $\blacksquare$