Олимпиадное задание: Разделимость множеств точек S

Будем называтькрасно-разделимыммножество, для которого существует такой треугольник $\delta$, что все красные точки лежат строго внутри $\delta$, а все зеленые – строго снаружи. Пусть $A$ – конечное множество красных и зеленых точек общего положения, $P$ – выпуклая оболочка некоторых красных точек из $A$, $Q$ – подмножество зеленых точек $A$. Выясним, при каких условиях существует треугольник $\delta$, разделяющий $P$ и $Q$.

Без ограничения общности можно считать стороны $\delta$ опорными прямыми для $P$.

Зафиксируем некоторую окружность $c$. Каждой опорной прямой $l$ множества $P$ сопоставим точку $T(l)$ на $c$ такую, что касательная $t(T)$ к $c$ в точке $T(l)$ параллельна $l$ и $P$ лежит по ту же сторону от $l$, что $c$ от $t(T)$.

Пусть $X$ – произвольная точка $Q$, $l_1(X)$ и $l_2(X)$ – опорные прямые к $P$, проходящие через $X$ (если $X$ лежит внутри $P$, то $P$ нельзя отделить от $Q$), $a(X)$ дуга $c$, ограниченная точками $T(l_1(X))$ и $T(l_2(X))$.

Если разделяющий треугольник $\delta$ существует, три точки $c$, соответствующие его сторонам, «протыкают», все дуги $a(X)$, где $X\in Q$. С другой стороны, если существуют три точки $c$, протыкающие все дуги $a(X)$ и образующие остроугольный треугольник, то образованный соответствующими прямыми треугольник $\delta$ отделяет $P$ от $Q$.

Таким образом, задачу можно переформулировать: пусть любая достаточно большая подсистема системы дуг $c$ протыкается тремя точками, верно ли, что и вся система протыкается тремя точками.

Построим контрпример: систему равных дуг, такую, что любая точка протыкает почти треть всех дуг.

Пусть $n$ – натуральное число, $T_1, T_2, \ldots, T_{3n + 1}$ вершины правильного $(3n + 1)$-угольника, вписанного $c$, $T_{i + 3n + 1} \equiv T_i$. Для каждого $i$ пусть $a_i$ – открытая дуга $T_iT_{i + n}$. Тогда любая точка $c$ протыкает максимум $n$ дуг, следовательно, проткнуть все дуги тремя точками невозможно. С другой стороны, если удалить дугу $T_1T_{n + 1}$, все оставшиеся дуги можно проткнуть серединами дуг $T_{n + 1}T_{n + 2}$, $T_{2n + 1}T_{2n + 2}$ и $T_{3n + 1}T_1$.

Построим теперь контрпример к исходной задаче. Возьмем правильный 3001-угольник $Y_1Y_2\ldots Y_{3001}$, вписанный в окружность $k$ с центром $O$, $Y_{i + 3001} \equiv Y_i$. Для каждого $i$ обозначим через $X_i$ точку пересечения касательных к $k$ в точках $Y_i$ и $Y_{i + 1000}$. Небольшим перемещением точек $X_i$ в направлении $O$ получим множество общего положения. Покрасим все $X_i$ в зеленый цвет, а $Y_i$ – в красный, и обозначим полученное множество через $A$.

Так как выпуклая оболочка точек $X_i$ содержит $Y_i$, множество $A$ может быть только красно-разделимым. Но из приведенного выше рассуждения следует, что это не так.

Если удалить любую из точек $X_i$ или $Y_i$, то, как показано выше, $A$ станет красно-разделимым и, значит, разделимым.

Примечание. Назовем конечное множество $S$ красных и зеленых точек линейно-разделимым, если существует такая прямая $l$, что точки разных цветов лежат строго по разные стороны от $l$. Если любые четыре точки множества $A$ образуют линейно-разделимое множество, то и все множество линейно-разделимо.

Назовем конечное множеств $S$ красных и зеленых точек окружностно-разделимым, если существует такая окружность $c$, что все точки одного цвета лежат строго внутри $c$, а все точки другого – строго снаружи. Если любые пять точек множества $A$ образуют окружностно-разделимое множество, то и все множество $A$ окружностно-разделимо.