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

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

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

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

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

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

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

Рассмотрим следующие групп, состоящих из белых отрезков каждая: при группа состоит из отрезков …, а при

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

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

Поэтому отрезок учтён хотя бы в числах вида Поэтому

Из полученных двух оценок на сумму вытекает, что

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что утверждение задачи для некоторых неверно:

и при этом условии сумма — минимальная возможная.

Без ограничения общности тогда Возьмём -й слева белый отрезок и -й слева чёрный отрезок У какого-то из них правый конец левее.

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

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

Положим

и

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

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

Противоречие.

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

1.

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

2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

База: При это очевидно.

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

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

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

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

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

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

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

Обозначим . Тогда . По свойству биссектрисы , поэтому если , то . Сумма сторон треугольника равна периметру, т.е. , откуда , поэтому . Учтём неравенство треугольника:

Так как , то

На этом интервале содержится 24 целых значения .

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

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

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

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

Осталось посчитать количество “зиг-заг” триангуляций. Мы выбираем произвольную вершину за начало ломаной, далее идем от нее через одну вершины вправо или влево, и весь остальной путь однозначно определяется первым звеном. Итого, но каждую ломаную мы посчитали дважды (для одного конца и для второго), поэтому на самом деле ответ

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