There are $n$ sets of $k$ points in the 2-dimensional plane. Following the recent social distancing instructions, the distance between each two points in the same set is at least 2. We would like to choose a single representative point from each set, such that the distance between each two representatives is at least 2. What is the smallest $k$ (as a function of $n$) for which this is always possible?
For $n=2$, I am quite sure that the answer is 3. $k=2$ is insufficient, as shown below:
The distance between the green points is 2 and the distance between the blue points is 2, but the distance between each pair of representatives is only $\sqrt{2}$.
I do not have a proof that $k=3$ is sufficient, but in all configurations I tried, I ended up with a situation as shown below:
If the distance between every two green points is 2, and the distance between every blue and green point is less than 2, then the blue points must be inside a very small region, and then there must be some blue points with a distance of less than 2.
So my question is: given $n$ (the number of sets), what is the minimal $k$ (the number of points in each set) such that there always exist representatives with a sufficient separation?
Let $k(n)$ denotes the minimal sufficient $k$ for $n$ sets. A subset of the pane is $2$-separated, if the distance between each two disstinct points of the set is at least $2$.
An example where all sets are equal shows that $k(n)\ge n$.
Example 1. It seems that $k(n)\ge n+1$ for each $n\ge 2$.
Proof. Consider a regular $2n$-gon such that the distance between its neighbor by one vertices is $2$. Enumerate the vertices of the $n$-gon along its boundary by natural numbers from $1$ to $2n$. As each of sets $A_1,\dots, A_{n-1}$ pick the set of all vertices with odd numbers, and by the set $A_n$ pick the set of all vertices with even numbers. $\square$
Proposition 1. For each natural $n$, $k(n+1)\le k(n)+3$.
Proof. Given a family $\{A_i:1\le i\le n+1\}$ of $2$-separated sets of size $|k(n)+3|$ each, pick as the first representative a leftmost point $P$ from the union of the sets. Let $P$ represents $A_i$. By Lemma 2, each of the sets $A_j$ contains at most $3$ points at distance less than two from $n$. Let $A_j’$ be the set $A_j$ with these points removed. Then $\{A’_j:j\ne i\}$ is a family of $n$ $2$-separated sets of size $k(n)$ each, so we can choose a $2$-separated set of representatives for the family. When we add the point $P$ to this set, we obtain a $2$-separated set of representatives for the family $\{A_i\}$. $\square$
By Lemma 3, $k(2)\le 3$.
The following lemmas can be useful.
Lemma 1. An open disc of radius $2$ cannot cover six points with a distance at least $2$ between each distinct points.
Proof. Let a disc $D$ centered at $O$ with radius $2$ contains points $A_1,\dots, A_6$ in its interior. The rays $OA_i$ partition $D$ into six (maybe, degenerated) sectors, so one of them has the angle at most $\pi/6$. Using an equality $$|A_iA_j|^2=|OA_i|^2+|OA_j|^2-2|OA_i||OA_j|\cos\angle A_iOA_j$$ is easy to check that the distance between points $A_i$ lying on the rays bounding the sector is less than $2$. $\square$
Similarly we can prove the following
Lemma 2. A half of an open disc of radius $2$ cannot cover four points with a distance at least $2$ between each distinct points. $\square$
Lemma 3. Let $\mathcal A$ and $\mathcal B$ be subsets of a plane, $|\mathcal A|=3$, $|\mathcal B|=2$, and a distance between any two distinct points of $\mathcal A$ or of $\mathcal B$ is at least $2$. Then there exist points $A\in\mathcal A$ and $A\in\mathcal B$ such that the distance between $A$ and $B$ is at least $2$.
Proof. Suppose to the contrary that a distance between each point $A\in\mathcal A$ and each point $B\in\mathcal B$ is less than $2$. It follows that the set $\mathcal A$ is contained in the interior of a lens created by the circles of radius $2$ centered at points of $\mathcal B$. Since the lens is seen at angle at most $2\pi/3$ from any of these centers, say $B$, there are two distinct points $A'$ and $A’'$ of the set $\mathcal A$ such that the segment $A'A’'$ is seen from $B$ at angle less than $\pi/3$. Similarly to the end of the proof of Lemma 1, it follows that $|A'A'’|<2$.