Турнир городов - задания по годам

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

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

Решение 1. Ясно, что положим где — натуральное, и будем искать количество подходящих то есть таких для которых уравнение

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

Умножив на и приведя подобные слагаемые получаем:

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2.

Очевидно, где натуральное. Запишем равенство из условия в виде

Отсюда:

Чтобы условие задачи выполнялось с данным необходимо и достаточно, чтобы было целым неотрицательным.

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

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

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

Но что и требовалось. Поэтому подходящих значений будет ровно то есть нечётное количество.

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

Это количество достигается, например, на наборе Здесь все неравенства из оценки обращаются в равенства, а значит, и оценка достигается.

Есть и другие примеры, в том числе, в которых все числа набора попарно взаимно простые, скажем,

Решение 1. Рассмотрим куб с тремя направляющими векторами рёбер вида где

Числа подобраны так, что

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2. Рассмотрим куб с тремя направляющими векторами рёбер вида

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

откуда заключаем, что принадлежит окружности

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Пусть — точка на прямой такая, что Докажем, что точки лежат на одной окружности.

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

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

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

Предположим противное — существуют такие многочлены и , что выполнено тождество .

_________________________________________________________________________________________________________________________________________________________________________________

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

У многочленов и нет общих корней, иначе это будет кратный корень суммы кубов, а у многочлена кратных корней нет.

Тогда многочлен имеет степень ) (старшие коэффициенты не сократятся) и не имеет корней, поскольку выражение равно 0 только при . Но такого делителя у многочлена нет.

_________________________________________________________________________________________________________________________________________________________________________________

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

Применим формулу суммы кубов:

При имеем , откуда , то есть .

Значит, многочлен имеет корнями числа , откуда его степень не меньше (поскольку он не тождественный ноль). В частности, у одного из многочленов и степень не меньше — не теряя общности, пусть у . Тогда, из равенства (*), степень многочлена равна 0 , то есть это ненулевая константа. Но это невозможно, так как из представления видно, что у этого многочлена старшая степень не меньше, чем максимум из степеней многочленов и , то есть, не меньше . (Можно сказать иначе: принимает сколь угодно большие значения, откуда - тоже, то есть, последний многочлен не может быть константой).

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Обозначим . Необходимо доказать, что .

Заметим, что

Далее, , как центральный и вписанный в окружность ( ), а также , как центральный и вписанный в окружность ( ). Тогда

______________________________________________________________________________________________________________________________________________________

Замечание.

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

Оценка.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример, подтверждающий точность полученной оценки

хороших клеток уже возможно.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

______________________________________________________________________________________________________________________________________________________

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

Обозначим сферу, проходящую через точки , с центром в точке , через , вписанную сферу пирамиды — через , а плоскость, проходящую через середины рёбер пирамиды — через .

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание.

Утверждение задачи является частным случаем следующего факта.

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

Оценка.

Можно считать, что первый наклеенный кусок — весь квадрат, от этого ничего не испортится. Считаем его нулевым. Докажем индукцией по утверждение:

_________________________________________________________________________________________________________________________________________________________________________________

После еще кусков между любыми двумя клетками есть путь с не более чем сменами цвета.

_________________________________________________________________________________________________________________________________________________________________________________

База при верна.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

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

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

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

Рассмотрим треугольник 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 группы, чтобы среди первых коробочек слева оказались все шарики основного цвета.

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

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

По теореме, обратной к теореме Менелая, для треугольника достаточно проверить, что

Поскольку и равны как касательные, достаточно проверить равенство

Но по свойству внешней биссектрисы

Так что проверяем равенство

Пусть и пересекают окружность в точках и соответственно. Запишем степени точек и относительно окружности

Осталось проверить равенство

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

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

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

Поэтому можно найти Так как и известны, отсюда определяется А значит и третий корень