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

Рассмотрим пятиугольник и наибольшую диагональ в нем, не умаляя общности это Она разбивает пятиугольник на треугольник и четырехугольник В четырехугольнике рассмотрим диагонали и Проверим неравенство треугольника для треугольника на диагоналях и Получается, что и так как — наибольшая диагональ. Пересечение отрезков и обозначим за

Тогда образуется треугольник откуда получаем, что из диагоналей можно составить треугольник.

Будем последовательно выбирать квадраты по следующему алгоритму: на каждом шаге берём квадрат наибольшей площади из оставшихся, удаляем его вместе со всеми пересекающимися квадратами. Полученные выбранные квадраты не пересекаются по построению.

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

Аналогично на каждом следующем шаге площадь удаляемых квадратов Поскольку весь исходный квадрат имеет площадь получаем неравенство:

Таким образом, выбранные непересекающиеся квадраты дают требуемую оценку.

Рассмотрим все пары точек и Для каждой пары найдём количество точек таких что площадь треугольника равна Площадь треугольника можно выразить как где — высота к основанию Отсюда

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

Общее количество пар точек: Каждый треугольник учитывается трижды (по каждому из трёх оснований). Следовательно, общее число треугольников не превосходит:

Что и требовалось доказать.

Сначала покажем, как осуществить требуемую в условии триангуляцию угольника, если делится на Занумеруем вершины угольника по часовой стрелке числами от до Проведём диагонали, попарно соединяющие вершины для всех они и образуют искомую триангуляцию. При этом из вершины номер выходит диагонали, из вершин для всех по диагонали и из вершин и для всех — диагоналей.

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

Рассмотрим хорошую триангуляцию угольника. Хорошо известно, что её треугольники можно раскрасить в цвета, белый и чёрный, так, что любые два треугольника, имеющих общую сторону, окрашены в разные цвета. Этот факт легко доказать индукцией по числу диагоналей, начав с монотонной окраски всего многоугольника, добавляя по одной диагонали и меняя каждый раз окраску всех частей многоугольника с одной из сторон от добавляемой диагонали на противоположный цвет.

Заметим, что, если из каждой вершины угольника выходит чётное число диагоналей, то каждая его сторона является стороной треугольников одного, скажем чёрного, цвета. Тогда каждая диагональ триангуляции и каждая сторона угольника являются сторонами в точности одного из чёрных треугольников. Если чёрных треугольников штук, то откуда следует, что делится на Отсюда легко следует, что и делится на

Усилим утверждение, найдется нечетное число таких ячеек.

База индукции: Для оно очевидно, ведь симплекс это просто отрезок с разноцветными концами и, если на нем отметить точки двух цветов, то найдется нечетное число отрезков с разноцветными концами.

Индукционный переход: Предположим, что лемма верна для всех симплексов размерности Докажем её для -мерного симплекса

Построим граф

• Вершины графа -мерные симплексы триангуляции и внешняя область.
• Ребра соединяют две вершины, если соответствующие им симплексы имеют общую -мерную грань, вершины которой раскрашены в цвета
• На внешней грани симплекса содержащей вершины по индукционному предположению существует нечётное число -мерных симплексов с вершинами цветов Следовательно, степень вершины, соответствующей внешней области, нечётна.
• В графе число вершин с нечётной степенью чётно. Так как внешняя область имеет нечётную степень, существует нечётное число внутренних -мерных симплексов с нечётной степенью.
• У симплекса нечетной степени есть грань с вершинами цветов Если оставшаяся вершина не цвета то его степень равна двум, противоречие, значит, все его вершины разноцветны.

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

База для очевидна. Теперь докажем переход от к Пусть в хорошей раскраске на вершинах есть гадкий четырёхугольник причём, не умаляя общности, вершины и — чёрные, а и — белые. Рассмотрим одну из триангуляций, которая соответсвует данной раскраске.

Если вершина не соединена рёбрами с вершинам, кроме своих соседей, то её соседи соединены, а значит, среди них есть чёрная вершина Не умаляя общности, вершины идут так: ----- но тогда в многоугольнике без вершины раскраска должна быть правильной, при этом есть гадкий четырёхугольник По предположению индукции получаем противоречие.

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

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

(выбрать начало чёрного блока — способов, а после этого белого — способ).

Заметим, что все такие раскраски подходят, а значит, всего существует хороших раскрасок.

Докажем по индукции более сильный факт: пусть — произвольная точка на одной из данных прямых, через которую не проходит ни одна из остальных прямых; тогда существует требуемая ломаная, начинающаяся с

Пусть — данные прямые, лежит на — ближайшая к точка пересечения с остальными прямыми (если ближайших точек две, выберем любую из них). Можно считать, что лежит на

По предположению индукции существует несамопересекающаяся ломаная начинающаяся с и содержащая по одному звену на каждой из прямых Тогда — требуемая ломаная.

Докажем более общее утверждение: если дано точек, образующих выпуклый -угольник, то между ними нельзя провести больше отрезков так, чтобы любые два имели общую точку. Сделаем индукцией по

База для очевидна. Докажем переход от к Пусть можно выбрать больше отрезков требуемым образом, тогда какая-то точка является концом хотя бы 3 отрезков (иначе отрезков не больше Выберем из них 3 любые, пусть они соединяют с и причём в выпуклой оболочке всех точек они идут в порядке ----

Если существует отрезок, соединяющий с какой-то вершиной, кроме то он должен пересекать отрезки и чего быть не может. Тогда выкинув вершину мы выкинем одно ребро, и для оставшихся точки проведено больше отрезков, что невозможно по предположению индукции, так как все условия выполняются.

Применим принцип крайнего: выберем среди всех троек точек треугольник с самым большим углом

Предположим, что точки , , не подходят. Тогда существует точка в объединении частей плоскости, одна из которых заключена между прямыми и а другая — между прямыми и

При этом не может лежать внутри треугольника , иначе .

Рассмотрим случай, когда лежит между лучами и (когда и лежат в разных полуплоскостях относительно ). Тогда

получаем противоречие. То же работает для случая, когда лежит между лучами и .

Оставшиеся два случая (когда и лежат в разных полуплоскостях относительно ) рассматриваются аналогично: в них

Правильный шестиугольник можно разбить на шесть правильных треугольников со стороной 1. Тогда хотя бы в одном из этих треугольников будет лежать две отмеченные точки. Расстояние между ними не будет превосходить стороны треугольника.

В решении будем пользоваться тем фактом, что у любой триангуляции выпуклого многоугольника есть так называемое “ухо”, т.е. треугольник триангуляции, к которого минимум стороны являются сторонами многоугольника.

Будем доказывать утверждение задачи индукцией по

База. Для треугольника утверждение задачи очевидно.

Предположение. Будем считать, что утверждение задачи верно для любой триангуляции при

Переход. Докажем утверждение для Рассмотрим триангуляцию нашего -угольника. Найдем в нем “ухо” и пока забудем об этом треугольнике триангуляции. Оставшийся -угольник можно раскрасить в три цвета правильным образом по предположению индукции. Вернем наше “ухо”. Оставшаяся вершина -угольника, которая принадлежит только “уху” из треугольников триангуляции, соседствует только с вершинами. Значит, ее можно спокойно покрасить в оставшийся цвет. Переход доказан.

Перед нами задача вида “оценка пример”. Сперва докажем оценку. По индукции по будем доказывать, что наибольшее возможное значение не превосходит

База индукции: Если то стороны единственного треугольника обязаны быть но это противоречит условию, о том, что в треугольнике есть две равные стороны.

Индукционное предположение: Пусть утверждение индукции выполняется для всех от до Рассмотрим произвольное распределение важностей для угольника, где Согласно условию, должен быть отрезок важности рассмотрим произвольный треугольник на вершинах угольника, для которого этот отрезок является стороной (далее будем называть такие треугольники подходящими). В треугольнике не может быть более одной стороны важности ведь иначе оставшаяся сторона должна быть меньше

Обозначим вершины отрезка важности как и за и обозначим произвольные вершины угольника (такие найдутся, так как ). Покажем, что важности сторон треугольника не поменяются при замене на Действительно, при такой замене отрезок будет заменён на а отрезок на Но поскольку оба треугольника и содержат отрезок важности то, согласно доказанному выше, важности пар сторон каждого треугольника равны. Значит, важности и как и важности и совпадают.

Проделаем следующую процедуру: для отрезка с важностью эти две вершины склеим в одну вершину и для каждой вершины важностью будем считать равной важности Докажем, что многоугольник удовлетворяет первому условию и “ослабленному” второму, т.e. важности всех его сторон и диагоналей образуют отрезок или натурального ряда без пропусков. Действительно, для любого подходящего треугольника нового многоугольника, если ни одна из вершин не была склеена с другой, то требование на важности сторон не изменилось. Если же какая-то вершина (без ограничения общности, вершина ) была склеена из вершин и то, как было показано ранее, распределение важностей в треугольнике будет таким же, как в треугольниках и в каждом из которых первое условие было выполнено, а значит, оно не нарушилось и после склейки. Второе, "ослабленное"условие также будет выполнено, т.к. после склейки из набора важностей будет удалено

Проделав такую склейку по очереди с каждым отрезком важности получим угольник , для которого выполнено первое и второе "ослабленное условия задачи". Для него понизим все важности на и получим выполняющиеся условия для угольника, значит, откуда Индукция доказана.

Пример: Занумеруем все вершины угольника числами от до и зададим отрезкам, соединяющим вершины с номерами и важность Легко проверить, что оба условия на важности выполняются, и максимальная важность равна

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

Будем доказывать это утверждение индукцией по числу вершин многоугольника.

База для очевидна.

Переход. Пусть для и меньших значений всё доказано, докажем для Найдём три соседние вершины разного цвета. Пусть не нашлось, тогда использовались бы только два цвета, а это противоречило бы условию наличия всех трёх цветов. Пусть вершины идут по порядку и окрашены в цвета 1, 2 и 3 соответственно.

Случай 1. Если между вершинами и в части многоугольника, где нет есть хотя бы одна вершина цвета 2, то отсекаем от многоугольника треугольник по линии получая угольник, для которого выполняются все условия индукции. По предположению, его можно разбить на треугольники с необходимым условием. Тогда получается, что мы получили разбиение угольника.

Случай 2. Если же такой вершины не нашлось, то все вершины поочерёдно окрашены в цвета 1 и 3. Тогда можно провести отрезки от вершины ко всем остальным вершинам. Тем самым мы получаем искомое разбиение.

Переход доказан.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Докажем утверждение индукцией по числу вершин многоугольника Для получаем, что все стены внешние, поэтому открываются наружу, ЧТД. Пусть для выпуклого -угольника доказано, докажем для -угольника. В любой триангуляции (разбиении многоугольника на треугольники) есть треугольник, две из сторон которого являются исходными сторонами многоугольника. Рассмотрим его. Если его “диагональная” дверь открывается наружу, то мы нашли нужную комнату. Иначе эта дверь открывается внутрь, тогда уберём комнату из дворца. Снова получим многоугольник, в котором все внешние двери открываются наружу. По предположению индукции, там найдётся нужная комната, ЧТД.

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

Теперь осталось показать, что можно подобрать такое что Для этого достаточно выбрать любое

Будем считать, что стороны пронумерованы по часовой стрелке. Рассмотрим направление параллельное первой стороне многоугольников. Проекция на равна удвоенной сумме проекций ее сторон на это направление, а эта сумма равна:

где — -ая сторона Просуммируем это по всем направлениям

Аналогично, для и его сторон А так как проекции на любое направление строго больше, чем проекции получаем, что

Пусть выбрано отрезков. Докажем утверждение методом математической индукции по

1.

База: Для одного отрезка просто отметим его правый конец.

2.

Переход: Пусть мы можем так отмечать для отрезков. Докажем, что мы сможем так сделать для отрезков. Для этого рассмотрим отрезок, у которого конец находится правее всех концов других отрезков. Далее «забудем» про этот отрезок, и для оставшихся отрезков применим предположение. Теперь «вспомним» отрезок. Если он содержит нечетное число отмеченных точек, то мы смогли отметить точки нужным образом. Если же это не так, то дополнительно отметим его конец, так как он самый правый, то остальные отрезки его не содержат и мы получим требуемое.

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

Переход. Воспользуемся предположением и разделим треугольник на прямоугольных треугольников. Среди полученных треугольников выберем любой и разделим его на два прямоугольных. Получили разделение на прямоугольный треугольник.