5

Let $a_1, a_2,..., a_{2n}\in \mathbb {R} $ s.t. $a_1+a_2+...+a_{2n}=0$. Show that there exists $2n-1$ pairs $(a_i, a_j)$ s.t. $a_i+a_j\geq 0$.

My idea: I consider that $a_1,..., a_k\geq 0$ and $a_{k+1},..., a_{2n}<0$(I put them the sign minus).

Then there are $\frac {k (k-1)}{2} $ pairs. Also $a_1+...a_k=a_{k+1}+...+a_{2n} $. But I am stuck.

Problemsolving
  • 2,067

1 Answers1

3

Motivation: There are $$ \binom{2n}{2} = (2n-1)n $$ pairs $(a_i, a_j)$ with $1 \le i < j \le 2n$. One can arrange the corresponding sums $a_i + a_j$ in $2n-1$ rows with $n$ entries in per row, so that in each row the entries add up to $a_1 + \ldots + a_{2n} = 0$.

Then every row must have at least one non-negative entry, that makes $2n-1$ sums $a_i + a_j \ge 0$, and the statement is proved.

Examples:

$n=2$: $$ \begin{array}{ccc} a_1 + a_2 & & a_3+a_4 \\ a_1 + a_3 & a_2 + a_4 \\ a_1 + a_4 & a_2 + a_3 \end{array} $$

$n=3$: $$ \begin{array}{ccccc} a_1 + a_2 & & a_3 + a_4 & & a_5 + a_6 \\ a_1 + a_3 & a_2 + a_5 & & a_4 + a_6 \\ a_1 + a_4 & a_2 + a_6 & a_3 + a_5 \\ a_1 + a_5 & a_2 + a_4 & a_3 + a_6 \\ a_1 + a_6 & a_2 + a_3 & & a_4 + a_5 \end{array} $$

Proof of the general case: (With the great help of Batominovski!)

Consider the complete graph $K_{2n}$ with vertices $1, \ldots, 2n$. According to Wikipedia: Graph factorization, it has a “1-factorization”, i.e. the edges can be partitioned into disjoint “1-factors” or “perfect matchings.”

Each perfect matching consists of $n$ edges without common vertices $$ (i_1, j_1), (i_2, j_2), \ldots , (i_n, j_n) $$ and since the sum of all $a_k$ is zero, there must be (at least) one vertex $(i_k, j_k)$ such that $a_{i_k} + a_{j_k} \ge 0$.

The total number of edges in $K_{2n}$ is $\binom{2n}{2} = (2n-1)n$, so that the factorization consists of $2n-1$ perfect matches, and we have indeed $2n-1$ distinct vertices $(i_k, j_k)$ with $a_{i_k} + a_{j_k} \ge 0$.

Martin R
  • 113,040
  • 1
    Your observation is point on. First, remove $n$ independent edges (i.e., no two removed edges share a common vertex) from the complete graph $K_{2n}$ on ${1,2,\ldots,2n}$. Call the resulting graph $G_1$, and let $P$ denote the set of removed edges. Then, $G_1$ is Eulerian, and we can remove a $(2n)$-cycle $C_1$ from $G_1$, resulting in $G_2$. Continue to do this until you decompose $K_{2n}$ as a disjoint union of $C_1$, $C_2$, $\ldots$, $C_{n-1}$, and $P$. Each $C_i$ can be decomposed into two disjoint perfect pairings $P_i^1$ and $P_i^2$. – Batominovski Oct 18 '19 at 21:55
  • 1
    Then, if $\big{{i_1,j_1},{i_2,j_2},\ldots,{i_n,j_n}\big}$ is a perfect pairing on $K_{2n}$, then you have a $$\left{a_{i_1}+a_{j_1},a_{i_2}+a_{j_2},\ldots,a_{i_n}+a_{j_n}\right},.$$ The proof is now finished. – Batominovski Oct 18 '19 at 21:57
  • 1
    @Batominovski: Unfortunately, graph theory is not my area of expertise :) – I suggest that you post an answer. – Martin R Oct 18 '19 at 21:58
  • 1
    Maybe tomorrow, I am going to bed. But if you want to cooperate my idea into your answer to make it complete, then that'd be great. So I don't have to type it up myself. Plus, the proof is pretty much your idea. – Batominovski Oct 18 '19 at 22:03
  • 1
    @Batominovski: I have tried to incorporate your information into the answer. Any feedback is welcome. – Martin R Oct 18 '19 at 23:09
  • This looks great! Thank you for a complete answer. – Batominovski Oct 19 '19 at 04:17