Given 100 real numbers, their sum is zero. How many pairs can be chosen from them at least, in which the sum of the numbers is non-negative?
I. solution. None of the 100 real numbers can be negative, because then their sum would also be negative, not 0. If 99 of the 100 real numbers are negative, then the 100th number must definitely be positive, since only then can the sum of the numbers be 0. In this case, among the two-term sums, there are exactly 99 positive ones, specifically those where one of the terms is the positive number.

In the following, we will show that by varying the number of negative numbers among the 100 numbers, we cannot get fewer than 99 non-negative two-term sums.

If among the 100 numbers there are $k$ non-negative numbers, then from their pairwise sums, $\frac{k(k-1)}{2}$ (necessarily non-negative) sums result. If $k \geq 15\left(k \in \mathbb{N}^{+}\right)$, then this number is at least $\frac{15 \cdot 14}{2}=105>99$. Thus, it is sufficient to consider the case $k \leq 14$.

Let the non-negative numbers be denoted by $n_{1}, n_{2}, \ldots, n_{k}$, and the negative numbers by $m_{1}, m_{2}, \ldots, m_{100-k}$; since $k \leq 14$, there are fewer non-negative numbers than negative ones. We arrange those two-term sums that consist of one non-negative and one negative number in a $k \times (100-k)$ table as follows:

$$
\begin{array}{cccc}
n_{1}+m_{1} & n_{1}+m_{2} & \ldots & n_{1}+m_{100-k} \\
n_{2}+m_{2} & n_{2}+m_{3} & \ldots & n_{2}+m_{1} \\
\vdots & \vdots & & \\
n_{k}+m_{k} & n_{k}+m_{k+1} & \ldots & n_{k}+m_{k-1}
\end{array}
$$

If we add the two-term sums in the same column, we get the sum of a non-negative and a part of the negative numbers. The sum in each column is positive, since the sum of the 100 numbers is 0, and by omitting $100-2k$ negative terms, the remaining sum is positive. Thus, there is at least one positive two-term sum in each column, and therefore we have at least

$$
\frac{k(k-1)}{2}+100-k=\frac{(k-1.5)^{2}+197.75}{2}
$$

non-negative sums. For $0 \leq k \leq 100, k \in \mathbb{N}$, the expression takes its minimum value when $k=1$ or $k=2$, and in both cases, the minimum value is 99.

Thus, at least 99 pairs can be chosen from the 100 numbers such that the sum of the numbers in the pair is non-negative.

In the following, we provide several proofs that the number of pairs with a non-negative sum is at least 99.

II. solution. Let the 100 numbers be denoted by $A_{0}, A_{1}, \ldots, A_{99}$. We can pair them in 99 different ways, each pair being different in each pairing. If we add the sums of the numbers in each pair in a given pairing, we get 0, so there is definitely a pair in this pairing where the sum of the numbers is non-negative. Thus, in each of the 99 pairings, there is such a pair, and since every pair is different, there are at least 99 such pairs.

In the following, we provide a construction for 99 different pairings where each pair appears only once.

![](https://cdn.mathpix.com/cropped/2024_05_02_547d8747df5c6b43b777g-1.jpg?height=176&width=816&top_left_y=1755&top_left_x=644)

The first pairing is shown in the figure, where the numbers in the same column belong to a pair. The next pairing is obtained by shifting each number along the arrows by one position. Each subsequent pairing is obtained in the same way from the previous one. It is clear that $A_{0}$ will have a different pair in each of the 99 pairings $\left(A_{1}, A_{99}, A_{98}, A_{97}, \ldots, A_{4}, A_{3}, \text{finally } A_{2}\right)$. This is also true for $A_{1}$, whose pairs are: $\left(A_{0}, A_{98}, A_{96}, \ldots, A_{4}, A_{2}, A_{99}, A_{97}, A_{95}, \ldots, A_{5}, A_{3}\right)$; and it would also be true if a different element started from the $A_{1}$ position. Since the pairings repeat every 99 cycles, it does not matter which pairing we consider first. Thus, any element can start from the $A_{1}$ position. Therefore, every element will have a different pair in each of the 99 pairings.

Thus, at least 99 pairs can be chosen such that the sum of the numbers in the pair is non-negative.

Remark. Some referred to an article in the 2006/9 issue of KöMaL when constructing the 99 different pairings. (The problem was also published in the same issue.)

III. solution. Let $a_{1}, a_{2}, \ldots, a_{100}$ be the 100 given numbers in a certain order such that $a_{1} \geq a_{2} \geq a_{3} \geq \ldots \geq a_{100}$.

Consider the following sums: $a_{1}+a_{100}, a_{2}+a_{99}, \ldots, a_{i}+a_{101-i}, \ldots, a_{50}+a_{51}$. The sum of these 50 two-term sums is the sum of all the numbers, which is 0. Therefore, among these two-term sums, there is a non-negative one. Let $a_{x}+a_{101-x}$ $(x \in\{1,2, \ldots, 50\})$ be such a sum.[^0]

The two-term sums where one term has an index of at most $x$ and the other term has an index of at most $101-x$ are greater than or equal to $a_{x}+a_{101-x}$. Thus, these sums are also non-negative. Let's count these pairs. The first term can be chosen in $x$ ways, and the second term in $(101-x)$ ways. We do not need to count the pairs where the same number is chosen twice, and since otherwise we would count them twice, we need to subtract the number of pairs where both terms have an index of at most $x$. The number of such pairs is therefore

$$
x(101-x)-x-\frac{x^{2}-x}{2}=x\left(100+\frac{1}{2}-\frac{3}{2} x\right) .
$$

The value of this expression is 99 when $x=1$, and for $x \geq 2$, it is at least 100 because $100+\frac{1}{2}-\frac{3}{2} x \geq 50$. Therefore, the number of pairs with a non-negative sum is at least 99.


[^0]:    ${ }^{1}$ Kiss György: How to organize a round-robin football tournament? KöMaL, 2006/9., 514-525.