|
|
 |
Условие
На плоскости даны n (n > 2) точек, никакие три из которых не лежат на одной прямой. Сколькими различными способами это множество точек можно разбить на два непустых подмножества так, чтобы выпуклые оболочки этих подмножеств не пересекались?
Решение
Так как выпуклые оболочки двух подмножеств не пересекаются, они лежат по разные стороны от некоторой прямой. Таким образом, требуется узнать, сколькими способами данное множество точек можно разделить прямой на два подмножества. Возьмём в плоскости точку O, не лежащую ни на одной из прямых, соединяющих данные точки, и рассмотрим полярное соответствие с центром O. Данным точкам будут соответствовать n прямых, никакие две из которых не параллельны и никакие три не пересекаются в одной точке. Как известно (см. задачу 60323), эти прямые делят плоскость на ½ n(n + 1) + 1 частей, из которых 2n неограниченных.
Лемма. Пусть поляры a, b точек A, B делят плоскость на четыре угла. Тогда полюса прямых, пересекающих отрезок AB, лежат в двух вертикальных углах, а полюса прямых, не пересекающих отрезок AB, – в двух других углах.
Доказательство. Пусть прямая l пересекает прямую AB в точке X. Тогда поляра X проходит через точку пересечения a и b. Если вращать l вокруг X, то ее полюс будет двигаться по этой прямой, то есть внутри пары вертикальных углов, образованных a и b. При движении точки X по AB ее поляра вращается вокруг точки пересечения a и b, переходя из одной пары вертикальных углов в другую в моменты прохождения X точки A или B.
Из леммы следует, что две прямые разбивают данное множество точек одинаковым образом тогда и только тогда, когда их полюсы либо лежат в одной из частей, на которые плоскость разбивается полярами данных точек, либо лежат по разные стороны от всех n прямых. Но второй случай возможен тогда и только тогда, когда обе точки лежат в неограниченных областях. Действительно, если точки P, Q лежат по разные стороны от всех прямых, то каждая из этих прямых пересекает отрезок PQ. Значит, каждый из продолжающих этот отрезок лучей целиком лежит в одной части. Обратно, если точка P лежит в неограниченной части, то возьмем луч с началом в ней, целиком лежащий в этой части и не параллельный ни одной из n прямых. Точки противоположного луча, лежащие дальше от P, чем все точки пересечения с прямыми, лежат по разные стороны с P от этих прямых.
Таким образом, 2n неограниченных областей разбиваются на пары, каждой из которых соответствует один способ разбиения данного множества точек, а каждой из остальных областей соответствует свой способ разбиения. Всего получаем ½ n(n – 1) + 1 способов, при одном из которых все n точек попадают в одно подмножество.
Ответ
½ n(n – 1) способами.
