$39$ students participated in a math competition. The exam consisted of $6$ problems and each problem was worth $1$ point for a correct solution and $0$ points for an incorrect solution. For any $3$ students, there is at most $1$ problem that was not solved by any of the three. Let $B$ be the sum of all of the scores of the $39$ students. Find the smallest possible value of $B$.
Problem
Source: 2015 CentroAmerican Math Olympiad #6
Tags: OMCC, combinatorics
03.07.2015 04:44
Any idea?
03.07.2015 06:07
Let $S_i$ be the set of students that did not solve problem $i$. Note that the condition is equivalent to that for all $1\le i, j\le 6$, $|S_i\cap S_j|<3$ because if $|S_i\cap S_j|\ge 3$ then take three students $s_1, s_2, s_3\in S_i, S_j$ and all three of them did not solve problems $i, j$, a contradiction. Now let's start with all $S_i$ being disjoint, which means a maximum of $39$ unsolved problems, and start adding more students in each $S_i$. Note that there are a total of $6\times 5/2=15$ intersections of the form $S_i\cap S_j$. Since each intersection adds at most $2$ extra students who did not solve a problem, we can have at most $39+15\times 2=69$ unsolved problems total. There are a total of $39\times 6=234$ problems; with $69$ unsolved it leaves $234-69=\boxed{165}$ solved problems.
04.10.2015 00:29
Using the notations in the solution above, what we are looking for is the maximum of $\sum|S_i|$. Since $|\cup S_i|=\sum|S_i|-\sum|S_i\cap S_j|+...\geq\sum|S_i|-\sum|S_i\cap S_j|$ and $|S_i\cap S_j|\leq 2$, we can conclude that $$\sum|S_i|\leq\binom{6}{2}\cdot 2+39=69.$$Hence, the minimum total score is $6\cdot 39-69=\fbox{165}.$ (Just a more formalized way to write the proof).
30.11.2018 17:31
To end the proof you must give a construction for $B=165$ which satisfies the conditions. And the task is solvable for every $n\ge 30$ instead of $39$
26.03.2020 20:31
A bit shorter solution. We call non-solution situation when student haven't solved certain problem. Let $a_{0}$ students have 0 non-solutions... $a_{6}$ students have 6 non-solutions. So total number of non-solutions is $a_{1}+2a_{2}+...+6a_{6} = 39 - a_{0}+a_{2}+2a_{3}+...+5a_{6}$. Now let's notice that if there are at least $31$ pairs of non-solutions so at least one pair repeats three or more times, and contradiction. So number of such pairs is not greater than 30. From the other side we got $a_{2}+3a_{3}+6a_{4}+10a_{5}+15a_{6}$ pairs of non- solutions. From there we got $a_{2} \leq 30 - 3a_{3} - 6a_{4} -...-15a_{6}$. So, $$39 - a_{0}+a_{2}+2a_{3}+...+5a_{6}\leq 39+30 - a_{0} - a_{3} - 3a_{4} -...- 10a_{6} \leq 69$$. Total number of non-solutions is not more than $69$. So there are at least $234-69=165$ solutions. Equality holds when $30$ students have $2$ non-solutions and others have $1$ non-solution. So example of it is clear and we are done.
29.03.2020 18:14
@Above, Well Done! Mine would have been a bit longer.