Let $S$ be a set of $n$ points in the plane such that no four points are collinear. Let $\{d_1,d_2,\cdots ,d_k\}$ be the set of distances between pairs of distinct points in $S$, and let $m_i$ be the multiplicity of $d_i$, i.e. the number of unordered pairs $\{P,Q\}\subseteq S$ with $|PQ|=d_i$. Prove that $\sum_{i=1}^k m_i^2\leq n^3-n^2$.
Problem
Source: China TST 2011 - Quiz 1 - D1 - P2
Tags: inequalities, geometry, perpendicular bisector, combinatorics proposed, combinatorics
20.05.2011 02:13
Let $K$ be the number of isosceles triangles. A single segment is also counted as a special isosceles, and equilateral triangles are counted with multiplicity $3$. For each segment $AB$, there are at most $3$ isosceles triangles based at $AB$ because no four points are collinear. There are $\binom{n}{2}$ special isosceles triangles. So there are at most \[\binom{n}{2} \cdot 3 + \binom{n}{2} = 2n(n-1)\] isosceles triangles. Let $r$ be a distance with multiplicity $m$. Consider the graph $G$ spanned by the segments with length $r$. Let $d_i$ be the degree of vertex $i$. Then there are $m$ special isosceles triangles with side length $r$. The number of ordinary isosceles triangles with side length $r$ is $\sum_i{\binom {d_i}{2}}$, thus \[K_r = \sum_i \binom{d_i}{2} + m = \sum_i \frac{d_i^2}{2} \geq \frac{1}{2n} (\sum_i d_i)^2 = \frac{4m^2}{2n} = \frac{2m^2}{n}\] where $K_r$ is the number of isosceles triangles of side length $r$. Sum it over all $r$ we have \[2n(n-1) \geq K = \sum_r K_r \geq \sum_i \frac{2m_i^2}{n}\] which gives us $m_1^2 + m_2^2 + \cdots + m_k^2 \leq n^2(n-1)$
20.05.2011 05:57
I think it's more natural to just count the number of isosceles triangles directly (again, equilateral triangles with multiplicity $3$) without the "special" isosceles triangles... then letting $d_{i,j}$ denote the number of lengths of $d_i$ containing vertex $j$, \[3\binom{n}{2}\ge\sum_{i=1}^{k}\sum_{j=1}^{n}\binom{d_{i,j}}{2}\ge\sum_{i=1}^{k}n\binom{\frac{2m_i}{n}}{2}=\sum_{i=1}^{k}\frac{2m_i^2}{n}-\sum_{i=1}^{k}m_i=\sum_{i=1}^{k}\frac{2m_i^2}{n}-\binom{n}{2},\]so \[\sum_{i=1}^{k}m_i^2\le n^3-n^2\]as desired. (But it's equivalent, so whatever...)
21.01.2012 00:55
Consider the set $\mathcal{T} = \left \{ (p_i,p_j, \rho_f,) d_c \right \}$, where $\triangle \rho_f p_i p_j$ is $\rho_f$ isosceles and the length of the equal sides is $d_c$. So $\rho_f$ lies in the perpendicular bisector of the segment $p_i,p_j$. Since at most $3$ points can be collinear, we have $|\mathcal{T}| \le 3 \binom{n}{2}$. Now we will count $\mathcal{T}$ from the frame of $\rho_f$ and $d_c$. Note that $\sum_{c=1}^{k}m_c = \binom{n}{2} $ . Consider a point $\rho_f \in S$ and $A_{\rho_f}$ be the set of points , such that if $p_t \in A_{\rho_f}$, then $|\rho_f p_t| = d_c$. Its easy to see that $\sum_{\rho_f \in S}^{{}} |A_{\rho_f}| = 2m_c $ . So $\binom{|A_{\rho_f}|}{2}$ is the number of '' $\rho_f$ - isosceles '' triangles. So $\mathcal{|T|} = \sum_{c=1}^{k} \sum_{\rho_f \in S}^{{}} \binom{|A_{\rho_f}|}{2} = $ $\sum_{c=1}^{k} \left ( \sum_{\rho_f \in S}^{{}}\frac{{|A_{\rho_f}|}^2}{2} - \sum_{\rho_f \in S}^{{}}\frac{|A_{\rho_f}|}{2} \right ) \ge$ $ \sum_{c=1}^{k} \left ( \frac{ \left( \sum_{\rho_f \in S}^{{}} |A_{\rho_f}|\right )^2 }{2n} - m_c \right )$ $ = \sum_{c=1}^{k} \left ( \frac{2{m_c}^2}{n} - m_c \right ) $. So we get $3 \binom{n}{2} \ge \mathcal{|T|} \ge \left ( \sum_{c=1}^{k} \frac{2 {m_c}^2}{n} \right ) - \binom{n}{2} $, which gives $ \sum_{c=1}^{k}m_{c}^{2}\leq n^{3}-n^{2} $
23.03.2012 10:25
13.09.2014 21:24
03.03.2023 16:48
记 ${n}$ 个点为 $P_1,P_2,\cdots ,P_n.$ 显然有 $\sum\limits_{i=1}^km_i=n.$ 对于 ${S}$ 中任意三个点 $A,B,C,$ 若 $AB=AC,$ 则记 $\angle BAC$ 为一个"等角"$.$ 设"等角"的个数为 ${f}.$ 对 $1\leq i\leq k,1\leq j\leq n,$ 定义 $m_i(P_j)$ 为满足 $X\in S$ 且 $|XP_j|=d_i$ 的点的个数$,$ 从而 $\sum\limits_{j=1}^nm_i(P_j)=2m_i.$ 又 $P_j$ 引出的"等角"有 $\sum\limits_{i=1}^k\dbinom{m_i(p_j)}{2},$ 得到 $\begin{aligned}f&=\sum\limits_{j=1}^n\sum\limits_{i=1}^k\dbinom{m_i(p_j)}{2}=\sum\limits_{i=1}^k\sum\limits_{j=1}^n\dbinom{m_i(p_j)}{2}=\frac 12\sum\limits_{i=1}^k\left(\sum\limits_{j=1}^nm_i^2(P_j)-\sum\limits_{j=1}^nm_i(P_j)\right)\\&\geqslant\frac 12\sum\limits_{i=1}^k\left(\frac{4m_i^2}n-2m_i\right)=\sum\limits_{i=1}^k\left(\frac{2m_i^2}{n}-m_i\right)=\frac 2n\sum\limits_{i=1}^km_i^2-\dbinom{n}2.\end{aligned}$ 另一方面$,$ 对于 ${S}$ 中任意两点 $M,N,$ 满足 $\angle MXN$ 为一个"等角"的 ${X}$ 在 $PQ$ 的垂直平分线上$.$ 结合任意四点不共线$,$ 至多有三个 ${X},$ 因此 $f\leqslant 3\dbinom{n}2.$ 因此 $\frac 2n\sum\limits_{i=1}^km_i^2-\dbinom{n}2\leqslant f\leqslant3\dbinom{n}2,$ 即 $\sum_{i=1}^k m_i^2\leqslant n^3-n^2.\blacksquare$