Given is an integer $k\geq 2$. Determine the smallest positive integer $n$, such that, among any $n$ points in the plane, there exist $k$ points among them, such that all distances between them are less than or equal to $2$, or all distances are strictly greater than $1$.
Problem
Source: Romanian TST 2022, Test 1, P5
Tags: combinatorics, geometry
14.05.2022 19:31
16.05.2022 16:56
@above bound conditions for the distances are not supposed to satisfied simultaneously The answer is (k-1)² + 1 Why (k-1)² doesnt work: Consider a k-1 gon with the radius 1/2. Place k-1 pieces k-1 gon in the plane while keeping the distance between any 2 circumcenter sufficiently large. If we select k points from these points,there will be 2 points are on the same circle ,thus distance between them will be less than or equal to 1, And there will be 2 points that are not in the same circle,thus the distance between them will be greater than 2. Algorithm that proves the existence of such k points among fixed (k-1)²+1 points. Pick an arbitrary point P1 and consider its disc with the radius 1. There will be at most k-1 points in it. At i-th move pick a point Pi that are not part of previous discs. Consider its disc with the radius 1. And continue the algorithm till k-th move. At the end of the k-th move there will be k points P1,P2,... Pk and clearly they satisfy the bound conditions
16.05.2022 17:38
Solution: The answer is $n=(k-1)^2+1=k^2-2k+2$. Lower bound (Construction): Take $k-1$ points $C_{1},C_{2},\ldots ,C_{k-1}$ such that $C_{i}C_{j}>3$ $\forall i\neq j$ (for concreteness, assume $C_{i}$'s are the vertices of a regular $k-1$-gon with side length greater than $3$). Now construct $k-1$ circles $\omega_{i}=\left(C_{i},\frac{1}{2}\right)$ and take $k-1$ different points at random in each circle. Thus we've constructed $(k-1)^2$ points (we disregard the points $C_{i}$). Now consider a group of $k$ points. By the PHP there exist two points from different circles, therefore the distance between them is $> 3-\frac{1}{2}-\frac{1}{2}=2$. Also by the PHP, there are two points from the same circle $\omega_{i}$, so the distance between them is $\leq \frac{1}{2}+\frac{1}{2}=1$. Therefore there does not exist a set of $k$ points such that the distances between any two of them are either $>1$ or $\leq 2$. Upper bound: Assume that we have $k^2-2k+2$ points. Consider the graph $G$ with $k^2-2k+2$ vertices corresponding to the points and colour the edge between two points in green if the distance between them is $\leq 1$ and red otherwise. Note the following important observation: $\textbf{Lemma:}$ If $AB$ and $AC$ are green, then $BC\leq 2$. $\textbf{Proof:}$ Since $AB$ and $AC$ are green, then $AB\leq 1$ and $AC\leq 1$. By the triangle inequality, we have that $BC\leq AB+AC=1+1=2$. We will now prove that there is either a clique of $k$ points where all distances are $\leq 2$ or a red clique of $k$ vertices. Assume the contrary. Notice that the Lemma implies that if a vertex $X$ is a part of $\geq k-1$ green segments, then $X$ combined with the $k-1$ vertices form a clique of the first type. This implies that each vertex has at least $(k^2-2k+2)-1-(k-2)=k^2-3k+3$ incident red edges. Thus we have that: \[|E_{\text{red}}|\geq \Bigg\lfloor\frac{|V|(k^2-3k+3)}{2}\Bigg\rfloor=\Bigg\lfloor\frac{(k^2-2k+2)(k^2-3k+3)}{2}\Bigg\rfloor\geq \frac{(k^2-2k+2)(k^2-3k+3)}{2}-\frac{1}{2}\]However, since we assumed that there isn't a red $K_{k}$, then by Turan's theorem we have that: \[|E_{\text{red}}|\leq \Bigg\lfloor \left(1-\frac{1}{k-1}\right)\cdot \frac{|V|^2}{2}\Bigg\rfloor= \Bigg\lfloor \frac{k-2}{k-1}\cdot \frac{(k^2-2k+2)^2}{2}\Bigg\rfloor\leq \frac{k-2}{k-1}\cdot \frac{(k^2-2k+2)^2}{2}\]Now we reach a contradiction by: \[\frac{(k^2-2k+2)(k^2-3k+3)}{2}-\frac{1}{2}>\frac{k-2}{k-1}\cdot \frac{(k^2-2k+2)^2}{2}\]\[\iff (k-1)(k^2-2k+2)(k^2-3k+3)-(k-1)-(k-2)(k^2-2k+2)^2>0\]\[\iff k^2 - 3 k + 3>0\iff \frac{1}{4} (2 k - 3)^2 + \frac{3}{4}>0\]So we proved that $|E_{\text{red}}|\leq \frac{k-2}{k-1}\cdot \frac{(k^2-2k+2)^2}{2}<\frac{(k^2-2k+2)(k^2-3k+3)}{2}-\frac{1}{2}\leq |E_{\text{red}}|$, contradiction.
02.01.2023 18:03
Really beautiful problem!! In graph theory language: "Let $m$ be a positive integer. The edges of $K_n$ are colored red and blue such that whenever $xy$ and $xz$ are blue, then $yz$ is also blue. What's the smallest $n$ (in terms of $m$) such that there always exists a $K_m$ inside the previous graph with all it's edges blue or all it's edges red."
05.05.2023 11:19
One of the official solution goes like that. To prove that for $n\ge (k-1)^2+1$ there always exists $k$ points one way or another, we assume there are no $k$ points with all pairwise distances less or equal to $2.$ Consider a graph $G(V,E)$ with vertices the given $n$ points. Two vertices are connected if the distance between them is at most $1.$ Note that $d(v)\le k-2, \forall v\in V.$ Indeed, if $d(v)\ge k-1$ then the distance between any two points of the set $\{v\}\cup N(v)$ is at most $2,$ which we assumed is not the case. Further we want to prove that there is an independent set in $G$ with at least $k$ vertices. This is a direct corollary of Caro - Wei theorem which says $$\alpha(G) \ge \sum_{v\in V}\frac{1}{1+d(v)}$$It only remains to put $d(v)\le k-2.$ This is the same approach as in #4, except that there is used Turan's theorem which is a weaker result than Caro - Wai's. You can see my blog for more details.