Let $P_{1}, P_{2}, \ldots, P_{2021}$ be 2021 points in the quarter plane $\{(x, y): x \geq 0, y \geq 0\}$. The centroid of these 2021 points lies at the point $(1,1)$. Show that there are two distinct points $P_{i}, P_{j}$ such that the distance from $P_{i}$ to $P_{j}$ is no more than $\sqrt{2} / 20$.
Problem
Source: Irish Mathematical Olympiad 2021 P10
Tags: combinatorics, combinatorial geometry, geometry, Centroid
10.05.2021 21:39
Let $(x_1,y_1),...,(x_{2021},y_{2021}),(x_G,y_G)$ be the coordinates of points $P_1,...,P_{2021}$ and the barycenter of the set of points. Also let $d$ be the minimal distance between two distinct points in the set $S=\{P_1,...,P_{2021}\}$. We will use the following lemma. In the set $A_n=\{(x,y)\in (\mathbb{R}_0^+)^2| nd\leq x+y<(n+1)d\}$ there are at most $2(n+1)$ points. The proof is that if in the definition of $n$ we used a weak upper bound we would obtain at most $2(n+1)+1$, but this optimal configuration uses some points on $x+y=(n+1)d$ and so we must have at most $2(n+1)$ points if we have a strict upper bound. Using our lemma, the optimal configuration (which need not necessarily be obtainable) for $2021$ points is one where we have $2\cdot 1$ points in $A_0$ with $x+y\geq 0d$, $2\cdot 2$ points in $A_1$ with $x+y\geq d$,..., $2\cdot 44$ points in $A_{43}$ with $x+y\geq 43d$, and $41$ points in $A_{44}$ with $x+y\geq 44d$. Therefore, we have $$2=x_G+y_G=\frac{1}{2021}(\sum_{i=1}^{2021} x_i+y_i)\geq \frac{1}{2021}(0d\cdot 2\cdot 1+1d\cdot 2\cdot 2+\cdots+43d\cdot 2\cdot 44+44d\cdot 41)=$$$$\frac{d}{2021}(2(0\cdot 1+\cdots 43\cdot 44)+44\cdot 41)=\frac{58564}{2021}d$$. Finally, we have that the minimal distance is $d\leq 2\cdot\frac{2021}{58564}=\frac{2021}{29282}=0.06901...<\frac{\sqrt{2}}{20}=0.07071$, and so we are done