Problem 1600

To prove that there exist at least $n-1$ two-element subsets of an $n$-element set of real numbers, where $n \geq 6$, such that the arithmetic mean of the elements in each subset is not less than the arithmetic mean of the elements in the whole set, we will consider two cases: when $n$ is even and when $n$ is odd.

1. **Case 1: $n$ is even**

Let the numbers in the set $S$ be $a_1 \le a_2 \le \dots \le a_n$, and let $a = \frac{1}{n} \sum_{i=1}^n a_i$ be the arithmetic mean of the elements in $S$.

Lemma: The set $S$ can be partitioned into $\frac{n}{2}$ disjoint pairs in $n-1$ unique ways. This is a known result from graph theory that $K_{2n}$ (the complete graph on $2n$ vertices) has $2n-1$ edge-disjoint perfect matchings.

Proof:
- Remove $a_n$ from $S$ and let $P_i = \{(a_{i-1}, a_{i+1}), (a_{i-2}, a_{i+2}), \ldots, (a_{i-\frac{n-2}{2}}, a_{i+\frac{n-2}{2}})\}$, where operations are done modulo $n-1$.
- The sets $P_i \cup \{(a_i, a_n)\}$ for $i = 1, 2, \ldots, n-1$ are $n-1$ disjoint partitions of $S$.

For any $P_i$, the union of its elements is $S$ and no pair occurs in two different sets $P_i$. It follows that there is at least one unique pair in each $P_i$ whose arithmetic mean is not less than the mean of all pairs in $P_i$, which is also equal to the mean of $S$. So the claim is true for even $n$.

2. **Case 2: $n$ is odd**

Consider the largest element that is not larger than the mean, $a_m \le a$. If $\frac{a_n + a_m}{2} < a$, then $a_n - a < a - a_m$. Hence, there are at least as many elements $a_i$ above the mean as there are below the mean. Therefore, there are at least $\lceil \frac{n}{2} \rceil$ elements greater than $a$, and any two of them will have an average greater than $a$.

Since $\binom{\lceil \frac{n}{2} \rceil}{2} \ge n-1$ when $n$ is odd and $n \ge 7$, we are done. So we can assume $\frac{a_n + a_m}{2} \ge a$. This gives one pair (1).

Now consider $S \setminus \{a_m\}$. Since $a_m \le a$, the mean of $S \setminus \{a_m\}$ is not less than the mean of $S$. Furthermore, since $|S \setminus \{a_m\}|$ is even, from the previous case, we can find $n-2$ pairs greater than the mean. Clearly, these won't contain $a_m$, so we have $n-1$ distinct pairs. This completes the proof.

$\blacksquare$