What is the highest grade that Roma can get?

$30$ students took part in the Mathematics Olympiad. They were offered $8$ problems. First, the jury checked the participants' work, giving each problem a "solved" or "not solved" grade. Then, for each task, its cost is determined - a natural number, which is equal to the number of participants who did not solve it. The total cost of solved problems by a student makes up his overall grade. It turned out that the boy Roma received a grade lower than everyone else. What is the highest grade he could get?

I got $55$; $4$ problems, from $13$ to $17$ points. Found this number by brute force. Is it correct?

Solution 1:

Observe that if a question is solved by $k$ students, then the total score obtained by all $30$ students for that question is $k(30-k)$. This is maximised when $k = 15$, so the maximum total score of all $30$ students for all $8$ questions are $8 \cdot 15(30-15) = 1800$.

We know that Roma's score must be less than $60$. Otherwise, the total score of the $30$ students would be at least $$60 + 29 \cdot 61 > 1800$$ which contradicts the fact that the total score is at most $1800$.

Claim. Roma's score cannot be $59$.

Proof. Suppose Roma's score is $59$. Then all $29$ other students must get at least $60$, which means the total score is at least $59 + 29 \cdot 60 = 1799$.

• If the total score is $1799$, then there must be one question that is solved by exactly $14$ or $16$ students, while each of the other seven questions is solved by exactly $15$ students. (Why?) Let us consider the question that is not solved by exactly $15$ students.

  • If that question is solved by exactly $14$ students, then the $30$ students in total solve $14 + 7 \cdot 15 = 119$ questions. So, at least one student solves $3$ questions or fewer. Since each question awards either $15$ or $16$ points, this student's score is at most $48$. This contradicts the assumption that Roma's $59$ points is the lowest score.
  • If that question is solved by exactly $16$ students, then the $30$ students in total solve $16 + 7 \cdot 15 = 121$ questions. So, at least one student solves $5$ questions or more. Since each question awards either $15$ or $14$ points, this student's score is at least $70$. As a consequence, the total score of all $30$ students is at least $$59 + 70 + 28 \cdot 60 = 1809.$$ This contradicts the assumption that the total score is $1799$.

• If the total score is $1800$, then each of the eight questions is solved by exactly $15$ students. (Why?) So, each question is worth $15$ points, and hence, each student's score is a multiple of $15$. But Roma's score is $59$, which is not a multiple of $15$.

We can therefore conclude that Roma's score cannot be $59$. $\square$

Now, we prove that Roma can get $58$ points.

Consider the following scenario:

• Roma solves questions 3, 4, 5, 6,
• One student solves questions 3, 4, 7, 8,
• One student solves questions 1, 2, 4, 5,
• $13$ students solve questions 1, 2, 3, 4,
• $14$ students solve questions 5, 6, 7, 8.

The number of points for the eight questions are $16$, $16$, $15$, $14$, $14$, $15$, $15$, and $15$ in that order. So,

• Roma gets $15 + 14 + 14 + 15 = 58$ points,
• The one student who solves questions 3, 4, 7, 8 gets $15 + 14 + 15 + 15 = 59$ points,
• The one student who solves questions 1, 2, 4, 5 gets $16 + 16 + 14 + 14 = 60$ points,
• The $13$ students who solve questions 1, 2, 3, 4 get $16 + 16 + 15 + 14 = 61$ points each,
• The $14$ students who solve questions 5, 6, 7, 8 get $14 + 15 + 15 + 15 = 59$ points each.

So, in this scenario, Roma gets $58$ points while the others get at least $59$ points.