, 2010

If there are four students $S_i$, $1 \le i \le 4$, and $S_1$ and $S_2$ solved the same half of the questions, and $S_3$ and $S_4$ solved the other half; then we cannot partition 2010 questions into three sets of 670 questions so that each set can be assigned to a student who solved all of those questions. Now we will show that this can be done if there are five students.

Assume that there are five students $S_i$, $1 \le i \le 5$, in the class. For $1 \le i \le 5$, let $n_i$ be the number of questions that are not solved only by $S_i$; and for $1 \le i < j \le 5$, let $n_{\{ij\}} = n_{\{ji\}}$ be the number of questions that are solved neither by $S_i$ nor by $S_j$. Since there are at most two students who did not solve any given question, we have $\sum_i n_i + \sum_{\{i<j\}} n_{\{ij\}} \le 2010$. Also, for $1 \le i \le 5$, $w_i = n_i + \sum_{\{j \ne i\}} n_{\{ij\}}$ is the number of questions not solved by $S_i$.

We claim that there are $1 \le x < y < z \le 5$ such that $w_i \le 1340$ and $n_{\{ij\}} \le 670$ for $i, j \in \{x, y, z\}$ and $i \ne j$.

First let us see how we can distribute the questions to $S_x$, $S_y$, $S_z$ if the claim is true. We will assign the questions one by one to one of the students $S_x$, $S_y$, $S_z$ who solved it. Let us say that we are about to assign the question $Q$. Since we have three students, $Q$ is solved by at least one of them. If there is a student who solved $Q$ and has less than 670 questions assigned to her up to this point, we assign $Q$ to her. If this is not the case, then will proceed as follows.

* If $S_x$ is the only student who solved $Q$, but she has already 670 questions assigned to her, and both $S_y$ and $S_z$ have less than 670 questions assigned to them, then we will reassign one of the questions $Q'$ from $S_x$ to $S_y$ or $S_z$, and assign $Q$ to $S_x$. If this is not possible for any $Q'$ then $n_{\{yz\}} \ge 671$, a contradiction.
* If at least one of $S_x$ and $S_y$ (say, $S_x$) solved $Q$ and each of them has already 670 questions assigned to her, then by the reasoning above we can reassign a question $Q'$ from $S_x$ to $S_y$ or $S_z$. If we cannot reassign any question from $S_x$ to $S_z$, then we will try to reassign a question $Q'$ from $S_x$ to $S_y$, and also reassign a question $Q''$ from $S_y$ to $S_z$ (and, of course, assign $Q$ to $S_x$). If this is not possible for any $Q''$ either, then $w_z \ge 1341$, a contradiction.

Now we will prove the claim. Assume that there are three students, say, $S_1, S_2, S_3$ who solved less than 670 questions each. Then $w_i \ge 1341$ for $i = 1, 2, 3$ and $3 \cdot 1341 \le w_1 + w_2 + w_3 \le 2(\sum_i n_i + \sum_{\{i<j\}} n_{\{ij\}}) \le 2 \cdot 2010$ gives a contradiction. Therefore there are at least three students with $w_i \le 1340$. Again without loss of generality let us assume that these include $S_1, S_2$ and $S_3$.
If each of $n_{\{12\}}, n_{\{23\}}, n_{\{13\}}$ is less than equal or to 670, then the claim is proven. If not, then since $w_i \le 1340$ for $1 \le i \le 3$, at most one of $n_{\{12\}}, n_{\{23\}}, n_{\{13\}}$ can be greater than 670. Let us assume that $n_{\{12\}} > 670$. Then $n_{\{23\}} < 670, n_{\{13\}} < 670$, and also $w_4 < 1340$ and $w_5 < 1340$. Applying the same reasoning to the triple $w_2, w_3, w_4$ we conclude that $n_{\{34\}} > 670$. Now we have $w_i \le 1340$ for $i = 1, 3, 5$, and $n_{\{13\}} < 670, n_{\{15\}} < 670$ and $n_{\{35\}} < 670$, and the claim is proven.