Putnam 2017, Problem A-4

A class with \( 2N \) students took a quiz, on which the possible scores were \( 0, 1, \ldots, 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 \).

Solution:
### First solution
Let \( a_1, \ldots, a_{2N} \) be the scores in nondecreasing order, and define the sums \( s_i = \sum_{j=i+1}^{i+N} a_j \) for \( i = 0, \ldots, N \). Then \( s_0 \leq \cdots \leq s_N \) and \( s_0 + s_N = \sum_{j=1}^{2N} a_j = 7.4(2N) \), so \( s_0 \leq 7.4N \leq s_N \). Let \( i \) be the largest index for which \( s_i \leq 7.4N \); note that we cannot have \( i = N \), as otherwise \( s_0 = s_N = 7.4N \) and hence \( a_1 = \cdots = a_{2N} = 7.4 \), contradiction. Then \( 7.4N - s_i < s_{i+1} - s_i = a_{i+N+1} - a_{i+1} \) and so  
\[
a_i < s_i + a_{i+N+1} - 7.4N \leq a_{i+N+1};
\]  
since all possible scores occur, this means that we can find \( N \) scores with sum \( 7.4N \) by taking \( a_{i+1}, \ldots, a_{i+N+1} \) and omitting one occurrence of the value \( s_i + a_{i+N+1} - 7.4N \).  

### Remark
David Savitt (via Art of Problem Solving) points out that a similar argument applies provided that there are an even number of students, the total score is even, and the achieved scores form a block of consecutive integers.  

### Second solution
We first claim that for any integer \( m \) with \( 15 \leq m \leq 40 \), we can find five distinct elements of the set \( \{1, 2, \ldots, 10\} \) whose sum is \( m \). Indeed, for \( 0 \leq k \leq 4 \) and \( 1 \leq \ell \leq 6 \), we have  
\[
\left( \sum_{j=1}^k j \right) + (k + \ell) + \left( \sum_{j=k+7}^{10} j \right) = 34 - 5k + \ell,
\]  
and for fixed \( k \) this takes all values from \( 35 - 5k \) to \( 40 - 5k \) inclusive; then as \( k \) ranges from \( 0 \) to \( 4 \), this takes all values from \( 15 \) to \( 40 \) inclusive.  

Now suppose that the scores are \( a_1, \ldots, a_{2N} \), where we order the scores so that \( a_k = k \) for \( k \leq 10 \) and the subsequence \( a_{11}, a_{12}, \ldots, a_{2N} \) is nondecreasing. For \( 1 \leq k \leq N - 4 \), define \( S_k = \sum_{j=k+4}^{k+N} a_j \). Note that for each \( k \), \( S_{k+1} - S_k = a_{k+N+5} - a_{k+10} \) and so \( 0 \leq S_{k+1} - S_k \leq 10 \). Thus \( S_1, \ldots, S_{N-4} \) is a nondecreasing sequence of integers where each term is at most \( 10 \) more than the previous one. On the other hand, we have  
\[
S_1 + S_{N-4} = \sum_{j=11}^{2N} a_j = (7.4)(2N) - \sum_{j=1}^{10} a_j = (7.4)(2N) - 55,
\]  
whence \( S_1 \leq 7.4N - 27.5 \leq S_{N-4} \). It follows that there is some \( k \) such that \( S_k \in [7.4N - 40, 7.4N - 15] \), since this interval has length \( 25 \) and \( 7.4N - 27.5 \) lies inside it.  

For this value of \( k \), note that both \( S_k \) and \( 7.4N \) are integers (the latter since the sum of all scores in the class is the integer \( (7.4)(2N) \) and so \( N \) must be divisible by \( 5 \)). Thus there is an integer \( m \) with \( 15 \leq m \leq 40 \) for which \( S_k = 7.4N - m \). By our first claim, we can choose five scores from \( a_1, \ldots, a_{10} \) whose sum is \( m \). When we add these to the sum of the \( N - 5 \) scores \( a_{k+10}, \ldots, a_{k+N+4} \), we get precisely \( 7.4N \). We have now found \( N \) scores whose sum is \( 7.4N \) and thus whose average is \( 7.4 \).  

### Third solution
It will suffice to show that given any partition of the students into two groups of \( N \), if the sums are not equal we can bring them closer together by swapping one pair of students between the two groups. To state this symbolically, let \( S \) be the set of students and, for any subset \( T \) of \( S \), let \( \Sigma T \) denote the sum of the scores of the students in \( T \); we then show that if \( S = A \cup B \) is a partition into two \( N \)-element sets with \( \Sigma A > \Sigma B \), then there exist students \( a \in A, B \in B \) such that the sets  
\[
A' = A \setminus \{a\} \cup \{b\}, \quad B' = A \setminus \{b\} \cup \{a\}
\]  
satisfy  
\[
0 \leq \Sigma A' - \Sigma B' < \Sigma A - \Sigma B.
\]  

In fact, this argument will apply at the same level of generality as in the remark following the first solution. To prove the claim, let \( a_1, \ldots, a_n \) be the scores in \( A \) and let \( b_1, \ldots, b_n \) be the scores in \( B \) (in any order). Since \( \Sigma A - \Sigma B \equiv \Sigma S \pmod{2} \) and the latter is even, we must have \( \Sigma A - \Sigma B \geq 2 \). In particular, there must exist indices \( i, j \in \{1, \ldots, n\} \) such that \( a_i > b_j \). Consequently, if we sort the sequence \( a_1, \ldots, a_n, b_1, \ldots, b_n \) into nondecreasing order, it must be the case that some term \( b_j \) is followed by some term \( a_i \). Moreover, since the achieved scores form a range of consecutive integers, we must in fact have \( a_i = b_j + 1 \). Consequently, if we take \( a = a_i \), \( b = b_j \), we then have \( \Sigma A' - \Sigma B' = \Sigma A - \Sigma B - 2 \), which proves the claim.