Maths Olympiad Prep

Library / /4 of 7

, 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,yS,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>0D(S,r)23S2(S1)/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:yS,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), r0r \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=xSr>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=xSr>0(S(x,r)2)=r>0xS(S(x,r)2)r>0S(1SxSS(x,r)2)=r>0S(2D(S,r)S2)=2Sr>0D(S,r)2r>0D(S,r)=2Sr>0D(S,r)2(S2), \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.