Let $n\geqslant 2$ be an integer and $A{}$ a set of $n$ points in the plane. Find all integers $1\leqslant k\leqslant n-1$ with the following property: any two circles $C_1$ and $C_2$ in the plane such that $A\cap\text{Int}(C_1)\neq A\cap\text{Int}(C_2)$ and $|A\cap\text{Int}(C_1)|=|A\cap\text{Int}(C_2)|=k$ have at least one common point. Cristi Săvescu
Problem
Source: Romania JBMO TST 2024 Day 4 P4
Tags: combinatorics, combinatorial geometry
01.08.2024 22:19
To see why this works, notice that $C_{1}$ can't be "inside" of $C_{2}$ since $C_{1}$ and $C_{2}$ have k points inside, and $A \cap\text{Int}(C_{1}) \neq A \cap\text{Int}(C_{2})$. And since $2k > n$, $A\cap Int(C_{1})$ and $A \cap Int(C_{2})$ have at least a common point so the circles intersect. Now we show why $k \le [\frac{n}{2}]$ fails. Consider a line $d$ such that it isnt parallel to any line determined by any two points from $A$. We can rotate the plane such that $d$ is vertical. Now label the points $A_{1}$, $A_{2}$, $\dots$, $A_{n}$ from left to right and consider the lines $d_{1}$, $d_{2}$, $\dots$, $d_{n}$ parallel to $d$ such that line $d_{i}$ passes through point $A_{i}$. We will show that there is a circle containing (only) points $A_{1}$, $A_{2}$, $\dots$, $A_{k}$. Consider a circle with center $O$ tangent to $d_{k}$ at point $A_{k}$ (to the left of $d_{k}$) with radius $c$. As $O$ moves to the left on the line perpendicular to $d_{k}$ at $A_{k}$, the angle $\angle A_{k}A_{i}O$ is increasing for any $i \in \{1,2, \dots, k-1\}$ and hence it will eventually surpass $90^{\circ}$. Therefore, if $c$ is sufficiently large, we will have $OA_{i} < c$ for any $i \in \{1,2,\dots,k-1\}$ and so, the circle will contain every one of the $k$ points. Similarly, we can construct a circle that cointains the last $k$ points to the right and these clearly dont intersect so we are done.