(A.Akopyan, V.Dolnikov) Given a set of points inn the plane. It is known that among any three of its points there are two such that the distance between them doesn't exceed 1. Prove that this set can be divided into three parts such that the diameter of each part does not exceed 1.
Problem
Source: Sharygin contest. The final raund. 2008. Grade 10. Second day. Problem 8
Tags: geometry unsolved, geometry
22.01.2020 03:05
Nice problem! We will first dispatch of the case where there are two points which are at least $\sqrt3$ apart. Let $S$ denote the set of points in question. Case 1. The diameter of $S$ is $\ge \sqrt 3.$ Let $A, B$ be points in $S$ so that $AB \ge \sqrt3.$ Let $\omega_A, \omega_B$ denote the unit circles centered at $A, B,$ respectively. Let $\omega$ denote the region which is the (closed) intersection of $\omega_A$ and $\omega_B.$ Note that since $AB \ge \sqrt 3$, $\omega$ is either empty or has diameter at most $1.$ We claim that all of the points of $S$ in $\omega_A / \omega$ comprise a set of diameter at most $1.$ Indeed, if not, then consider two points $P_1, P_2 \in (\omega_A / \omega) \cap S$ so that $P_1 P_2 > 1.$ Then $P_1, P_2, B$ contradict the condition of the problem. A similar thing holds for $S \cap (\omega_B / \omega),$ and so from the previous results we know that $S \cap (\omega_A / \omega), S \cap (\omega_B / \omega), S \cap \omega$ is a partition of $S$ into three parts, each of diameter at most $1.$ Case 2. The diameter of $S$ is at most $\sqrt 3.$ Notice that for any three points $A, B, C$ so that $AB, BC, CA \le \sqrt 3$, there is a unit circle covering $\triangle ABC.$ Indeed, simply consider cases on whether $\triangle ABC$ is acute or obtuse (if acute, take the circumcircle; if obtuse take the circle with the longest side of $\triangle ABC$ as diameter). Hence, by Helly's Theorem, the set of unit circles centered at the points in $S$ all have a common point, say $P$. This means that the entirety of $S$ is contained in the unit circle centered at $P.$ Let $Q \in S$ be the point furthest from $P$, and let $PQ = r \le 1.$ Let $\omega_P$ denote the circle centered at $P$ of radius $r$; note that $S \subset \omega_P.$ Let $\omega_Q$ denote the unit circle centered at $Q.$ Note that the set of points of $S$ contained in $\omega_P / \omega_Q$ has diameter at most one, as else we can obtain a contradiction with two points of distance $>1$ and $Q.$ It only remains to notice that $\omega_P \cap \omega_Q$ can be split into two sets of diameter $1$ rather easily, by simply bisecting it along line $PQ.$ From here, the partition of $S$ is clear. As we've exhausted all cases, we're done. $\square$