Сложный вариант осеннего тура Турнира Городов

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

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

Первое решение. Случай очевиден. Иначе и различны, пусть Всего лягушка проигрывала путь, длина которого делится на и на а значит, и на так как и взаимно просты. Тогда длина пути равна для некоторого натурального и лягушка сделала «коротких» прыжков вправо и «длинных» прыжков влево.

Известно, что при взаимно простых и можно представить в виде с целыми и Это равенство, очевидно, сохранится, если одновременно увеличить (или уменьшить) на и на Поэтому можно выбрать натуральным и не превосходящим При этом будет неотрицательным (иначе и так как то (ведь Поэтому

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

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

Сложим число коротких прыжков во всех окнах — получим ведь каждый прыжок учил раз. Окон и в среднем на окно придётся коротких прыжков. Это число равно

что больше и меньше Значит, найдётся окно, где коротких прыжков не менее и окно, где их не более

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Через обозначим разность между положениями лягушки в момент (то есть через шагов после начала) и в момент Так как их разделяет шагов, то

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

Заметим, что разность между и определяется тем, какими были -й и -й шаги; разобрав случаи, нетрудно убедиться, что она равна или Это означает, что числа либо все меньше либо все больше

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

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

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

то четырёхугольник вписанный. Поэтому точки лежат на одной окружности.

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

Первое решение.

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

Поскольку

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

______________________________________________________________________________________________________________________________________________________

Второе решение.

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

Пусть — середина стороны , — точка касания вневписанной окружности для треугольника пересекается с в точке Воспользуемся фактом, что на прямой лежит диаметрально противоположная точке точка

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

В итоге имеем В силу перпендикулярности мы знаем, что Кроме того, по свойству ортоцентра тогда Так что — параллелограмм, поэтому

Замечание.

Равенство можно проверить чисто технически: пусть — высота тогда При этом

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

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

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

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

"Потери"на горизонтальные ходы происходят только на втором и четвёртом этапах.

Пусть первоначальная последовательность была Введём новую последовательность посчитаем разность для

Тогда Поскольку то что и требовалось.

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

(b) Рассмотрим соседние вершины и Обозначим через разбиение, в котором все диагонали выходят из вершины а через — разбиение, в котором все диагонали выходят из Заметим, что в ни одна диагональ не выходит из Поскольку за одну перестройку добавляется не более одной диагонали, выходящей из то для преобразования в требуется не менее перестроек.

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

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

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

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