We call a set of points free if there is no equilateral triangle with the vertices among the points of the set. Prove that every set of $n$ points in the plane contains a free subset with at least $\sqrt{n}$ elements.
Problem
Source: Romanian JBTST V 2007, problem 4
Tags: analytic geometry, combinatorics proposed, combinatorics
07.06.2007 16:44
Let $f(n)$ be the minimal size of the largest free subset among any distribution of $n$ points in the plane. We have to prove that $f(n) \geq \sqrt{n}$ for all $n$. Note that $f$ is clearly non-decreasing, so that it suffices to prove that $f(n^{2}+1) \geq n+1.$ Now, let's consider a set of $n^{2}+1$ points in the plane. Since it is a finite set of points, we may choose a system of coordinates such that no two of the given $n^{2}+1$ points have the same $x$-coordinate. Let $M_{1}, \cdots , M_{n^{2}+1}$ be the given points with $x_{1}< \cdots < x_{n^{2}+1}.$ Now, the $y$-coordinates form a sequence of length $n^{2}+1$. But it is well-known that such a sequence contains a non-decreasing subsequence of length $n+1$ or a non-increasing sequence of length $n+1$. Wlog, we may assume that we are in the first case, and let $P_{1}, \cdots ,P_{n+1}$ be some $n+1$ of the initial set of points such that $x_{i}< x_{j}$ and $y_{i}\leq y_{j}$ when $i<j$. It is a straightforward verification that this set of $n+1$ points cannot contains the three vertices of an equilateral triangle. Hence result. Pierre.
09.06.2007 13:39
Another solution: Let $F$ be maximal free subset of set $A$ with $n$ elements. Let $|F|=k$, then $|F'| = n-k$, $F' = A\setminus F$. Connect point $X\in F'$ with unordered pair $\{Y,Z\}\subset F$ iff $XY = XZ=YZ$. Then each point $X$ has degree at least 1 since it would contradict maximality of set $F$ and each pair $\{Y,Z\}$ has degree at most 2 (by contradiction, if pair is connected with three points, say $A,B,C$ then all triangles $AYZ$, $BYZ$ and $CYZ$ are equilateral, so two points from set $\{A,B,C\}$ are equal). Now we have \[\;\;\;\;\;2\cdot{k\choose 2}\geq n-k\] and problem is solved.
09.03.2015 07:04
how is f(n) non decreasing ?
09.03.2015 08:28
Now that you re-opened this old thread with this simple question, here is an immediate formal proof. For any finite configuration $C$ of points in the plane, denote by $F_C$ a largest free subset of $C$. Then, for $C\subset C'$, we have $|F_C| \leq |F_{C'}|$, since $F_C \subseteq C \subset C'$, thus $F_C$ is a free subset of $C'$. But we want to prove $f(n) = \min_{|C| = n} |F_C| \leq \min_{|C'| = n+1} |F_{C'}| = f(n+1)$, and according to the above, $|F_C| \leq |F_{C'}|$ for any $C\subset C'$ with $|C|=n$ and $|C'| = n+1$, so the claim is obvious.