Some points in the plane are either colored red or blue. The distance between two points of the opposite color is at most 1. Prove that there exists a circle with diameter $\sqrt{2}$ such that no two points outside of this circle have same color. It is enough to prove this claim for a finite number of colored points.
Problem
Source: Bundeswettbewerb Mathematik 2022, Round 2, Problem 4
Tags: enclosing circles, colored points, geometry, combinatorics
minusonetwelth
02.09.2022 11:37
(This is a summary of the proof that I submitted for the contest, 9 DinA4 pages iin total): Assume that there are at least two points of each color, as the other cases are trivial. Then the problem becomes equivalent to showing that there is a circle with diameter $\sqrt{2}$ that contains all the colored points (so either in or on the circle). We will call a circle $S$-tight if it is the smallest circle that contains all points of a set $S$. We will take the following for granted: (1) Every set $S$ of countably many points in the plane has a $S$-tight circle, that is moreover unique. (2) $S$-tight circles has at least two points $A,B\in S$ on it. (3) If the $S$-tight circle has exactly two points $A,B\in S$ on it, then $\overline{AB}$ is the diameter of the circle. (4) If the $S$-tight circle at least three points in $S$ on it, then we can find three of those points that form a right or acute triangle. We will denote the tight circle with respect to the colored points by $\omega$ with diameter $d$ and Midpoint $M$. If $d\le \sqrt{2}$ we are easily done. Hence we may assume that $d>\sqrt{2}$ from now on. Case 1: There are exactly two colored points on $\omega$ (see second attachement}. Using (3) those two points must form the diameter of the circle and have to be of the same color, as otherwise the distance condition would be dissatisfied, because $d>\sqrt{2}>1$. Wlog let them be red and denoted by $A$ and $B$. We now toss two circles with radius $1$ around those two points, such that now all blue points must lie in the intersection of these circles in order to satisfy the distance condition. If $M$ and $N$ are the intersection points of the two triangles, $H\coloneq \overline{AB}\cap\overline{MN}$, then we see that $$MN=2MH=2\sqrt{AM^2-AH^2}\le 2\sqrt{1-\left(\frac{\sqrt{2}}{2}\right)^2}=2\cdot\sqrt{1-\frac{1}{2}}=2\cdot\frac{1}{\sqrt{2}}=\sqrt{2}.$$It is now easy to see that the circle with $\overline{MN}, MN\le\sqrt{2}$ contains all blue points. Case 2: There are at least three colored points on $\omega$.
All points on omega are of the same color.
Assume ftsoc that this is not the case. By the pigeonhole principle at least two points must be of the same color, let them be wlog $A$, $B$ and $C$, where $A$ and $B$ are red, and $C$ is blue. If exactly $k=3$ points on the cirlce, they have two form a right or acute triangle, where $M$ must now lie on one of the sides or inside the triangle $\triangle ABC$. Hence $\angle AMB\le180^\circ$,and by the pigeonhole principle one of the angles $\angle CMA$, $\angle BMC$ is greater than or equal $90^\circ$, let it $\angle CMA$ (third att. left). By the pythagorean inequality
$$AC^2\ge MA^2+MC^2>2\cdot\left(\frac{\sqrt{2}}{2}\right)^2=1\Longleftrightarrow AC>1$$which violates the distance condition.
Now we assume that there are at least 4 points on the circle. If there are at least two red and two blue points, then each of the ${4\choose 3}$ triangles contains two points of the same color. One of them must be right or acute, whcih by the $k=3$ case leads to a contradiction. Thus we now assume that there are at least $3$ points of the same color,, say red, and let them be $A$, $B$ and $C$, on $\omega$. If they form a right or obtuse triangle with a blue point, we are done. If not, then $ABC$ recht- oder spitzwinklig. We now project the three points $M$ to $A^\prime$, $B^\prime$ and $C^\prime$ (att. 3 right), and look at a blue point $D$ on $\omega$. this point must lie on one of the arcs $C^\prime B^\prime$, $B^\prime A^\prime$ or $A^\prime C^\prime$. But in all cases $D$ forms a right or acute triangle with $BC$, $AB$ or $AC$, respectively, which is also a contradiction as in the $k=3$ case. Thus alll points on $\omega$ must be of the same color.
With this claim we now know that we may find three points on $\omega$ that have the same color, wlog red, and form a right or acute triangle. Let this triangle be called $\triangle ABC$. We complete the proof with the following claim.
All blue points have distance less than $\frac{\sqrt{2}}{2}$ from $M$.
Let $P$ be any blue point in $\omega$. AS $\triangle ABC$ right or acute, $M$ lies $\triangle ABC$ or on one of the side. We project $A$, $B$ und $C$ through $M$ onto $\omega$ to $A^\prime$, $B^\prime$ and $C^\prime$ again (see attachement one).
If $P$ lies in sector $C^\prime B^\prime$ (possibly on $BB^\prime$ or$CC^\prime$), then one of the angles $\angle PMB$ or $\angle PMC$ are right or obtuse as, $\angle BMC\le 180^\circ$ and thus $\angle PMB+\angle PMC\ge 180^\circ$ meaning by the pigeonhole principle one of them is greater than or equal $90^\circ$. With the exact same procedure we get the same thing when $P$ lies in the sectors $B^\prime A^\prime$ and $A^\prime C^\prime$, since $\angle BMA\le 180^\circ$ and $\angle AMC\le 180^\circ$ holds there too, respectively. Hence we can, no matter where $P$ lies, find a triangle $\triangle PMX$, $X\in\{A,B,C\}$, which is right or obtuse at $M$. Let $\ell=|PX|\le 1$. As $d=MX>\frac{\sqrt{2}}{2}$ the pythagorean inequality gives
$$|PM|^2+d^2\le\ell^2\Longleftrightarrow |PM|^2\le\ell^2-d^2< 1-\frac{1}{2}=\frac{1}{2}\Longrightarrow |PM|<\frac{\sqrt{2}}{2}.$$As the position of $P$ was arbitray, all blue points lie in a circle with diameter $2\cdot\frac{\sqrt{2}}{2}=\sqrt{2}$ around $M$, as desired..
The last claim finishes the proof.
Attachments:
