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?

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

enter image description here

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.