Maths Olympiad Prep

Library / /333 of 520

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it

Example 6 Given nn distinct points in the plane. Prove: the number of pairs of points at unit distance apart is less than 2n32 \sqrt{n^{3}} pairs.

Solution

Prove that for a set of points {P1,P2,,Pn}\left\{P_{1}, P_{2}, \cdots, P_{n}\right\} in the plane, let aia_{i} be the number of points PiP_{i} that are a unit distance from PiP_{i}. Assume ai1a_{i} \geqslant 1, then the number of pairs of points that are a unit distance apart is
A=a1+a2++an2A=\frac{a_{1}+a_{2}+\cdots+a_{n}}{2}

Let CiC_{i} be the circle with center at point PiP_{i} and radius 1.
Since each pair of circles has at most 2 intersection points, the total number of intersection points of all CiC_{i} is at most
2Cn2=n(n1)2 \mathrm{C}_{n}^{2}=n(n-1)

The point PiP_{i} appears as an intersection point of CjC_{j} Caj2\mathrm{C}_{a_{j}}^{2} times, so
n(n1)j=1nCaj2=j=1naj(aj1)212j=1n(aj1)2.n(n-1) \geqslant \sum_{j=1}^{n} \mathrm{C}_{a_{j}}^{2}=\sum_{j=1}^{n} \frac{a_{j}\left(a_{j}-1\right)}{2} \geqslant \frac{1}{2} \sum_{j=1}^{n}\left(a_{j}-1\right)^{2} .

By the Cauchy-Schwarz inequality, we get

Thus
[j=1n(aj1)]2nj=1n(aj1)2n2n(n1)<2n3\left[\sum_{j=1}^{n}\left(a_{j}-1\right)\right]^{2} \leqslant n \cdot \sum_{j=1}^{n}\left(a_{j}-1\right)^{2} \leqslant n \cdot 2 n(n-1)<2 n^{3}

Therefore
j=1n(aj1)<2n3\sum_{j=1}^{n}\left(a_{j}-1\right)<\sqrt{2} \cdot \sqrt{n^{3}}
A=j=1naj2<n+2n32<2n3A=\frac{\sum_{j=1}^{n} a_{j}}{2}<\frac{n+\sqrt{2 n^{3}}}{2}<2 \sqrt{n^{3}}

Hence the proposition is true.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.