An inequality about the sum of distances between points : same color $\le$ different colors?

Solution 1:

Given $2n$ points ($B=(b_1,\dots, b_n)$ and $R=(r_1,\dots,r_n)$) by $f$ we denote the difference between the right-hand and the left-hand sides of the required inequality (1). We’ll prove that $f$ is always non-negative.

We start from one-dimensional case (which is also a still unanswered MSE question). Without loss of generality we may assume that all points belong to the segment $[-1,1]$ and some two of the points are endpoints of the segment. Then $f$ is a continuous function on a compact set, so the family of the admissible sets $B$ and $R$ on which the minimum is attained is non-empty. Take such sets $B$ and $R$ with the smallest number of different coordinates of points. We claim that this number is two. Indeed, assume that there is a group of points which are placed in one point strictly between the endpoints of the segment. When we synchronically move the group in its small convex neighborhood containing no other points of the sets $R$ and $D$, the value of $f$ changes linearly. Thus we can move the group to a side of a non-increasity of $f$ until it reach an other group of points and then merge the groups, which contradicts the minimality of the group number of the chosen sets $B$ and $R$. So we can assume that $r$ red points and $b$ points are placed at $-1$ and $n-r$ red points and $n-b$ points are placed at $1$. Then $$f=2r(n-b)+2b(n-r)-2r(n-r)+2b(n-b)=2(r-b)^2\ge 0.$$

Now we consider two-dimensional case. Let $\ell$ be a straight line making an angle $\alpha$ with $Ox$ axis. Orthogonally projecting the configuration of the points and segments between each two of them, and applying to the projected configuration one-dimensional case of the inequality, we obtain an inequality of the form

$$\sum_{x,y\in B\cup R} \varepsilon(x,y) d(x,y)|\cos(\varphi (x,y)-\alpha)|\ge 0,$$

where $\varepsilon(x,y)$ equals $1$ provided the points $x$ and $y$ have different colors and equals $-1$ otherwise, and $\varphi(x,y)$ is an angle between the $Ox$ axis and the segment $[x,y]$ (if $x=y$ then we put $\varphi(x,y)=0$). When we integrate this inequality over $\alpha\in [0,2\pi]$, all integrals $\int_{0}^{2\pi} |\cos (\varphi(x,y)-\alpha)|d\alpha$ yield the same non-zero constant so we obtain the required inequality (1).

The inequality for general $d$-dimensional case should be proved similarly, with the $(d-1)$-dimensinal sphere of line $\ell$ directions instead of one-dimensional circle of the angles $\alpha$.

Solution 2:

Consider all your $2n$ points, blue and red, as point charges, each of them having a charge $q_k=\pm1$ and sitting at position $\vec{x}_k$, blue points having charge $+1$ and red points $-1$. Your problem amounts at proving that the following "potential energy" $U$ is always non negative: $$ U(\vec{x}_1,\ldots,\vec{x}_{2n})=-\sum_{\stackrel{\scriptstyle i,j}{i<j}} q_iq_j|\vec{x}_i-\vec{x}_j|. $$ The force derived from such potential is peculiar: two points of the same colour repel each other with unit force directed along the straight line joining them, while points of different colour attract each other in the same way, irrespective of their distance.

Potential energy has a minimum when the total force $\vec{F}_{tot}$ vanishes. The only way to arrange our charges so that $\vec{F}_{tot}=0$ is when every blue point is coupled with a red point, both sharing the same position. But then $U=0$, so that is the minimum of the potential energy.

I don't know if all this can be turned into a rigorous proof, but I hope this approach may give some further insight.

Solution 3:

$\def\RR{\mathbb{R}}$This answer contains basically the same proof as Alex Ravsky's answer, namely:

1. Prove the proposition in the one-dimensional case.
2. Show that a counter-example in the $d$-dimensional case can be reduced to one in the 1-dimensional case.

The reason this is a new answer is that (a) my proof of the first point is a bit different, and (b) I wanted to highlight that the second part is an application of a cool and really general "dimension reduction" result in linear algebra.

Here's what we want to prove:

Proposition 1. If $r_1,\ldots,r_n,b_1,\ldots,b_n\in\RR^d$ then $A\le B$ where $A$ is the total monochromatic distance, and $B$ is the total bichromatic distance.

Below are the main two ingredients. Proposition 3 is the general linear algebra result I wanted to highlight.

Proposition 2. Proposition 1 holds when $d=1$.

Proposition 3. If $x_1,\ldots,x_k\in\RR^d$, $w_1,\ldots,w_k\in\RR$ and $\sum_i w_i|x_i|=0$ then there exists a unitary linear projection $\pi:\RR^d\to\RR$ such that $\sum_i w_i|\pi(x_i)|=0$.

Remark. A unitary linear projection is just a map $\pi:x\mapsto x\cdot u$ for some fixed unit vector $u\in\RR^d$.

Proof of Proposition 1. Suppose the proposition is false, and select a counter-example. Defining the multi-sets $X=\{r_i-r_j:i<j\}\cup\{b_i-b_j:i<j\}$ and $Y=\{r_i-b_j\}$, then $\sum_{x\in X}|x|=A>B=\sum_{y\in Y}|y|$.

Let $\lambda=B/A$, then $\sum_{x\in X}|\lambda x|-\sum_{y\in Y}|y|=0$. By Proposition 3, there is a unitary linear projection $\pi:\RR^d\to\RR$ such that $\sum_{x\in X}|\lambda\pi(x)|-\sum_{y\in Y}|\pi(y)|=0$, hence $\sum_{x\in X}|\pi(x)|>\sum_{y\in Y}|\pi(y)|$. We deduce that $\pi(r_1),\ldots,\pi(r_n),\pi(b_1),\ldots,\pi(b_n)\in\RR$ is a counter-example to Proposition 2, which cannot happen. $\square$

Proof of Proposition 2. We shall proceed by induction on $n$. Clearly the result holds for $n\le1$. Without loss of generality the points are sorted, so that $r_1\le r_2\le\ldots\le r_n$ and $b_1\le b_2\le\ldots\le b_n$, and again without loss of generality $r_1\le b_1$. Let $m\ge1$ be the number of red points less than or equal to $b_1$.

From left-to-right on $\RR$ we have some red points $r_1,\ldots,r_m$, then $b_1$, then the other red and blue points. In particular, $r_m$ and $b_1$ appear consecutively in that order.

Now $$A-B = \sum_{i<j}|r_i-r_j|+\sum_{i<j}|b_i-b_j|-\sum_{i,j}|r_i-b_j|$$ which we decompose as $$A-B = C + \sum_{i<m}|r_i-r_m| + \sum_{m<j}|r_m-r_j| + \sum_{1<j}|b_1-b_j| \\-\sum_{i<m}|r_i-b_1|-\sum_{m<i}|r_i-b_1|-\sum_{1<j}|r_m-b_j|-|r_m-b_1|$$ where $C$ is the contribution of the terms involving neither $r_m$ not $b_1$. Defining $h=b_1-r_m\ge0$, we group the sums ranging over the same values giving $$A-B = C + \sum_{i<m}(|r_i-r_m|-|r_i-b_1|) + \sum_{m<j}(|r_m-r_j|-|r_j-b_1|) \\+ \sum_{1<j}(|b_1-b_j|-|r_m-b_j|) - |r_m-b_1|$$ $$ = C + (m-1)(-h) + (n-m)(h) + (n-1)(-h) - h$$ $$ = C + (1-2m)h.$$

By induction, $C\le0$. And $m\ge1$ so $1-2m<0$ so $(1-2m)h\le0$. Hence $A-B\le0$. $\square$

Remark. In fact, this further proves that we have equality $A=B$ if and only if $r_i=b_i$ for all $i$ (because $A=B$ requires $h=0$ and $C=0$).

Proof of Proposition 3. If $S\subset\RR^d$ is the unit sphere, we are looking for some $u\in S$ so that $\sum_i w_i|x_i\cdot u|=0$.

Integrating, $$I := \int_S \sum_i w_i|x_i\cdot u| du = \sum_i w_i |x_i| \int_S |\hat x_i \cdot s| du$$ where $\hat x_i = x_i/|x_i| \in S$. By rotational symmetry, the latter integral does not depend on $\hat x_i \in S$ and therefore is some constant $D_n>0$ depending only on $n$.

We deduce $I = D_n \sum_i w_i|x_i| = 0$. Since the integral $I$ is zero and its integrand is continuous in $u$, we deduce that the integrand $\sum_i w_i|x_i\cdot u|$ attains the value $0$ for some $s\in S$. $\square$