Suppose, one hundred real numbers are given and their sum is 0.Then how can I prove that at least 99 of the pairwise sums of these hundred numbers are non-negative?

I tried this: Let the real numbers be $a_i$,$1\leq i\leq100$. By the given condition, $a_1+a_2+\dots +a_{100}=0$.Suppose for the sake of contradiction, that at most 98 of the pairwise sums of these given reals are non-negative.I just tried to examine the case when exactly 98 of them are non-negative. I labelled the sums $S_1$,$S_2,\dots S_{4950}$,WLOG assume that sums $S_1,S_2,\dots S_{4852}$ are negative, the rest are non-negative. $$S_1+S_2+\dots +S_{4950}=99(\sum_{i=1}^na_i)=0$$ Case I: $S_{4853}+a_{4854}+\dots +a_{4950}=0$.That simply means that $S_1+S_2+\dots +S_{4852}=0$.But, by the given condition, $S_1+S_2+\dots +S_{4852}<0$,a contradiction.After that, I am not able to make any progress.

Can anyone please suggest a more efficient method to solve this problem.I feel this approach will involve enormous case work.

  • 2
    $\begingroup$ More of a sketch than a proof, but consider the largest element. The pairwise sum of this with the others will yield 99 positive sums, unless there is an element even more negative than the maximum is positive. But if this is the case, then the average of the other 98 will be positive, so there will be more positive sums there. $\endgroup$ – Mario Carneiro Dec 13 '12 at 8:00

Without loss of generality, $a_1\ge a_2\ge \ldots\ge a_{100}$. From $$0=(a_1+\ldots+a_{50})+(a_{51}+\ldots+a_{100})\le 50a_1+50a_{51},$$ we conclude $a_1+a_{51}\ge0$, hence we have $50$ nonnegative sums $$\tag1 a_1+a_k,\ 2\le k\le 51$$ involving $a_1$. We may assume that $a_1+a_{100}<0$ as otherwise $(1)$ can be extended to $2\le k\le 100$ and we are done. Therefore $a_2+\ldots+a_{99}=-(a_1+a_{100})>0$ and from $$0< (a_2+\ldots+a_{50})+(a_{51}+\ldots a_{99})\le 49a_2+49a_{51},$$ we conclude $a_2+a_{51}> 0$, hence we have another $49$ nonnegative (in fact positive) sums $$\tag2a_2+a_k,\ 3\le k\le 51$$ and together with $(1)$ this produces the required $99$ nonnegative sums.

Warning: Contrary to what it may look like, this method will not guarantee us $50+49+48+\ldots$ nonnegative sums as the first step from $(1)$ to $(2)$ comes into play only if $a_1+a_{100}<0$. In fact, $a_1=99, a_2=\ldots=a_{100}=-1$ shows that $99$ cannot be improved.


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.