XIV математическая олимпиада «Шелковый путь», 2020 год


Докажите, что для любого натурального числа $m$ существует такое натуральное $n$, что любые $n$ различных точек на плоскости можно разбить на $m$ непустых множеств, выпуклые оболочки которых будут иметь общую точку.
Выпуклой оболочкой конечного множества $X$ точек на плоскости называется множество точек, лежащих внутри или на границе хотя бы одного выпуклого многоугольника с вершинами в $X$, включая вырожденные, т. е. отрезок и точка считаются выпуклыми многоугольниками. Никакие три вершины выпуклого многоугольника не лежат на одной прямой. Многоугольник содержит свою границу. ( Зиманов А. )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Напомним теорему Хелли: если в конечном множестве выпуклых множеств точек на плоскости каждые три пересекаются, то и все пересекаются.
Докажем, что $n = 9m$ подходит. Пусть $X$ — произвольное множество из $9m$ различных точек на плоскости, а $Y$ — множество подмножеств $X$ размера $6m + 1$.
Предположим, что существуют такие $A, B, C \in Y$, что их пересечение пусто. Пронумеруем все точки из $X$ числами от 1 до $9m$. Выпишем на листе бумаги сначала все номера точек из множества $A$, затем из множества $B$ и в конце из множества $C$. В итоге, мы выпишем $|A| + |B| + |C| = 18m + 3$ числа. Так как эти три множества не пересекаются, то мы не могли выписать никакое число более, чем два раза. Значит, мы выписали не более $2 \cdot 9m = 18m$ чисел — противоречие. Следовательно, любые три элемента $Y$ пересекаются.
Так как выпуклая оболочка множества точек полностью содержит это множество, то выпуклые оболочки любых трех элементов $Y$ пересекаются. Следовательно, по теореме Хелли, выпуклые оболочки всех элементов $Y$ имеют какую-то общую точку $O$.
Докажем следующую лемму: если выпуклая оболочка какого-то конечного множества точек $Z$ содержит какую-то точку $P$, то существует $W \subseteq Z$, такое что $|W| \leq 3$ и выпуклая оболочка $W$ содержит $P$. По определению выпуклой оболочки, существует выпуклый многоугольник с множеством вершин $V \subseteq Z$ (возможно, вырожденный), который содержит эту точку $P$. Если $|V| \leq 3$, то $V$ подходит в качестве $W$. Иначе, сделаем произвольную триангуляцию многоугольника с вершинами в $V$. Точка $P$ должна лежать хотя бы в одном треугольнике разбиения. Множество вершин такого треугольника подходит в качестве $W$.
Заведем мешок, в который будем складировать непустые подмножества $X$. Определим следующую операцию, изменяющую $X$ и $Y$: выберем любое $A \in Y$. Так как выпуклая оболочка $A$ содержит $O$, то, по лемме, существует такое $B \subseteq A$, что $|B| \leq 3$ и выпуклая оболочка $B$ содержит $O$. Положим $B$ в мешок (очевидно, $B$ непусто), удалим элементы $B$ из $X$, и удалим из $Y$ множества, содержащие элементы $B$.
После одной операции мощность $X$ уменьшается не более, чем на три, и $Y$ непусто до тех пор, пока $|X| \geq 6m + 1$. Следовательно, мы можем выполнить операцию хотя бы $m$ раз. Выполним операцию ровно $m$ раз. Оставшиеся в $X$ точки распределим произвольным образом между множествами в мешке.
Итак, множества в мешке составляют разбиение начального множества точек на $m$ множеств и выпуклая оболочка каждого из них содержит точку $O$, т. е. они пересекаются, что нам и было нужно.

Комментарии от администратора Комментарии от администратора №2.     Индукцией по $m$ докажем, что любые хотя бы $4m^2$ различных точек на плоскости можно разбить на $m$ непустых множеств, выпуклые оболочки которых пересекаются. При $m = 1$ утверждение, очевидно, верно. Пусть оно верно для $m = k - 1$, где $k \geq 2$. Докажем, что оно верно и для $m = k$. Рассмотрим произвольное множество $X$ из хотя бы $4k^2$ различных точек на плоскости. Пусть $Y$ — подмножество точек $X$, лежащих на границе выпуклой оболочки всех точек из $X$. Если $|Y| < 4k$, то $|X \setminus Y| > 4k^2 - 4k > 4(k-1)^2$. По предположению индукции, $X \setminus Y$ можно разбить на $k - 1$ непустое множество точек, выпуклые оболочки которых пересекаются. Если добавить $Y$ к этому $k - 1$ множеству, то мы получим $k$ множеств, выпуклые оболочки которых пересекаются (так как выпуклая оболочка $Y$ содержит все точки из $X \setminus Y$). Если же $|Y| \geq 4k$, то рассмотрим два случая. Если все точки из $Y$ лежат на одной прямой, то и все точки из $X$ лежат на одной прямой. Проведем вдоль этой прямой ось координат и обозначим точки из $X$ через $A_1, A_2, \ldots, A_{|X|}$ по возрастанию координат. Так как $4k^2 > 2k$, то нам подходит разбиение: \[X = \{A_1, A_{|X|}\} \cup \{A_2, A_{|X|-1}\} \cup \ldots \cup \{A_{k-1}, A_{|X|-k+2}\} \cup \{A_k, A_{k+1}, \ldots, A_{|X|-k+1}\}.\] Иначе, точки $Y$ лежат на границе какого-то невырожденного выпуклого многоугольника. Обозначим точки из $Y$ в порядке обхода по часовой стрелке границы этого многоугольника через \[A_1, A_2, \ldots, A_k, B_k, B_{k-1}, \ldots, B_1, C_1, C_2, \ldots, C_k, D_k, D_{k-1}, \ldots, D_1, E_1, E_2, \ldots, E_{|Y| - 4k}.\] Пусть \[Z = \{A_k, B_k, C_k, D_k, E_1, \ldots, E_{|Y| - 4k}\} \cup (X \setminus Y).\] Докажем, что нам подходит следующее разбиение: \[X = \left(\bigcup_{i=1}^{k-1} \{A_i, B_i, C_i, D_i\}\right) \cup Z.\] Для этого достаточно доказать ключевое утверждение: выпуклые оболочки множеств \[\{A_1, B_1, C_1, D_1\}, \{A_2, B_2, C_2, D_2\}, \ldots, \{A_k, B_k, C_k, D_k\}.\] пересекаются. Через $f(M)$ будем обозначать выпуклую оболочку множества точек $M$. Пусть \[T \in A_1B_1 \cap A_kD_k,\] \[H_i = f(\{A_1, A_2, \ldots, A_i, B_i, B_{i-1}, \ldots, B_1, C_1, C_2, \ldots, C_i, D_i, D_{i-1}, \ldots, D_1\})\] и \[V_i = f(\{A_i, A_{i+1}, \ldots, A_k, B_k, B_{k-1}, \ldots, B_i, C_i, C_{i+1}, \ldots, C_k, D_k, D_{k-1}, \ldots, D_i\}).\] Тогда для любого $1 \leq i \leq k$ верно \[T \in A_1B_1 \subseteq H_i \ \text{и} \ T \in A_kD_k \subseteq V_i.\] Следовательно, \[T \in \bigcap_{i=1}^{k} (H_i \cap V_i) = \bigcap_{i=1}^{k} f(\{A_i, B_i, C_i, D_i\}),\] что и требовалось доказать.