The problem: Suppose we have some set $X$ of $n$ points in the circle centered at the origin with radius $\frac{1}{2}$. Show that the number of pairs of points $x_{1}, x_{2}$ in $X$ whose distance $|x_{1} – x_{2}|$ apart is greater than $\frac{1}{\sqrt{2}}$ is at most $\lfloor \frac{n^{2}}{3} \rfloor.$ Show this is sharp for $n \geq 2$.
So far, I've tried to place a grid on a square over the points in the circle to apply the pigeonhole principle as one usually does for these sorts of problems, but I can't arrive at the actual conclusion. How can one prove this?
Best Answer
Observe that there is no quadrilateral in the circle defined in your problem whose sides and diagonals are all greater than $\frac{1}{\sqrt 2}$ because, as shown below, if all sides are greater than $\frac{1}{\sqrt 2}$, then at least one diagonal is greater than $1$ (to prove this use the law of cosines and the fact that, at least one angle of the quadrilateral is greater than or equal to $\ 90^{\circ}$).
Now, assume $x_1, x_2, ..., x_n$ are the points in the circle. Let's assume that $x_1, x_2, ..., x_n$ are vertices of a graph. If the distance $|x_i-x_j|$ is greater than $\frac{1}{\sqrt 2}$, then add the edge connecting $x_i$ and $x_j$. Based on this problem, if the constructed graph has $[\frac{n^2}{3}]+1$ edges, then it has a subgraph of $K_4$, which contradicts the fact that there is no quadrilateral in the circle defined in your problem whose sides and diagonal are all greater than $\frac{1}{\sqrt 2}$.
For the last part of the problem, for example if $n=3k+1$, put $k+1$ points inside the circle $C_1$, $k$ points inside circles $C_2$ and $C_3$. It is very easy to see that we can have circles $C_1, C_2$, and $C_3$ such that every point in each of the three circles is at a distance of greater than $\frac{1}{\sqrt 2}$ from every point of the two other circles. Then,
$$[\frac{n^2}{3}]=3k^2+2k=k(k+1)+k(k+1)=k^2.$$