Minimizing the Number of Pairwise Sums

We solve this problem for general $n$ .

Let $A = \{ a_1, a_2, \ldots , a_n \}$ where the elements are arranged in increasing order. Observe that

$a_1 + a_1 < a_1 + a_2 < a_1 + a_3 < \ldots < a_1 + a_{n-1} < a_1 + a_n < a_2 + a_n < \ldots < a_{n-1} + a_n$

Thus, this tells us that there must be at least $2n -1$ elements in $A + A$ .

Conversely, if there are exactly $2n-1$ elements in $A + A$ , consider $a_i + a_j$ . We can similarly create a chain to demonstrate that

$a_1 + a_1 < a_1 + a_2 < \ldots < a_1 + a_j < a_2 + a_j < \ldots < a_i + a_j < a_{i+1} + a_j < \ldots < a_n + a_{j} < a_n + a_{j+1} < \ldots < a_n + a_n$

Since there are $2n+1$ terms in this sequence, it must exactly match the first sequence. We can thus conclude that:

• If $i + j \leq n + 1$ , then $a_i + a_j = a_1 + a_{i+j-1 }$ .
• If $i+j \geq n+1$ , then $a_i + a_j = a_n + a_{i+j - n}$ .

Hence, (skipping a step) we can conclude that $a_i$ is an arithmetic sequence.

I am only posting a hint for now. Show that the following two results hold:

Proposition 1: $A^*+A^*$ has $2n-1$ elements.

Proposition 2: The sorted elements of $A^*$ are in A.P.

These results can be proved easily using induction (Hint: Use induction on $n$ after sorting the set $A$ ), and left as an exercise.

From the above propositions, it follows that common difference of the A.P. is $31-13=18$ , with the first term equal to $13$ . Hence $S= 90004000$ , and $C=2n-1=19999$ . The result follows from it.