We say that a finite set $S$ of red and green points in the plane is separable if there exists a triangle $\delta$ such that all points of one colour lie strictly inside $\delta$ and all points of the other colour lie strictly outside of $\delta$. Let $A$ be a finite set of red and green points in the plane, in general position. Is it always true that if every $1000$ points in $A$ form a separable set then $A$ is also separable?
Problem
Source: Sharygin Finals 2018 Grade 10 P4
Tags: geometry, combinatorics
27.08.2018 20:02
No, it's not true. A counterexample is sketched below. Take a equalatteral trianle $T$ with center $O$. Let $k$ be its incircle and $R$ be the radius of its circumcircle. We construct a circle $K$ with center $O$ and radius $R-\varepsilon$, where $\varepsilon$ is sufficiently small. Now, suppose the set $A$ consists of many points which very densely cover the circles $k$ and $K$. The points on $K$ are red and those on $k$ - green. Then $A$ is not separable. But if one chooses any $1000$ points (or less) on $K$, there will be a small arc on $K$ which is free of points. If $\varepsilon$ is sufficiently small, we could rotate and a bit transform $T$, such that one of its vertices slightly protrude through that arc and the other two be inside $K$. Hence that triangle would separate $k$ with those $1000$ red points on $K$.
29.07.2022 14:40
The official solution more strongly constructs a set $A$ such that it is not separable, while if we remove any point from $A$, then it becomes separable.
02.08.2022 16:05
guptaamitu1 wrote: The official solution more strongly constructs a set $A$ such that it is not separable, while if we remove any point from $A$, then it becomes separable. The provided link shows it's a Nikolai Beluhov's problem, and the official solution is virtually the same as in #2.