Team Selection Test for IMO 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^{\prime }$ from $S_x$ to $S_y$ or $S_z$, and assign $Q$ to $S_x$. If this is not possible for any $Q^{\prime }$ 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^{\prime }$ 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^{\prime }$ from $S_x$ to $S_y$, and also reassign a question $Q^{\prime \prime }$ from $S_y$ to $S_z$ (and, of course, assign $Q$ to $S_x$). If this is not possible for any $Q^{\prime \prime }$ 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.