Finding minimum given constraints

Question

120 students enter a contest. The contest have 5 questions. It is known that for questions 1-5, 96, 83, 74, 66, 35 have scored respectively. If a student can win an award if he or she scored at least 3 times, what is the minimum number of students who win an award?

Answer 1

The answer is $40$. I don't know if there is a mathematically elegant way to arrive at this answer, but I used a combination of simple logic and brute force computing.

If $x_i$ is the number of people who got exactly $i$ correct answers, we can immediately write two equations: $$x_0+x_1+x_2+x_3+x_4+x_5 = 120 \tag{1}$$ and $$S_{tot}= 0x_0+ 1x_1+2x_2+3x_3+4x_4+5x_5 = 96+83+74+66+35 =354\tag{2}$$ where $S_{tot}$ is the total number of correct answers.

Let us separate $S_{tot}$ into two parts, such that $S_{tot}=S_{good}+S_{bad}$, where $S_{good}=0x_0+ 1x_1+2x_2$ and $S_{bad}= 3x_3+4x_4+5x_5$. We want the number of people who scored $3$ or higher to be as small as possible, which means we want $S_{good}$ to be as large as possible. The max of $S_{good}$ occurs when $x_2=120$ (and all other $x_i=0$) making $S_{good}=240$. But we see this isn't enough to fulfill equation $2$, i.e. $S_{tot}-S_{good} = 354-240 = 114$. Clearly, we need $S_{bad}>0$. Now, how do we make $S_{bad}$ large enough to cover the missing $114$ while using as few people of the categories $x_3$, $x_4$ and $x_5$ as possible?

We use as many $x_5$ people as possible, as they count for the most ($5$) in $S_{bad}$, and if this is not enough, we use the $x_4$ people and then the $x_3$ people. For each $x_5$ person we add, we must subtract an $x_2$ person, since the sum of people must remain $120$. Each $x_5$ person therefore adds $5-2=3$ to the total. We therefore need $\frac{114}{3}=38$ $x_5$ people. However, since an $x_5$ person must have gotten all $5$ questions correct, and the fifth question was only answered correctly by $35$ people, $x_5 \le 35$. We set $x_5=35$ and find that $$S_{good}+S_{bad} = 2(120-35)+5(35) = 345$$ We are thus still missing $354-345=9$. We need to add some $x_4$ people, where each adds $4-2=2$ to the total. We therefore need $\lceil \frac{9}{2}\rceil=5$ $x_4$ people. This gives $$S_{good}+S_{bad} = 2(120-(35+5))+4(5) + 5(35) = 355$$ We now have a sum which is $1$ too large. We can fix this by changing an $x_2$ person into a $x_1$ person, giving the final result $$ \bbox[5px,border:2px solid red] {\begin{align} S_{tot}=S_{good}+S_{bad} &= 0x_0+ 1x_1+2x_2+3x_3+4x_4+5x_5 \\ & = 0(0)+ 1(1)+2(79)+3(0)+4(5)+5(35) = 354 \end{align}}$$ We see that $x_3+x_4+x_5=0+5+35=40$, which is the answer I gave at the start. However, we still need to show that this result is compatible with the distribution of correct Answers given, which was $A_1=96$, $A_2=83$, $A_3=74$, $A_4=66$ and $A_5=35$.

So, we have $x_5=35$. This means $35$ people got all $5$ questions correct. We can therefore subtract $35$ from all the correct answers, to find the new distribution of correct answers which we need to distribute among the remaining $x_1$, $x_2$ and $x_4$ people. Subtracting $35$ we get $A_1=61$, $A_2=48$, $A_3=39$, $A_4=31$ and $A_5=0$.

And we have $x_4=5$. Since $A_5=0$, the people having $4$ correct answers must have answered exactly $A_1$ to $A_4$ correctly. We can therefore subtract $5$ from each of these and get $A_1=56$, $A_2=43$, $A_3=34$, $A_4=26$ and $A_5=0$.

Before we look at $x_2$, let us handle $x_1=1$. One person answered exactly $1$ question correctly and there is no information to indicate which question it was (and it doesn't matter). Let's suppose it was $A_2$. Subtracting $1$ from $A_2$ gives $A_1=56$, $A_2=42$, $A_3=34$, $A_4=26$ and $A_5=0$.

And we have finally that $x_2=79$. We need to know if there is some combination of $79$ people getting $2$ correct answers which, when combined, can result in the distribution of correct answers given in the previous paragraph. This is where I used brute force computing. And the answer was Yes. In fact, there were 300 possible combinations (if I had selected a different question for the $x_1$ to answer, each of the $3$ possibilities would have give $276$ possible combinations).

Selecting one of the possible combinations gives the answer below. The first yellow area is the $x_5=35$. The green area is the $x_4=5$. The next yellow is the $x_1=1$. The blue and orange bits is the selected solution for $x_2$.