Принцип крайнего, индукция и другие методы в комбигео

Лемма. Всякий угольник можно триангулировать (то есть разбить диагоналями на треугольники),причём полученный граф (стороны и диагонали являются ребрами) можно покрасить правильно в три цвета, то есть не будет ребра между двумя вершинами одного цвета.

Доказательство. Будем доказывать по индукции. База: — очевидно.

Переход: Для начала найдем угол меньше Такой очевидно есть. Обозначим вершину этого угла за Теперь рассмотрим отрезок, который соединяет соседние вершины(обозначим их за и с вершиной Если он лежит внутри многоугольника, то отрежем треугольник, который образовался. Остальной многоугольник триангулируется и раскрашивается в цвета по предположению. Поэтому достаточно раскрасить вершину в цвет, в который не раскрашены и Теперь разберемся с случаем, когда отрезок пересекает другие отрезки. Проведём из вершины отрезок к ближайшему концу мешающего отрезка (Ближайшему в смысле, что прямая через которая параллельна лежит ближе к чем все остальные). Тогда мы получили два меньших многоугольника, которые по предположению раскрашиваются и триангулируются. Цвета в этих многоугольниках переименовываются так, чтобы и в разных многоугольниках имели те же цвета. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к решению задачи. Давайте триангулируем и раскрасим наш угольник. Найдем цвет, которого меньше всего. И в каждую вершину этого цвета поставим сторожа. Тогда этих сторожей не более чем и они очевидно видят все точки этого многоугольника.

Замечание. Данная оценка является точной! Ведь если то есть пример, как на картинке ниже. Заметим, что чтоб видеть все точки каждого из этих треугольников, то в каждой закрашенной части должен быть сторож, а закрашенных частей ровно