Высшая проба 2021

Оценка.

_________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Первая равносильность заслуживает пояснений: из уравнения если что и то невозможно поскольку многочлены взаимно-просты. Если же то деление на него является равносильным переходом, а однозначно находится из (*). Второй переход: просто поделили на Осталось заметить, что это в точности производная

______________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

Пример.

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

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

а). Из приведенных выше рассуждений следует система неравенств (самая левая)

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

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

_________________________________________________________________________________________________________________________________________________________________________________

б) Действуя аналогично, имеем:

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

Будем называть последовательность, удовлетворяющую условию задачи ПУУЗ.

Заметим, что следующая операция из ПУУЗ делает ПУУЗ: из последовательности выкидываем первый член, а все остальные делим на 2. В самом деле, все члены остались плюс или минус степенями двойки, и положительных все еще бесконечно. Назовем эту операцию сокращением.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для всех натуральных чисел, меньших . Рассмотрим и ПУУЗ . Если четное — представим в виде суммы нескольких различных членов сокращения , этому представлению соответствует представление в виде суммы различных членов . Если нечетное -— вычтем из него первый член , (который равен 1 или -1 ) и результат поделим пополам. Мы получили одно из чисел , оно натуральное и строго меньше , значит для него уже доказано, что оно представляется в виде суммы различных членов произвольной ПУУЗ, в частности — сокращения . Снова строим соответствующее представление в виде суммы различных членов .

а) Цветов не может быть больше 42, иначе есть цвет, в который покрашен только один дом, тогда домов этого цвета ни в каком отрезке не может быть строго больше, чем любого другого.

_________________________________________________________________________________________________________________________________________________________________________________

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

Назовем 38-блоком следующую конструкцию: подряд стоят 38 домов, пары домов на расстоянии 19 (т.е. такие, между которыми ровно 18 других домов)покрашены в один цвет, и больше этого цвета домов нет (не только в блоке но вообще из участвующих домов); 2-блоком назовем стоящие подряд два дома, покрашенные в уникальный цвет. 84 дома надо раскрасить так: 2-блок, 38-блок, два 2-блока, 38-блок, 2-блок.

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

_________________________________________________________________________________________________________________________________________________________________________________

б) Этот же пример позволяет реализовать 42 цвета на 86 домах — в конец добавим еще два дома, цвет которых совпадает с последним 2-блоком. Теперь постараемся доказать оценку в условиях данного пункта.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Докажем еще два полезных неравенства: — иначе нет отрезка из 20 домов, в который попали оба из и — иначе каждый отрезок, содержащий , также содержит или или .

_________________________________________________________________________________________________________________________________________________________________________________

Среди первых 20 номеров ровно одна -шка, это : иначе, если там есть и , среди домов от 1 до 20 есть два дома второго цвета, тогда для первого цвета нет отрезка, в котором его больше чем любого другого (поскольку только отрезок содержит два дома первого цвета, но он содержит и два дома второго). Значит, среди первых 20 домов ровно 19 -шек. Значит, из соответствующих им -шек 18 лежат среди 19 номеров от 21 до 39 , то есть там максимум одна -шка, это может быть только . Мы доказали, что . Повторив то же самое рассуждение с другого конца, получим, что . Но это противоречит неравенству (частный случай доказанного выше для ).

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

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

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

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

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

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

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

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

Если лежит в , то все при — тоже. Так что теперь можем без ограничения общности считать, что лежит в угле и вне круга .

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

Соответственно, если все точки лежат в но не в , то все вектора равны .

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

Итак, без ограничения общности можно считать, что попала в .

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Если сложить равенства и к полученному прибавить то мы получим равенство Или же То есть сумма двух целых неотрицательных равна а значит либо одно второе либо оба равны Осталось перебрать и написать ответ.