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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

1.

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

2.

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что поскольку то существует прямоугольник не являющийся нижне-, верхне-, лево- или правоплохим. Но тогда он пересекается со всеми прямоугольниками.

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

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

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

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

Предположим противное. Рассмотрим максимальное количество точек таких, что никакие из них не лежат на одной окружности. Их не более Каждая из оставшихся точек лежит на описанной окружности одного из треугольников, образованных этими точками. Таких треугольников всего не более Значит, все наши точки лежат не более чем на окружностях. Рассмотрим ту из них, на которой лежит наибольшее количество точек (их не менее и не более по нашему предположению). Оставшиеся хотя бы точек лежат на окружностях, так что на одной из этих окружностей (назовем ее ) лежит еще хотя бы точек. Докажем, что все наши точки лежат на окружностях и Предположим противное. Рассмотрим точку вне окружностей и Выберем на окружности точки не лежащие на Каждая из окружностей, описанных около треугольников пересекает окружность не более чем в двух точках. Выкинем не более чем точек, а также не более чем две точки пересечения и из рассмотрения (если какие-то из них отмечены). На окружности останется не менее отмеченных точек. Выберем одну из них, Описанные окружности треугольников и вторично пересекают не более чем в одной точке каждая. Выкинем из рассмотрения эти точки (если какие-то из них отмечены), на окружности останется не менее отмеченных точек. Выберем одну из них, и выкинем с окружности еще не более чем 6 точек, лежащих на описанных окружностях треугольников и На останется хотя бы точек, назовем любую из них Легко видеть, что из точек никакие не лежат на одной окружности. Противоречие. Итак, все отмеченные точки лежат на двух окружностях, следовательно, на одной из окружностей лежит не менее точек.

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

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

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

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

Пусть есть 2 фиолетовых числа и , которые симметричны относительно . Представим их как и из всех вариантов выберем те, где минимальный неотрицательный. Тогда , и . Так как числа были фиолетовыми, то . Значит, и , а . Заметим, что и значит, . С другой стороны, и поэтому . Противоречие.