Q:

A class with $2N$ students took a quiz, on which the possible scores were $0,1,\dots,10$. Each of these scores occurred at least once, and the average score was exactly $7.4$. Show that the class can be divided into two groups of $N$ students in such a way that the average score for each group was exactly $7.4$.

A:

We can always form two groups of $N$ students, and if the average is $7.4$ for all $2N$, that means that if we don’t have an average of $7.4$ for each group, then one group has a higher average and another group has a smaller average. This can be reformulated to say that one group has a higher total sum (big group) and another group has a lower total sum (small group), and that if the total sum of scores from each group is equal, they will have the same average. If we swap two students, one from each group, we change the sums of each group, and (possibly) get closer to the average. Specifically, because we deal with integers, if we can decrease the sum of the big group by one at a time and increase the sum of the small group by one at a time, we should be able to walk through all values and attain a value where both groups have the same sum.

Claim:

Given a big group, and a small group, we can always make a swap of one score from the big group and one score from the small group, such that the two scores differ by one (and therefore decreases the big sum by $1$ and increases the small sum by $1$).

Proof 1 (by JZ):

The big group is nonempty, and so it contains a maximum score $X$. Because all possible scores are in at least one of the two groups, $X-1$ is in either the big group or the small group. If it is in the small group, then we are done. If it is in the big group, then consider $X-2$. By the same logic, either the small group contains $X-2$, or it is also in the big group. By induction, the big group must contain all the scores from $0$ to $X$ for the small group to not contain any of those, but that means the small group, which is nonempty, must only contain elements larger than $X$, the max of the large group. This cannot be true, as it would imply the small group has a larger total sum. Thus at some point the small group must have contained an element one less than an element in the large group.

Proof 2 (by Franklin):

Consider taking a big score, $B$, from the big group and a small score, $S$, from the small group. We know this must be true because if the average of the big group is higher, it must have one element that is higher than at least one element in the small group. If $B = S + 1$, then we are done. If not, then there is some element $T$ that is greater than $S$ and less than $B$ that is in at least one group, due to the fact that all of $0, \dots, 10$ scores were attained on the test and $B$ and $S$ are more than $1$ apart. If $T$ is in the big group, just set $B = T$, and if $T$ is in the small group, then set $S = T$, and use the same argument. Because $T$ is strictly between $S$ and $B$, and we deal with integers, eventually, $B = S + 1$ will be satisfied.

With this claim proven, the proof is obvious.