A difficult mathematical competition consisted of a Part I and a Part II with a combined total of $28$ problems. Each contestant solved $7$ problems altogether. For each pair of problems, there were exactly two contestants who solved both of them. Prove that there was a contestant who, in Part I, solved either no problems or at least four problems.
Problem
Source: USAMO 1984 Problem 4
Tags: AMC, USA(J)MO, USAMO, algebra, system of equations, combinatorics unsolved, combinatorics
17.08.2011 05:37
This can't really be the original wording, can it? (Usually the USAMO is not written in British English.) It's appeared once before on the forum that I see, but no solutions there. Fixed.
17.08.2011 05:44
The above wording is the "kalva" version. The original problem statement was A dfficult mathematical competition consisted of a Part I and a Part II with a combined total of $28$ problems. Each contestant solved $7$ problems altogether. For each pair of problems, there were exactly two contestants who solved both of them. Prove that there was a contestant who, in Part I, solved either no problems or at least four problems. Fixed.
02.02.2013 02:24
Huh, no solution on either thread until now? I found even a third thread by searching but there are no solutions either. There are $\textstyle\binom{28}{2}$ pairs of problems and each student contributes $\textstyle\binom{7}{2}$ such pairs, so we find that the number of students is \[ \frac{2\binom{28}{2}}{\binom{7}{2}} = 36. \] Suppose that Part I has $n$ problems, and that $a,b,c$ students scored 1,2,3 respectively. Let us suppose for contradiction that $a+b+c=36$. By double counting in the same manner as above, we obtain the system of equations \begin{align} a+b+c &= 36 \\ b+3c &= 2\binom{n}{2} \\ 6a+10b+12c &= 2n(28-n) \end{align} Subtracting 6 times (1) and twice (2) from (3) gives the identity \begin{align*} b &= \frac{2n(28-n)-216-2n(n-1)}{2} \\ &= -2n^2 + 29n - 108 \\ &< -2n^2 + 28n -98 \\ &\le -2(n-7)^2 \\ &\le 0 \end{align*} which is a contradiction.
30.07.2014 06:20
We can also set up three equations by figuring out how many problems each person solved. If we consider an arbitrary problem solved by $x$ people, then each of those people had to solve $6$ other problems, resulting in $6x$ other solved problems. Since all pairs of two problems have to have been solved by a nonzero number of people (in particular two), these $6x$ problems must be spread over all the other $27$ questions, with each question counted twice due to the rule that exactly two contestants solve each question. So, we have that $6x = (2)(27)$, meaning that $9$ people solved any problem. Assuming for contradiction that each contestant solved $1$, $2$, or $3$ problems in part I, label the number of people corresponding to each category as $a$, $b$, and $c$, as v_Enhance did. We then get \[a+b+c = 36\]and \[b+3c = 2\binom{n}{2}\] (to count people solving pairs of problems) as above, with $n$ problems in part I, but we then also have that \[a+2b+3c = 9n\]Taking $-3$ times the first equation, $-2$ times the second equation, and $3$ times the third equation and adding, we get:\[b = -2n^2+29n-108 = -2\left(n-\frac{29}{4}\right)^2-\frac{23}{8} < 0\]which is a contradiction.