Find the smallest positive number $\lambda$, such that for any $12$ points on the plane $P_1,P_2,\ldots,P_{12}$(can overlap), if the distance between any two of them does not exceed $1$, then $\sum_{1\le i<j\le 12} |P_iP_j|^2\le \lambda$.
Problem
Source: China Team Selection Test 2016 Test 2 Day 1 Q2
Tags: geometry, inequalities, geometric inequality
20.03.2016 21:43
The answer is 48, achieved with 4 points each at the vertices of an equilateral triangle. To prove this is indeed an upper bound, we first assume that the points are in convex position: no point can lie on the segment between two distinct other points, or in the interior of any triangle formed by three other points. This is without loss because by moving $P_i$ along any line segment $l$, the maximum of $\sum_{j \neq i} |P_i P_j|^2$ is achieved at an endpoint of $l$. And as long as we do not move $P_i$ out of the convex hull of the other points, the distance between any pair of points is still bounded by 1. Now let us pick three distinct points $A, B, C$ among the $P_i$ to maximize $AB^2 + BC^2 + CA^2$. Let $D$ be any one of the remaining 9 points. We claim that $DA^2 + DB^2 + DC^2 \leq 2$. Without loss assume $D$ and $C$ lies on opposite sides of $AB$, so that we have a convex quadrilateral $DACB$. If $\angle D \geq 90^{\circ}$ then $DA^2 + DB^2 \leq AB^2 \leq 1$, and the claim follows since $DC^2 \leq 1$ as well. If $\angle A \geq 90^{\circ}$, we note by the choice of $A, B, C$ that $DB^2 + DC^2 + BC^2 \leq AB^2 + AC^2 + BC^2$. Thus $DB^2 + DC^2 + DA^2 \leq AB^2 + AC^2 + AD^2 \leq AB^2 + CD^2 \leq 2$. Similar argument shows that the claim also holds if $\angle B \geq 90^{\circ}$ or $\angle C \geq 90^{\circ}$. But one of the angles $\angle A, \angle B, \angle C, \angle D$ must be at least $90^{\circ}$, so the claim always holds. Without loss assume $A, B, C = P_{10}, P_{11}, P_{12}$, then from the claim we have $$\sum_{1 \leq i < j \leq 12} |P_i P_j|^2 = AB^2 + BC^2 + CA^2 + \sum_{1\leq i \leq 9} (|P_iA|^2 + |P_iB|^2 + |P_iC|^2) + \sum_{1 \leq i < j \leq 9} |P_i P_j|^2 \leq 3 +18 + \sum_{1 \leq i < j \leq 9} |P_i P_j|^2.$$So it suffices to show $\sum_{1 \leq i < j \leq 9} |P_i P_j|^2 \leq 27$. But this is essentially the same problem, only with less number of points, so an induction argument completes the proof.
18.02.2017 14:21
The answer is $\lambda=48$, an equality case being $4$ points at each vertex of an equilateral triangle (troll). Let $O$ be an arbitrary point, then with $a_i=\overrightarrow{OP_i}$ we have \[ \sigma:=\sum_{1\le i<j\le 12}|P_iP_j|^2=\sum (a_i-a_j)^2=12\sum a_i^2-(a_1+\dots+a_{12})^2\le 12\sum a_i^2. \]By the Universal Covering Problem, we can cover $\{P_1,\dots,P_{12}\}$ with a circle of radius $\frac1{\sqrt{3}}$; choosing $O$ to be the center of this circle gives $a_i^2\le \frac13$ and thus $\sigma\le 48$. $\blacksquare$ Since I didn't find the original paper proving that a regular hexagon inscribed in a circle of radius $\frac1{\sqrt{3}}$ (i.e. a hexagon whose opposite sides have distance $1$) can cover any set $S$ of diameter $\le 1$, here's a proof of this fact. An approach considering the maximal distance failed, so I used the more high-powered IVT and continuity-based method instead. Begin with a directed line $x$ and let its rotation by $+\theta$ be $x(\theta)$. For any $\theta$, there is a pair of lines $e_1,e_2$ both parallel to $x(\theta)$ which contain $S$ between them and have minimal distance. Since then both lines contain a point of $S$, and those points have distance $\le 1$, $d(e_1,e_2)\le 1$. Now move both lines by the same distance away from each other so that their distance would be exactly $1$, and call the resulting two directed lines $l(\theta)$ and $L(\theta)$, with $L$ in the left half-plane of $l$. In particular, $L(\theta)$ and $l(\theta+180^\circ)$ are the same line. Let $\text{Hex}(\theta)$ be the hexagon whose sides are $l(\varphi)$ for $\varphi=\theta,\theta+60^\circ,\dots,\theta+300^\circ$. All these hexagons cover $S$; we will prove one of them is regular and then we'll be done. To do this, we define a function $f(\theta)$ as follows. For simplicity, let $l(\theta),\dots,l(\theta+300^\circ)$ be $a,b,c,A,B,C$, respectively. Now define \[ f(\theta):=d(a\cap B,C)-d(A\cap b,c), \]then easy geometry shows $\text{Hex}(\theta)$ is regular iff $f(\theta)=0$. Moreover, replacing $\theta$ by $\theta+180^\circ$ switches $a,A$, $b,B$, $c,C$, and so \[ f(\theta)+f(\theta+180^\circ)=0. \]Since $f$ is continuous, IVT shows that $f$ must have a zero in $[0;180^\circ]$, hence done.
02.09.2021 06:14
Is there official sol available too?