Pairs $x_i+x_j$ positive for total positive sum

Let $x_1,\dots,x_n\in\mathbb{R}$ be such that $x_1+\dots+x_n>0$. At least how many sums $x_i+x_j$ ($i<j$) must be positive?

It is possible that $x_1=n$ and $x_2=\dots=x_n=-1$, in which case $n-1$ pairwise sums are positive. This should be the best as well. Can we argue something using linear algebra and basis?

• What if $n=3$ and $x_1=x_2=1$, $x_3=-1$? Then there is only one positive sum. – Guy Jul 23 '16 at 16:22
• That's true - $n=3$ is possibly a special case, because this example cannot be extended to $n\geq 4$. – pi66 Jul 23 '16 at 16:23
• Is it true that the smallest positive pair is less than the total sum for $n\geq 3$ ? – Jorge Fernández Hidalgo Jul 23 '16 at 16:57
• Ok, it isn't, but maybe it is if $x_1<x_2\dots x_n$ and $x_1+x_n\leq 0$. – Jorge Fernández Hidalgo Jul 23 '16 at 16:58
• for $n=5$ we also have $1,1,1,-1,-1$ which gives $n-2$ pairs. – Jorge Fernández Hidalgo Jul 23 '16 at 17:03

Let $f(n)$ be the minimum number of positive sums with $n$ terms.

We have $f(n)=n-2$ for $n=3,5$ and $f(n)=n-1$ otherwise.

Lemma: if $f(n)=n-1$ then $f(n+2)=(n+2)-1$

Proof: We let $x_1<x_2\dots < x_n$. If $x_1+x_{n+2}>0$ we are done.

Otherwise $x_2+x_3+\dots + x_{n+1}>0$ and so there are at least $n-1$ pairs within these number. Clearly this implies $x_{n-1}+x_{n-2}>0$.

Therefore $x_{n+1}+x_n$ and $x_{n+1}+x_{n-1}$ are also positive, and there are at least $n-1$ positive pairs. Notice that for equality to hold we must have $x_{n-3}+x_n\leq 0$ (used later).

Since $f(2)=1$ we have $f(2k)=2k-1$ for all $k$.

We have $f(3)=1$ (take $1,1,-1$).

We have $f(5)=3$ (use the lemma to see $f(5)\geq f(3)+2)$

We have $f(7)=6$, suppose not, let $x_1<x_2\dots <x_n$. By the lemma we must have $x_4+x_7\leq 0$, therefore $x_4\leq 0$ and $|x_4|\geq |x_7|$. from here $|x_1+x_2+x_3+x_4|\geq |4x_4|\geq |3x_7|\geq | x_5+x_6+x_7|\implies x_1+x_2+x_3+x_4+x_5+x_6+x_7\leq 0$.

So $f(7)=6$, we conclude $f(n)=n-1$ for $n\neq 3,5$ and $f(n)=n-2$ for $n=3,5$

When $n$ is even: In total there are $\frac{n(n-1)}{2}$ pairs.

these can be split into $(n-1)$ groups of $n/2$ pairs each, such that every number is in exactly one pair of each group.

Here is the way to do it (each color is one group):

It is clear at least one pair per group must have positive sum.