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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

1.

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

2.

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

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

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

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

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

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

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

То есть внутри можно отметить не более точек.

Пример. Будем отмечать точки с координатами Если то будет отмечено ровно точек. Если то будет отмечено точек. Если то будет отмечено точек.

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

Для краткости точку будем обозначать просто Заметим, что точки не повторяются: если бы оказалось, что при то выполнялось бы и т.д., тогда число хорд было бы конечным. Итак, каждая новая точка попадает строго между ранее поставленными.

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

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

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

(1)

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

Если предел равен нулю, то нулю же равен и предел последовательности поскольку Но заметим, что То есть если то Кроме того, всегда не равно нулю (иначе две точки совпали). Значит для в последовательности встречаются члены большие со сколь угодно большими номерами — ноль не является пределом.

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

Выберем будем говорить о числах 0 и как о двух пределах. Начиная с какого-то номера все должны попадать в -окрестность одного из двух пределов. Но тогда при переходе от к расстояние до предела будет расти в 2022 раза - рано или поздно выскочит из -окрестности текущего предела и еще не дотянется до -окрестности другого предела.

Докажем по индукции, что всего областей.

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

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

Рассмотрим минимальное множество дорожек покрывающее весь коридор. Требование минимальности означает, что при удалении любой дорожки из оно перестаёт покрывать коридор.

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

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

Таким образом, если показать, что после гомотетии на столе найдётся точка, не покрытая ни одной салфеткой, то задача будет доказана, ведь можно будет добавить новый квадрат с центром в этой точке. А она, очевидно, найдётся, поскольку суммарная площадь квадратов равна а площадь стола — Что и требовалось.