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

Question

When I was drawing some points on paper and studied the distances between them, I found that an inequality holds for many sets of points.

Suppose that we have $2$ blue points $b_1,b_2$ and $2$ red points $r_1,r_2$ in the Euclidean plane. Then using the triangular inequality, it is easy to see that the following inequality always holds :

$$\text{the sum of Euclidean distances between points in the same color}\le\text{the sum of Euclidean distances between points in different colors},$$ i.e.

$$d(\color{blue}{b}_1,\color{blue}{b}_2)+d(\color{red}{r}_1,\color{red}{r}_2)\le d(\color{blue}{b}_1,\color{red}{r}_1)+d(\color{blue}{b}_1,\color{red}{r}_2)+d(\color{blue}{b}_2,\color{red}{r}_1)+d(\color{blue}{b}_2,\color{red}{r}_2)\tag1$$where $d(p,q)= \sqrt{(q(x)-p(x))^2 + (q(y)-p(y))^2}$ is the Euclidean distance between two points $p(p(x),p(y))$ and $q(q(x),q(y))$.

However, its generalization is difficult for me.

Question : Let $n\ge 3$. Suppose that we have $n$ blue points $b_1,b_2,\cdots,b_n$ and $n$ red points $r_1,r_2,\cdots,r_n$ in the Euclidean plane. Then, can we say that the following inequality always holds? $$\text{the sum of Euclidean distances between points in the same color}\le\text{the sum of Euclidean distances between points in different colors},$$ i.e. $$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}d(\color{blue}{b}_i,\color{blue}{b}_j)+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}d(\color{red}{r}_i,\color{red}{r}_j)\le\sum_{i=1}^{n}\sum_{j=1}^{n}d(\color{blue}{b}_i,\color{red}{r}_j)$$

So far, I have not been able to find any counterexample, so it seems that this inequality always holds. However, I've been facing difficulty even in the $n=3$ case. For the $n=3$ case, using the result of the $n=2$ case several times, we can obtain $$3\left(\sum_{i=1}^{2}\sum_{j=i+1}^{3}d(\color{blue}{b}_i,\color{blue}{b}_j)+\sum_{i=1}^{2}\sum_{j=i+1}^{3}d(\color{red}{r}_i,\color{red}{r}_j)\right)\le 4\sum_{i=1}^{3}\sum_{j=1}^{3}d(\color{blue}{b}_i,\color{red}{r}_j)\tag2$$ But this does not seem to help. Can anyone help?

Added 1 : Induction does not seem to help. As I wrote, the result of the case $n=2$ does not seem to help for the case $n=3$.

Added 2 : For the case $n=2$, I used the triangular inequality. (sorry, I didn't write the details because what I'm asking is for $n\ge 3$.) However, it seems that the triangular inequality does not help for $n\ge 3$.

Added 3 : The following is how I obtained $(2)$ from $(1)$. From $(1)$, we have $$d(\color{blue}{b}_1,\color{blue}{b}_2)+d(\color{red}{r}_1,\color{red}{r}_2)\le d(\color{blue}{b}_1,\color{red}{r}_1)+d(\color{blue}{b}_1,\color{red}{r}_2)+d(\color{blue}{b}_2,\color{red}{r}_1)+d(\color{blue}{b}_2,\color{red}{r}_2)$$

$$d(\color{blue}{b}_1,\color{blue}{b}_2)+d(\color{red}{r}_2,\color{red}{r}_3)\le d(\color{blue}{b}_1,\color{red}{r}_2)+d(\color{blue}{b}_1,\color{red}{r}_3)+d(\color{blue}{b}_2,\color{red}{r}_2)+d(\color{blue}{b}_2,\color{red}{r}_3)$$

$$d(\color{blue}{b}_1,\color{blue}{b}_2)+d(\color{red}{r}_3,\color{red}{r}_1)\le d(\color{blue}{b}_1,\color{red}{r}_3)+d(\color{blue}{b}_1,\color{red}{r}_1)+d(\color{blue}{b}_2,\color{red}{r}_3)+d(\color{blue}{b}_2,\color{red}{r}_1)$$

$$d(\color{blue}{b}_2,\color{blue}{b}_3)+d(\color{red}{r}_1,\color{red}{r}_2)\le d(\color{blue}{b}_2,\color{red}{r}_1)+d(\color{blue}{b}_2,\color{red}{r}_2)+d(\color{blue}{b}_3,\color{red}{r}_1)+d(\color{blue}{b}_3,\color{red}{r}_2)$$

$$d(\color{blue}{b}_2,\color{blue}{b}_3)+d(\color{red}{r}_2,\color{red}{r}_3)\le d(\color{blue}{b}_2,\color{red}{r}_2)+d(\color{blue}{b}_2,\color{red}{r}_3)+d(\color{blue}{b}_3,\color{red}{r}_2)+d(\color{blue}{b}_3,\color{red}{r}_3)$$

$$d(\color{blue}{b}_2,\color{blue}{b}_3)+d(\color{red}{r}_3,\color{red}{r}_1)\le d(\color{blue}{b}_2,\color{red}{r}_3)+d(\color{blue}{b}_2,\color{red}{r}_1)+d(\color{blue}{b}_3,\color{red}{r}_3)+d(\color{blue}{b}_3,\color{red}{r}_1)$$

$$d(\color{blue}{b}_3,\color{blue}{b}_1)+d(\color{red}{r}_1,\color{red}{r}_2)\le d(\color{blue}{b}_3,\color{red}{r}_1)+d(\color{blue}{b}_3,\color{red}{r}_2)+d(\color{blue}{b}_1,\color{red}{r}_1)+d(\color{blue}{b}_1,\color{red}{r}_2)$$

$$d(\color{blue}{b}_3,\color{blue}{b}_1)+d(\color{red}{r}_2,\color{red}{r}_3)\le d(\color{blue}{b}_3,\color{red}{r}_2)+d(\color{blue}{b}_3,\color{red}{r}_3)+d(\color{blue}{b}_1,\color{red}{r}_2)+d(\color{blue}{b}_1,\color{red}{r}_3)$$

$$d(\color{blue}{b}_3,\color{blue}{b}_1)+d(\color{red}{r}_3,\color{red}{r}_1)\le d(\color{blue}{b}_3,\color{red}{r}_3)+d(\color{blue}{b}_3,\color{red}{r}_1)+d(\color{blue}{b}_1,\color{red}{r}_3)+d(\color{blue}{b}_1,\color{red}{r}_1)$$

Adding these gives $(2)$. However, $(2)$ does not seem to help.

Answer 1

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.

Answer 2

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$.