Maths Olympiad Prep

Library / Ninth STARS OF MATHEMATICS Competition /4 of 7

Ninth STARS OF MATHEMATICS Competition, 2015

Combinatorics Difficulty 5.6 AIME, harder Prove it Romania

Let SS be a finite planar set no three points of which are collinear, and let D(S,r)={{x,y}:x,y∈S,dist(x,y)=r}D(S, r) = \{\{x, y\} : x, y \in S, \text{dist}(x, y) = r\}, where rr is a positive real number, and dist(x,y)\text{dist}(x, y) is the Euclidean distance between the points xx and yy. Show that
∑r>0∣D(S,r)∣2≤3∣S∣2(∣S∣−1)/4. \sum_{r>0} |D(S, r)|^2 \le 3|S|^2(|S| - 1)/4.

Solution

Given a point xx in SS and a real number rr, let S(x,r)={y:y∈S,dist(x,y)=r}S(x, r) = \{y : y \in S, \text{dist}(x, y) = r\}, and notice that the S(x,r)S(x, r), r≥0r \ge 0, partition SS.
The number of non-degenerate isosceles triangles with vertices in SS and apex at xx
is ∑r>0(∣S(x,r)∣)2\sum_{r>0} (|S(x,r)|)^2, so the total number of non-degenerate isosceles triangles with vertices
in SS is N=∑x∈S∑r>0(∣S(x,r)∣2)N = \sum_{x \in S} \sum_{r > 0} \binom{|S(x,r)|}{2}, equilateral triangles with vertices in SS being counted three times each. Now,
N=∑x∈S∑r>0(∣S(x,r)∣2)=∑r>0∑x∈S(∣S(x,r)∣2)≥∑r>0∣S∣(1∣S∣∑x∈S∣S(x,r)∣2)=∑r>0∣S∣(2∣D(S,r)∣∣S∣2)=2∣S∣∑r>0∣D(S,r)∣2−∑r>0∣D(S,r)∣=2∣S∣∑r>0∣D(S,r)∣2−(∣S∣2), \begin{align*} N &= \sum_{x \in S} \sum_{r > 0} \binom{|S(x, r)|}{2} = \sum_{r > 0} \sum_{x \in S} \binom{|S(x, r)|}{2} \\ &\geq \sum_{r > 0} |S| \binom{\frac{1}{|S|} \sum_{x \in S} |S(x, r)|}{2} = \sum_{r > 0} |S| \binom{\frac{2|D(S,r)|}{|S|}}{2} \\ &= \frac{2}{|S|} \sum_{r > 0} |D(S, r)|^2 - \sum_{r > 0} |D(S, r)| = \frac{2}{|S|} \sum_{r > 0} |D(S, r)|^2 - \binom{|S|}{2}, \end{align*}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.