|
|
 |
Условие
На плоскости дано множество S, состоящее из чётного числа точек, никакие три из которых не лежат на одной прямой.
Докажите, что S можно разбить на два множества X и Y так, что выпуклые оболочки conv X и conv Y имеют поровну вершин.
Решение
Обозначим через k(X) число вершин выпуклой оболочки conv X множества X.
Пусть A = A1A2...An = conv S, а T – множество всех точек из S, лежащих строго внутри A. Рассмотрим множества Xi = {A1, ..., Ai} ∪ T,
Yi = {Ai+1, ..., An}.
Найдём наименьшее i, для которого k(Xi) ≥ k(Yi). Очевидно, i < n. Если i = 0, можно выбрать такое подмножество T' ⊂ T, что k(T') = n (исключая точки из T по одной). Тогда T' и S \ T' – искомое разбиение.
Пусть 1 ≤ i ≤ n – 1. В силу минимальности i k(Xi) – 1 ≤ k(Xi–1) ≤ k(Yi–1) – 1 ≤ k(Yi). Значит, или k(Xi) = k(Yi) (и требуемое разбиение найдено), или k(Xi) – 1 = k(Xi–1) = k(Yi–1) – 1 = k(Yi). Рассмотрим последний случай.
Пусть X = Xi, Y = Yi. Так как k(X) + k(Y) нечётно, найдётся хотя бы одна точка M ∈ X, не лежащая на границах множеств conv X и conv Y. Если есть такая точка M, не лежащая внутри conv Y, то, перенеся её из X в Y, получим искомое разбиение.
Пусть все такие точки лежат внутри conv X ∩ conv Y. Тогда это пересечение непусто. Положим X' = X \ conv Y. Все точки X' лежат на границе conv X (поскольку все внутренние точки conv X лежат также внутри conv Y), значит, k(X') < k(X) и k(X') ≤ k(Y). Если k(X') = k(Y), то X' и S \ X' задают искомое разбиение. В противном случае будем добавлять к X' точки из X ∩ conv Y, пока не получим такое множество Z, что k(Z) = k(Y). Множества Z и S \ Z задают искомое разбиение.
