Турнир городов - задания по годам → .09 Турнир городов 2023

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

Покажем теперь, как построить неправильную пирамиду с плоскими углами при вершине

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

Предположим целое удовлетворяет этому неравенству. Имеем

Но квадрат целого числа не может давать ни остаток 6, ни остаток 5 от деления на 9, значит,

Тогда исходное неравенство влечёт неравенство

Возводя в квадрат и приводя подобные слагаемые, получаем, что

Однако, прямая проверка показывает, что при исходное неравенство не выполняется — противоречие.

Положим и пусть и — количества синих и красных клеток. Оценим сверху количество общих сторон красных клеток с синими.

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

(1)

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

(2)

Из (1) и (2) следует, что

Поскольку получаем отсюда

Поскольку а целое, получаем нужный результат.

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

Значит, треугольники и подобны. Учитывая это и равенство имеем

Кроме того,

Следовательно,

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

Замечание. После доказательства подобия треугольников и можно действовать по-другому. Выберем точку на продолжении отрезка за точку так, что тогда треугольники и равны (). Значит, — равнобокая трапеция, и она вписана. С другой стороны, поскольку точки лежат на одной окружности. Значит, все пять точек лежат на окружности

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

Для любого предъявим явно начальную рассадку, которая является -удачной для любого натурального числа

Сначала для данного построим конечную геометрическую прогрессию со знаменателем для которой выполнено условие

Требуемый набор существует при любом целом поскольку уравнение

имеет решение на интервале так как левая часть меняет знак на его концах.

Расположим теперь кузнечиков в следующих начальных точках:

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

Сдвинув начало координат на 1 вправо, получим координаты кузнечиков

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

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

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

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

Лемма.

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

Доказательство леммы.

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

Вернёмся к задаче.

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

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

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

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

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

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

Воспользуемся методом математической индукции. Понятно, что для такая инструкция есть. Это база индукции. Теперь покажем, как из инструкции для сделать инструкцию для и для этого будет достаточно. Обозначим или Инструкция для будет выглядеть так:

I группа: сначала все пары вида в любом порядке

Если нечетно, сюда приходится добавить все пары вида при (назовём эти команды дополнительными).

II группа: инструкция для первых коробочек из индукционного предположения

III группа: все пары различных чисел вида в любом порядке

При длина этой инструкции не превышает

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

Есть четыре варианта того, как могут располагаться шарики основного цвета.

1) Они идут подряд, и все они среди левых коробок — ничего делать не надо;

2) Они идут подряд, и все они среди правых коробок — используем все пары вида ;

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

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

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

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

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