Intereting Posts

What is $\frac{x^{10} + x^8 + x^2 + 1}{x^{10} + x^6 + x^4 + 1}$ given $x^2 + x – 1 = 0$?
Question on Comaximal Ideals
Bhattacharya Distance (or A Measure of Similarity) — On Matrices with Different Dimensions
$m$ balls $n$ boxes probability problem
If a rational function is real on the unit circle, what does that say about its roots and poles?
Solving a system of equations with natural numbers?
How is Leibniz's rule for the derivative of a product related to the binomial formula?
A functional equation relating two harmonic sums.
Bergman-Shilov Boundary and Peak Points
Why rationalize the denominator?
How to compute Riemann-Stieltjes / Lebesgue(-Stieltjes) integral?
Compute $\int_{0}^{\infty}\frac{x\sin 2x}{9+x^{2}} \, dx$
Characterization of closure of set with open neighborhoods
Higher dimensional cross product
Solving $x^x=\frac{1}{\sqrt 2}$

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.

- Rigorous synthetic geometry without Hilbert axiomatics
- The Pythagorean theorem and Hilbert axioms
- Show that the angles satisfy $x+y=z$
- Why the interest in locally Euclidean spaces?
- How can we draw a line between two distant points using a finite-length ruler?
- Tangent Points for Common Tangent to Two Ellipses

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

- On some propreties of orthogonal complements
- A scalar product in the space of oriented volumes?
- which axiom(s) are behind the Pythagorean Theorem
- Prove that a straight line is the shortest distance between two points?
- What is the probability density function of pairwise distances of random points in a ball?
- To whom do we owe this construction of angles and trigonometry?
- About the ratio of the areas of a convex pentagon and the inner pentagon made by the five diagonals
- line equidistant from two sets in the plane
- Intersection of Altitudes in Hexagon
- What is the modern axiomatization of (Euclidean) plane geometry?

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.

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

- Analyzing whether there is always a prime between $n^2$ and $n^2+n$
- How does one prove that the Klein bottle cannot be embedded in $R^3$?
- Injective functions with intermediate value property are continuous. Better proof?
- If $\int f(x) \sin{x} \cos{x}\,\mathrm dx = \frac {1}{2(b^2 – a^2)} \log f(x) +c $. Find $f(x)$
- Which functions are tempered distributions?
- Number of digits from $1$ to $n$
- Finding $\lim_{n \to \infty} \frac{\sqrt{n!}}{2^n}$
- Any N dimensional manifold as a boundary of some N+1 dimensional manifold?
- Is this induction procedure correct? ($2^n<n!$)
- Can finite theory have only infinite models?
- Arithmetical Functions Sum, $\sum\limits_{d|n}\sigma(d)\phi(\frac{n}{d})$ and $\sum\limits_{d|n}\tau(d)\phi(\frac{n}{d})$
- Is $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ a context free language?
- Limit in Definition of Riemann Integral is one-sided?
- the converse of Schur lemma
- How many different groups of order $15$ there are?