On a 2017 putnam solution to a problem.

272 Views Asked by At

The problem is:

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 is exactly $7.4$.

The provided solution on the Putnam website, after defining $s_i = \sum_{j=i+1}^{i+N} a_j$, where $a_1, \dots , a_{2N}$ are the scores in increasing order and some calculations, states that

$$a_i < s_i +a_{i+N+1}-7.4N \le a_{i+N+1}$$

then it immediately concludes by saying that we can thus find $N$ scores that sum to $7.4N$ by taking $a_i, \dots, a_{i+1+N}$ and subtracting the value $s_i +a_{i+N+1}-7.4N $,am I getting this right?

I don't understand why this would work given the equality above. Also how can we be sure that $s_i +a_{i+N+1}-7.4N$ is a score value that we can subtract out? there must be something I am not understanding.

2

There are 2 best solutions below

0
On BEST ANSWER

The solution is quite specific about the $i$ that you choose in order to make the inequalities hold: it is the largest such that $s_i\leq 7.4N$. let us call $A$ the set $\{a_i,\dots,a_{i+N+1}\}$ So if $s_i=7.4N$, $s_i-7.4N+a_{i+N+1}=a_{i+N+1}$, so obviously you can remove $a_{i+N+1}$ from $A$ and obtained the desired set. If instead $s_i<7.4N$, you know that $s_i+a_{i+N+1}>s_{i+1}>7.4N$ by the choice of $i$, and you are sure that $7.4N$ is an integer because $7.4=37/5$, and since $7.4\cdot 2N$ is an integer you know that $5|N$. So $s_i-7.4N+a_{i+N+1}$ is an integer and it is obviously less than $10$ and larger than $a_i$. But then, by the hypothesis that every value is taken, you can find in $A$ the corresponding element and remove it.

1
On

I think you have omitted some key steps from the solution in the web site.

First it said $i$ is the largest index for which $s_i \le 7.4N$

$\implies s_{i+1} > 7.4N \implies s_{i+1} - s_i > 7.4N - s_i \implies a_{i+N+1} - a_i > 7.4N - s_i$

From this we get $a_i < a_{i+N+1} + s_i - 7.4N \le a_{i+N+1}$ ... (1)

Now since $14.8N$ is an integer, $5 | N$. Therefore $7.4N$ is an integer.

(1) now implies that $a_{i+N+1} + s_i - 7.4N$ is an integer.

Now consider the sum $a_i + ... a_{i+N+1}$ and subtract $a_{i+N+1} + s_i - 7.4N$.

You will get the sum of some $N$ numbers to be $7.4N.