Курчатов - задания по годам → .10 Курчатов 2023

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

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

1.

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

2.

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

Пример. Пусть Тогда, действительно, для любого

Оценка. По свойству модуля: Тогда получим такое неравенство:

Пусть является корнем тогда подставим его в это неравенство:

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

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

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

то Это означает, что у не может быть корней кратности , ведь иначе в окрестности любого из таких корней многочлен принимал бы значения разных знаков. Значит, каждый корень многочлена P(x) имеет кратность не менее а так как сумма кратностей корней не превосходит степень многочлена, корней у не более

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

Отметим, что — параллелограмм ( равен и параллелен поэтому искомый С другой стороны, из вписанности имеем

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

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

Пример. Возьмём числа и расставим их в следующем порядке:

Тогда НОДы будут

Оценка. Здесь и далее — это НОД Прежде всего отметим, что:

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

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

1.

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

2.

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

Заметим, что НОД двух различных нечётных чисел не больше половины от их разности, поскольку разность чётная делит НОД, при этом сам НОД нечётный.

Теперь снова рассмотрим случаи в зависимости от чётности

1.

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

2.

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

Оценка. Сначала сформулируем и докажем следующую лемму:

Лемма. Пусть — количество клеток некоторого цвета Тогда существует не более квадратов в которых клеток этого цвета хотя бы

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

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

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

Но так как каждая клетка покрашена в один цвет:

Значит,

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