Олимпиада по математике 10 класс — заключительный этап ВсОШ 2023/2024: задания и ответы

Решения — 1 день

Материалы для проведения заключительного этапа 50-й ВСЕРОССИЙСКОЙ МАТЕМАТИЧЕСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ 2023–2024 учебный год Первый день Нижний Новгород, 19–25 апреля 2024 г.

Москва, 2024

Сборник содержит материалы для проведения заключительного этапа 50-й Всероссийской олимпиады школьников по математике. Задания подготовлены Центральной предметно-методической комиссией по математике Всероссийской олимпиады школьников. Сборник составили: Н. Х. Агаханов, А. В. Антропов, С. Л. Берлов, И. И. Богданов, Н. Ю. Власова, П. А. Кожевников, А. С. Кузнецов, Е. Г. Молчанов, Ф. В. Петров, О. К. Подлипский, К. А. Сухов, Д. А. Терёшин, Д. Г. Храмцов, Г. Р. Челноков. А также: М. А. Дидин, И. А. Ефремов, К. А. Кноп, П. Ю. Козлов, Т. С. Коротченко, А. Д. Терёшин, И. И. Фролов, М. А. Туревский, А. И. Храбров. В скобках после каждой задачи указана фамилия её автора. Компьютерный макет: И. И. Богданов, А. И. Голованов.

© Авторы и составители, 2024 © И. И. Богданов, А. И. Голованов, 2024, макет

50-я Всероссийская математическая олимпиада школьников

10 класс 10.1. Пусть p и q — различные простые числа. Дана бесконечная убывающая арифметическая прогрессия, в которой встречается каждое из чисел p23 , p24 , q 23 и q 24 . Докажите, что в этой прогрессии обязательно встретятся числа p и q. (А. Кузнецов, методкомиссия)

Решение. Вычеркнем все нецелые числа из прогрессии (если они есть). Ясно, что после вычёркивания остаётся бесконечная убывающая арифметическая прогрессия, состоящая из целых чисел. Пусть её разность равна −d. Заметим, что q 23 − p23 делится на d, значит, d не делится на p, иначе q 23 должно будет делиться на p, что неверно. С другой стороны, d должно являться делителем числа p24 −p23 = p23 (p− − 1). Поскольку p и d взаимно просты, p − 1 делится на d. Далее, p23 − p делится на p − 1 (поскольку оно равно p(p − 1)(p21 + p20 + + . . . + 1)). Поэтому p23 − p делится на d, и, поскольку p < < p23 , получаем, что p лежит в нашей прогрессии. Аналогично, q лежит в этой прогрессии. 10.2. Дано нечётное число n ⩾ 3. В клетчатом квадрате 2n × 2n закрашивают 2(n − 1)2 клеток. Какое наибольшее количество трёхклеточных уголков можно гарантированно вырезать из незакрашенной клетчатой фигуры? (Г. Шарафетдинова) Ответ. 2n − 1. Решение. Оценка. Разобьём квадрат 2n × 2n на n2 квадратиков 2 × 2. Среди этих квадратиков не более 2(n − 1)2 /2 = (n − 1)2 квадратиков, в которых покрашено хотя бы 2 клетки. Остальных квадратиков 2 × 2 — не менее n2 −(n−1)2 = 2n−1 штук. Из каждого из них можно вырезать трёхклеточный уголок. Рис. 2 Пример. Построим пример индукцией по нечётным n ⩾ 1. При n = 1 закрашенных клеток нет, и можно вырезать один уголок. Для перехода выделим в квадрате внешнюю «рамку» ши8

Заключительный этап, 2023–2024 учебный год. Первый день

риной в две клетки. В этой рамке закрасим все 8(n − 2) клетки, примыкающие к внутренней границе рамки (см. рис. 2), а в квадрате внутри рамки закрасим клетки по предположению индукции. Общее количество закрашенных клеток равно 2(n − 3)2 + 8(n − 2) = 2(n − 1)2 . Осталось понять, сколько уголков можно вырезать в этом примере. Любой уголок из непокрашенных клеток целиком лежит либо в рамке, либо во внутреннем квадрате (таких по предположению 2(n − 2) − 1 = 2n − 5). Из рамки же нельзя вырезать более 4 уголков — каждый такой уголок должен содержать хотя бы 2 клетки одного из угловых квадратов 2 × 2, а двух уголков, пересекающихся с одним квадратом, вырезать нельзя. Значит, общее количество уголков не больше (2n − 5) + 4 = 2n − 1. 10.3. Дано натуральное число n. Илья задумал пару различных многочленов степени n (с вещественными коэффициентами), аналогично Саша задумал пару различных многочленов степени n. Лёня знает n; его цель — выяснить, одинаковые ли пары многочленов у Ильи и Саши. Лёня выбирает набор из k вещественных чисел x1 < x2 < . . . < xk и сообщает эти числа. В ответ Илья заполняет таблицу 2 × k: для каждого i = 1, 2, . . ., k он вписывает в две клетки i-го столбца пару чисел P (xi ), Q(xi ) (в любом из двух возможных порядков), где P и Q — задуманные им многочлены. Аналогичную таблицу заполняет Саша. При каком наименьшем k Лёня сможет (глядя на таблицы) наверняка добиться цели? (Л. Шатунов) Ответ. 2n + 1. Решение. Покажем, что при k = 2n (а тем более при k < < 2n) Лёня не сможет однозначно определить определить пару P , Q. Пусть он назвал x1 < x2 < . . . < x2n . Положим A = (x − −x1 )(x−x2 ) . . . (x−xn ), B = (x−xn+1 )(x−xn+2 ) . . . (x−x2n ), так что A(xi ) = 0 для i = 1, 2, . . ., n и B(xi ) = 0 для i = n + 1, n + 2, . . ., 2n. Тогда если Илья загадал P1 = A + 2B и Q1 = −A − 2B, то в i-м столбце таблицы будут числа ±2B(xi ) при i = 1, 2, . . ., n и числа ±A(xi ) при i = n + 1, n + 2, . . ., 2n. Но та же таблица годится для пары P2 = A − 2B и Q2 = −A + 2B, её мог загадать Саша. С другой стороны, покажем, что при k = 2n + 1 таблице 9

50-я Всероссийская математическая олимпиада школьников

Ильи может удовлетворять не более одной пары многочленов P , Q. Предположим противное, и есть две такие пары: P1 , Q1 и P2 , Q2 . Тогда P2 совпадает c P1 или Q1 хотя бы при n + 1 различных значениях аргумента, пусть, скажем, с P1 . Но тогда P1 и P2 — одинаковые многочлены (поскольку их разность — многочлен степени не выше n, имеющий не менее n + 1 различных корней). Из таблицы тогда получаем, что значения Q1 и Q2 совпадают в 2n + 1 точке, а тогда и Q1 = Q2 . 10.4. Дан выпуклый четырёхугольник ABCD, в котором ∠A + ∠D = = 90◦ , его диагонали пересекаются в точке E. Прямая ` пересекает отрезки AB, CD, AE и ED в точках X, Y , Z и T соответственно. Известно, что AZ = CE и BE = DT . Докажите, что длина отрезка XY не больше диаметра описанной окружности треугольника ET Z. (А. Кузнецов) Решение. Обозначим через ω окружность (ET Z) и через d — её диаметр. Поскольку BE = DT , то BT = BE +ET = DT + + ET = DE. Из условия ∠A + ∠D = 90◦ следует, что лучи AB и DC пересекаются в некоторой точке F под прямым углом (см. рис. 3). Проведем диаметр EB 0 в окружности (ABE). Поскольку ∠ABE > 90◦ , точки идут на окружности в порядке A − B − − E − B 0 . Тогда ∠AB 0 B = ∠AEB = ∠CED и ∠BAB 0 = 90◦ + + ∠F AC = ∠ECD. Следовательно, треугольники CED и AB 0 B 0 CE = AZ . Полученное подобны по двум углам, поэтому AB 0 = ED BT BB

равенство означает, что прямоугольные треугольники AB 0 Z и BB 0 T подобны по отношению катетов. Тогда ∠BT B 0 = ∠AZB 0 , поэтому точка B 0 лежит на окружности ω. Заметим, что AB — прямая Симсона точки B 0 для треугольника ZET , поскольку ∠B 0 AE = ∠B 0 BE = 90◦ . Тогда и проекция B 0 на прямую ZT тоже лежит на AB, то есть B 0 X ⊥ ZT . Рассуждая аналогично, мы получаем, что точка C 0 , диаметрально противоположная E на окружности (CED), лежит на окружности ω, а также C 0 Y ⊥ ZT . Таким образом, B 0 C 0 — хорда окружности ω, а X и Y — проекции точек B 0 и C 0 на прямую ZT , поэтому XY ⩽ B 0 C 0 ⩽ d, что и требовалось. Замечание 1. На самом деле B 0 C 0 — диаметр окружности (ET Z), что нетрудно установить счётом углов, но для решения 10

Заключительный этап, 2023–2024 учебный год. Первый день

C E E

X A

Y T

B0

Рис. 3 этого не требуется. Равенство XY = d достигается в том и только в том случае, когда исходный четырёхугольник — вписанный. Замечание 2. Приведём план другого подхода к задаче. Используем обозначения из приведённого выше решения, а также введём новые: x = BF , y = AB, z = CF , t = DC, k = DE , EB AE , p = ZT , α = ∠AED. Из теорем Менелая для 4EZT m= F C

и прямой AY B; 4EZT и прямой CY D находим: XZ = Y T = = p · kl 1− 1 . По теореме синусов для треугольника ZET : d = + 1. = sinp α , в силу сказанного выше XY = XZ+Y Z+ZT = p· kl kl − 1 − 1 (?). Из Таким образом, достаточно доказать, что sin α ⩽ kl kl + 1

теорем Менелая для 4AF C и прямой BED; 4BF D и пряt(x + y) y(z + t) , l = , отсюда zy xt (x + y)(z + t) − 1 = (x + y)(z + t) − xz . kl = и kl xz kl + 1 (x + y)(z + t) + xz

мой AEC легко видеть, что k =

Обозначим ∠F AC = β, ∠F DB = γ, тогда α = = 90◦ + β + γ. Значит, sin α = cos γ cos β − sin γ sin β = = p

(x + y)(z + t) − xz , последнее равенство получает(x2 + (z + t)2 )(z 2 + (y + t)2 )

ся из прямоугольных треугольников AF C и BF D. Остаётся заp 2 метить, что (x + (z + t)2 )(z 2 + (y + t)2 ) ⩾ xz +(z +t)(y +t) по 11

50-я Всероссийская математическая олимпиада школьников

неравенству Коши-Буняковского-Шварца, получаем в точности требуемое неравенство (?).

12

КРИТЕРИИ ПРОВЕРКИ 10 КЛАССА ЗАДАЧА КРИТЕРИЙ

БАЛЛ

10.1 Проблемы со знаком разности прогрессии, не влияющие на решение

Баллы не снимаются

10.1 Без обоснования считается, что разность прогрессии целая

Баллы не снимаются

Доказано, что разность прогрессии рациональна, или задача сведена к целой 10.1 разности прогрессии

Баллы не добавляются

10.1 Неверно доказана делимость p-1 на d, и из этого верно выведено утв. задачи В предположении p>q доказано, что в прогрессии встречается p; второе 10.1 утверждение не доказано

Баллы не добавляются 2

10.2 Только полная оценка

10.2 Только полный пример с обоснованием

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

1 Штраф 1 балл

10.3 только доказательство достаточности n=2k+1

Утверждается, что для построения примера в случае k=2n достаточно найти пары многочленов (P_1, Q_1) и (P_2,Q_2) такие, что P_1(t)=P_2(t) для n данных 0 баллов за 10.3 точек и P_1(t)=Q_2(t) для n оставшихся точек, других продвижений нет эту часть 10.3 Замечено только, что можно рассматривать только k=2n (а не k=< 2n)

0 баллов за эту часть

10.3 Обсужден только случай k=2n, случай k<2n не рассмотрен

баллы не снимались

10.3 разбор конкретных значений n 10.3 В примере для k=2n некоторые многочлены имеют степень меньше n

0 снимается 1 балл

Начальные продвижения, включая достроение до прямоугольного AFB, 10.4 построение центра (EZT) и понимание, что он на серпере к BD, и т.д.

10.4 Огрублено XY<AD

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

Доказано, что XZ = TY (только написанные теоремы Менелая без выводов -- не 10.4 достаточно для получения балла) 10.4 Недоведенный счет (координаты и т.д)

1 0

Далее обозначено: Пусть длины прыжков a_0=eps, a_1, ..., a_7 (обычно 10.5 a_0=eps -- другое по сути число). В работе имеется идея кратного увеличения длин прыжков a_1, a_2, ..., a_7 10.5 (например, степени двойки)

1 балл

В работе имеется идея взять одним из прыжков число меньше 1 (a_0= eps), с 10.5 помощью которого <<допрыгивать до края дощечки>>.

1 балл

10.5 В работе считается, что длины отрезков --- целые числа

не более 1 балла

В работе не появляются конкретные неравенства на a_0= eps (например, в работе вместо неравенств написано <<достаточно маленькое>>, <<бесконечно не более 2 10.5 маленькое>>, <<очень маленькое, например, 10^{-100}>> и т.п.) баллов Выбирается наибольшее a_i<C и в качестве нужного прыжка берётся a_{i+1}, 10.5 при этом множество a_i<C может быть пусто.

снимается не менее 1 балла

снимается не В работе верно сформулировано неравенство, которое надо проверить, однако менее 2 10.5 проверка этого неравенства или неверна, или отсутствует баллов

В работе a_{i+1} выбирается по ходу выполнения алгоритма как сумма двух длин соседних отрезков, когда a_i уже не хватает. При этом утверждается, что 10.5 a_{i+1} >= 2a_i. В некоторых работах это неравенство неверно.

снимается не менее 3 баллов

Только счет углов и переформулировки в терминах углов (в частности, посчитан угол EMF, или если задача сведена к равенству угла EBF и угла 36010.6 2D ), достраивание конструкции до "трезубца" и пр.

баллы не добавляются

(A) Рассмотрение E'B'F' (как в решении А) и сведение задачи к нахождению угла E'B'F' (только переформулировки после гомотетии с центром D не 10.6 достаточно) (критерий не суммируется с другими)

2 балла

(B1) задача сведена к изогональности BE и BF отн. ABC (или к эквивалентному 10.6 равенству углов)

1 балл

(B1') задача сведена к подобию ABE и CBF(явно указано, что нам нужно подобие, или отношение/произведение соответствующих сторон) (не 10.6 суммируется с (B1))

2 балла

(B2) Доказано AE AD = CF CD

1 балл

10.6 (B2') Доказано подобие ABE и CBF (не суммируется с (B2) )

2 балла

10.6 Не рассмотрено различное расположение точек, не влияющее на ход решения незавершенный счет (в синусах, комплексных, недостаточно положений в 10.6 "методе движения точек" и пр.)

не снимаем 0

10.7 Введение графа, доказательство ацикличности, структура графа

10.7 Оценено количество рёбер

"Причёсывание" задачи: выкидывание изолированных отрезков, продление 10.7 отрезков и тд

10.7 Недоведённый подсчёт всех пар подмножеств из x_1 и x_2 отрезков

Разборы частных случаев: x_1=1, чередуются цвета отрезков, одновременно 10.7 y_1 >= 2x_1 и y_2 >= 2x_2 и другие

Доказано только, что каждую пару белых отрезков пересекает не более чем 10.7 один чёрный отрезок

10.7 Равносильные преобразования доказываемого неравенства Рассмотрены циклические сдвиги по x_1 отрезку, недоведённая попытка 10.7 двойного подсчёта

10.8 Сведение задачи к получению всех нечётных чисел

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

Решения — 2 день

Материалы для проведения заключительного этапа 50-й ВСЕРОССИЙСКОЙ МАТЕМАТИЧЕСКОЙ ОЛИМПИАДЫ ШКОЛЬНИКОВ 2023–2024 учебный год Второй день Нижний Новгород, 19–25 апреля 2024 г.

Москва, 2024

Сборник содержит материалы для проведения заключительного этапа 50-й Всероссийской олимпиады школьников по математике. Задания подготовлены Центральной предметно-методической комиссией по математике Всероссийской олимпиады школьников. Сборник составили: Н. Х. Агаханов, А. В. Антропов, С. Л. Берлов, И. И. Богданов, Н. Ю. Власова, П. А. Кожевников, А. С. Кузнецов, Е. Г. Молчанов, Ф. В. Петров, О. К. Подлипский, К. А. Сухов, Д. А. Терёшин, Д. Г. Храмцов, Г. Р. Челноков. А также: М. А. Дидин, И. А. Ефремов, К. А. Кноп, П. Ю. Козлов, Т. С. Коротченко, А. Д. Терёшин, И. И. Фролов, М. А. Туревский, А. И. Храбров. В скобках после каждой задачи указана фамилия её автора. Компьютерный макет: И. И. Богданов, А. И. Голованов.

© Авторы и составители, 2024 © И. И. Богданов, А. И. Голованов, 2024, макет

Заключительный этап, 2023–2024 учебный год. Второй день

10 класс 10.5. Дана прямолинейная дорога, выложенная из зелёных и красных дощечек (дорога — отрезок, разбитый на отрезки-дощечки). Цвета дощечек чередуются; первая и последняя дощечки — зелёные. Известно, что длины всех дощечек больше сантиметра и меньше метра, а также что длина каждой следующей дощечки больше предыдущей. Кузнечик хочет пропрыгать вперёд по дороге по этим дощечкам, наступив на каждую зелёную дощечку хотя бы один раз и не наступив ни на одну красную дощечку (или границу между соседними дощечками). Докажите, что кузнечик может сделать это так, чтобы среди длин его прыжков встретилось не более 8 различных значений. (Т. Коротченко) Решение. Считаем, что дощечки выложены на числовой прямой. Примем 1 = 1 см. Возьмем 0 < ε < 0, 01 такое, что разность длин любой пары соседних дощечек больше 10ε. Отметим на прямой бесконечную в обе стороны арифметическую прогрессию с разностью ε так, чтобы концы дощечек не были отмечены. Кузнечик будет прыгать только по отмеченным точкам, и длины его прыжков будут из множества {ε, `, 2`, 4`, 8`, 16`, 32`, 64`}, где ` = N ε, а натуральное N подберём так, что ` < 2 и 64` > 101. Стратегия кузнечика будет такой: прыгать вправо по зелёной дощечке на ε пока возможно, и далее перепрыгивать очередную красную дощечку прыжком минимальной возможной длины (такая длина найдётся, поскольку длина самого длинного прыжка больше 100 + ε). Итак, пусть сделан прыжок длины 2d из зелёного отрезка через очередной красный отрезок [a, b]. Нам остаётся убедиться, что после этого прыжка кузнечик окажется в следующем зелёном отрезке [b, c]. Предположим, что это не так, и кузнечик из точки a − x, где 0 < x < ε перепрыгнул в точку a−x+2d > c. Видим, что 2d > (c−b)+(b−a) > 2, значит, в множестве длин прыжков кузнечика есть длина d. Далее, по выбору ε, имеем (c − b) > (a − b) + 10ε, поэтому можем оценить 2d > (c − b) + (b − a) > 2(b − a) + 10ε. Видим, что d > (b − a) + ε, а значит, кузнечик мог из точки a − x перепрыгнуть красный отрезок [a, b] прыжком более коротким, чем 2d. Противоречие. 9

50-я Всероссийская математическая олимпиада школьников

10.6. Дан параллелограмм ABCD. Точка M — середина дуги ABC окружности, описанной около треугольника ABC. На отрезке AD отмечена точка E, а на отрезке CD — точка F . Известно, что M E = M D = M F . Докажите, что точки B, M , E и F лежат на одной окружности. (А. Терёшин) Первое решение. Пусть ∠ADC = x. Из равнобедренных треугольников DM E и DM F (или из того, что M — центр окружности (DEF )) имеем ∠EM F = 360◦ − 2x (см. рис. 3). Для решения задачи остаётся понять, что тому же равен ∠EBF . При гомотетии с центром D и коэффициентом 1/2 точки E, F , B перейдут соответственно в E 0 , F 0 , B 0 — середины отрезков DE, DF и DB. Вместо ∠EBF найдём ∠E 0 B 0 F 0 , заметив, что E 0 и F 0 — проекции M на AD и CD, а B 0 — центр параллелограмма, или середина AC, тем самым, B 0 — проекция M на AC. Видим, что M , E 0 , A, B 0 лежат на одной окружности с диаметром M A. Отсюда ∠DE 0 B 0 = ∠AM B 0 = ∠AM C/2 = ∠ABC/2 = x/2. Аналогично ∠DF 0 B 0 = x/2. Из четырёхугольника E 0 B 0 F 0 D видим, что ∠E 0 B 0 F 0 = 360◦ − x − x/2 − x/2 = 360◦ − 2x, что и требовалось. X X B C M M F MB B0

A E E

E0

D Рис. 3

F0

F F

A E E

D D Рис. 4

Второе решение. Достаточно доказать равенство углов ∠ABE = ∠CBF (т.е. изогональность BE и BF относительно AB, BC). Действительно, тогда M будет лежать на внешней биссектрисе угла EBF и на серединном перпендикуляре к EF , а значит, будет совпадать с серединой дуги (EBF ). Равенство углов ∠ABE = ∠CBF , в свою очередь, эквивалентно подобию ABE ∼ CBF . Докажем это подобие. 10

Заключительный этап, 2023–2024 учебный год. Второй день

Отметим на луче AB за точкой B точку X так, что BX = = BC, а на луче CB за точкой B точку Y так, что BY = BA. Легко понять, что треугольники BM C и BM X равны по двум сторонам и углу между ними. Тогда M X = M C = M A. Рассмотрим серединный перпендикуляр к DF , тогда он является перпендикуляром к параллельной прямой AX, а поскольку M A = M X, то он же является серединным перпендикуляром к AX. Таким образом, трапеция ADF X равнобедренная, а раз ABCD — параллелограмм, то CXBF — также равнобедренная трапеция, причём CB = BX = XF и ∠XBC = 180◦ − − ∠ABC. Аналогичное получим для трапеции AY BE. Видим, что AY BE ∼ CXBF , откуда следует нужное нам ABE ∼ CBF . Замечание. Требуемое в решении 2 подобие ABE ∼ CBF можно доказать и по-другому — установив равенство AE · BC = = CF · AB. Последнее можно сделать, например, счётом в синусах через элементы треугольника ABC, выразив проекцию AM на AD, далее выразив отрезок AE и т.д. Имеются и другие вычислительные решения, в том числе с использованием комплексных чисел. 10.7. Пусть даны натуральные числа x1 и x2 . На прямой даны y1 белых отрезков и y2 чёрных отрезков, при этом y1 ⩾ x1 и y2 ⩾ x2 . Известно, что никакие два отрезка одного цвета не пересекаются (даже не имеют общих концов). Также известно, что при любом выборе x1 белых отрезков и x2 чёрных отрезков обязательно какая-то пара выбранных отрезков будет пересекаться. Докажите, что (y1 − x1 )(y2 − x2 ) < x1 x2 . (Г. Челноков)

Первое решение. Пронумеруем белые отрезки слева направо как w1 , w2 , . . . , wy1 , а чёрные — как b1 , b2 , . . . , by2 . Для каждого чёрного отрезка bj назовём его силой S(bj ) количество индексов i ⩽ y1 − 1 таких, что bj пересекается как с wi , так и с wi+1 . Если с какой-то парой (wi , wi+1 ) пересекаются два чёрных отрезка, то они имеют общую точку, что невозможно по условию. Поэтому каждая такая пара учтена в силе не более, чем одного чёрного отрезка, а значит, 11

50-я Всероссийская математическая олимпиада школьников y2 X

S(bj ) ⩽ y1 − 1.

j=1

Рассмотрим следующие y1 групп, состоящих из x1 белых отрезков каждая: при 0 ⩽ i ⩽ y1 − x1 группа Gi состоит из отрезков wi+1 , wi+2 , . . . , wi+x1 , а при y1 − x1 + 1 ⩽ i ⩽ y1 − − 1 группа Gi состоит из отрезков wi+1 , wi+2 , . . . , wy1 , а также из w1 , w2 , . . . , wi+x1 −y1 (иначе говоря, каждая группа состоит из x1 последовательных отрезков в циклическом порядке). Для группы Gi обозначим через N (Gi ) количество чёрных отрезков, не пересекающихся ни с одним из отрезков в Gi . По условию, N (Gi ) ⩽ x2 − 1; поэтому Σ :=

yX 1 −1

N (Gi ) ⩽ y1 (x2 − 1).

i=0

С другой стороны, каждый чёрный отрезок bj пересекается максимум с 1+S(bj ) белыми отрезками, и все эти белые отрезки расположены подряд. Тогда количество групп, содержащих хотя бы один из этих белых отрезков, не превосходит 1 + S(bj ) + + (x1 − 1) = S(bj ) + x1 . Поэтому отрезок bj учтён хотя бы в y1 − (S(bj ) + x1 ) числах вида N (Gi ). Поэтому y2 y2 X X S(bj ) ⩾ (y1 − S(bj ) − x1 ) = y2 (y1 − x1 ) − Σ⩾ j=1

j=1

⩾ y2 (y1 − x1 ) − (y1 − 1). Из полученных двух оценок на Σ вытекает, что y1 (x2 −1) ⩾ y2 (y1 −x1 )−(y1 −1) ⇐⇒ (y1 −x1 )(y2 −x2 ) ⩽ x1 x2 −1, что и требовалось доказать. Второе решение. Предположим, что утверждение задачи для некоторых x1 , x2 , y1 , y2 неверно: (y1 − x1 )(y2 − x2 ) ⩾ x1 x2 , и при этом условии сумма y1 + y2 — минимальная возможная. Без ограничения общности тогда y1 − x1 ⩾ x1 . Возьмём x1 -й слева белый отрезок W и (y2 − x2 )-й слева чёрный отрезок B. У какого-то из них правый конец левее. 1) Пусть правый конец W левее (или концы совпадают).

12

Заключительный этап, 2023–2024 учебный год. Второй день

Тогда правые x2 чёрных отрезков не пересекаются с левыми x1 белыми. Противоречие. 2) Пусть правый конец B левее. Выкинем все белые отрезки слева от W (включая его) и все чёрные отрезки слева от B (включая его). Оставшиеся белые отрезки (их хотя бы x1 ) не пересекаются с выкинутыми y2 −x2 чёрными; отсюда уже следует, что y2 − x2 < x2 . Положим x01 = x1 , y10 = y1 − x1 ⩾ x01 , x02 = x2 − (y2 − x2 ) 0 и y2 = y2 − (y2 − x2 ) = x2 ⩾ x02 ; тогда осталось y10 белых и y20 чёрных отрезков. Рассмотрим любые x01 оставшихся белых и x02 оставшихся чёрных отрезков. Если среди них нет пересекающихся, то, добавив к ним все выкинутые чёрные отрезки, получим набор из x1 = x01 белых и x2 = x02 + (y2 − x2 ) чёрных отрезков исходного набора, среди которых нет пересекающихся; это невозможно. Значит, оставшийся набор удовлетворяет условию (для новых чисел x01 , y10 , x02 и y20 ), при этом в нём меньше отрезков, чем в исходном, поэтому 0 < x01 x02 − (y10 − x01 )(y20 − x02 ) = = x1 (2x2 − y2 ) − (y1 − 2x1 )(y2 − x2 ) = = x1 x2 − (y1 − x1 )(y2 − x2 ) ⩽ 0. Противоречие. Замечание. Отметим, что при x1 = x2 = 1 утверждение задачи превращается в двухцветную (одномерную) теорему Хелли. 10.8. Дано натуральное n > 2. Маша записывает по кругу n натуральных чисел. Далее Тая делает такую операцию: между каждыми двумя соседними числами a и b она пишет некоторый делитель числа a + b, больший 1; затем Тая стирает исходные числа и получает новый набор из n чисел, стоящих по кругу. Всегда ли Тая может выполнять операции таким образом, чтобы через несколько операций все числа оказались равными? (Т. Коротченко)

Ответ. Да. Решение. Будем наращивать множество ситуаций, в которых Тая побеждает (т.е. сможет получить n равных чисел). (1) Пусть у нас n нечётных чисел. 13

50-я Всероссийская математическая олимпиада школьников

Тогда за одну операцию можно получить n двоек. (2) Пусть никакая сумма двух соседних чисел не является степенью двойки. Тогда за одну операцию можно получить ситуацию (1). (3) Пусть среднее арифметическое s всех чисел не равно степени двойки. Покажем, что сможем прийти к ситуации (2). Воспользуемся следующей леммой, доказательство которой приведём в конце решения. Лемма. Пусть a1 , a2 , . . . , an — вещественные числа, s — их среднее арифметическое. За один ход меняем набор a1 , a2 , a2 a2 + a3 a1 . . . , an на a1 + , , . . . , an + . Тогда для любого ε > 0 2 2 2 через несколько ходов все числа будут лежать в интервале (s− − ε, s + ε). Ясно, что s > 1. Выберем ε > 0 так, чтобы интервал (s − ε, s + ε) целиком помещался между соседними степенями двойки: 2t−1 < s − ε < s + ε < 2t для некоторого натурального t. Будем проводить много раз операцию замены пары соседней на их сумму. Тогда, согласно лемме, найдётся N такое, что после N операций все числа будут лежать в интервале (2N (s − ε), 2N (s + ε)), а значит, в интервале между соседними степенями двойки 2N · 2t−1 и 2N · 2t . Значит, после (N − 1) операции выполнялось условие (2). (4) Пусть все числа не меньше 2. Если мы не в ситуации (2), то есть пара соседей a, b, сумма которых равна 2t , где t ⩾ 2 — натуральное. Попробуем сделать следующую операцию произвольно, только a и b заменим на число 2. Пусть в такой попытке мы не пришли в ситуацию (3), то есть получили ситуацию, в которой среднее арифметическое s равно степени двойки. Тогда сделаем другую попытку, в которой все пары меняются так же, только только a и b заменяются на 4. 2 , поэтому По сравнению с первой попыткой s увеличилось на n мы окажемся в ситуации (3). (5) Пусть набор исходных чисел произвольный. Тогда после одной операции имеем ситуацию (4). Доказательство леммы. Сделаем переобозначения, пусть 14

Заключительный этап, 2023–2024 учебный год. Второй день

s+x0 , s+x1 , . . . , s+xn — данные числа, так что x0 +. . .+xn = 0. Пусть M = max{|x0 |, . . . , |xn |}. Ясно, что после хода M не увеличится. Достаточно понять, что что через некоторое количество k ходов этот максимум отклонения станет не более λM для некоторого фиксированного 0 < λ < 1. Ниже увидим, что можn но положить k = n и λ = 2 −2nn − 1 . Через n ходов у нас будет набор s + y0 , s + y1 , . . . , s + yn , где y0 = 21n (x0 + Cn1 x1 + Cn2 x2 + . . . + Cnn−1 xn−1 + xn ) и т.д. Так как x0 + x1 + . . . + xn = 0, имеем x0 + Cn1 x1 + Cn2 x2 + . . . + +Cnn−1 xn−1 +xn = (Cn1 −1)x1 +(Cn2 −1)x2 +. . .+(Cnn−1 −1)xn−1 . n Отсюда |y0 | ⩽ 21n ((Cn1 − 1) + . . . + (Cnn−1 − 1))M = 2 −2nn − 1 M . n Аналогично все |yi | ⩽ 2 −2nn − 1 M .

15

КРИТЕРИИ ПРОВЕРКИ 10 КЛАССА ЗАДАЧА КРИТЕРИЙ

БАЛЛ

10.1 Проблемы со знаком разности прогрессии, не влияющие на решение

Баллы не снимаются

10.1 Без обоснования считается, что разность прогрессии целая

Баллы не снимаются

Доказано, что разность прогрессии рациональна, или задача сведена к целой 10.1 разности прогрессии

Баллы не добавляются

10.1 Неверно доказана делимость p-1 на d, и из этого верно выведено утв. задачи В предположении p>q доказано, что в прогрессии встречается p; второе 10.1 утверждение не доказано

Баллы не добавляются 2

10.2 Только полная оценка

10.2 Только полный пример с обоснованием

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

1 Штраф 1 балл

10.3 только доказательство достаточности n=2k+1

Утверждается, что для построения примера в случае k=2n достаточно найти пары многочленов (P_1, Q_1) и (P_2,Q_2) такие, что P_1(t)=P_2(t) для n данных 0 баллов за 10.3 точек и P_1(t)=Q_2(t) для n оставшихся точек, других продвижений нет эту часть 10.3 Замечено только, что можно рассматривать только k=2n (а не k=< 2n)

0 баллов за эту часть

10.3 Обсужден только случай k=2n, случай k<2n не рассмотрен

баллы не снимались

10.3 разбор конкретных значений n 10.3 В примере для k=2n некоторые многочлены имеют степень меньше n

0 снимается 1 балл

Начальные продвижения, включая достроение до прямоугольного AFB, 10.4 построение центра (EZT) и понимание, что он на серпере к BD, и т.д.

10.4 Огрублено XY<AD

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

Доказано, что XZ = TY (только написанные теоремы Менелая без выводов -- не 10.4 достаточно для получения балла) 10.4 Недоведенный счет (координаты и т.д)

1 0

Далее обозначено: Пусть длины прыжков a_0=eps, a_1, ..., a_7 (обычно 10.5 a_0=eps -- другое по сути число). В работе имеется идея кратного увеличения длин прыжков a_1, a_2, ..., a_7 10.5 (например, степени двойки)

1 балл

В работе имеется идея взять одним из прыжков число меньше 1 (a_0= eps), с 10.5 помощью которого <<допрыгивать до края дощечки>>.

1 балл

10.5 В работе считается, что длины отрезков --- целые числа

не более 1 балла

В работе не появляются конкретные неравенства на a_0= eps (например, в работе вместо неравенств написано <<достаточно маленькое>>, <<бесконечно не более 2 10.5 маленькое>>, <<очень маленькое, например, 10^{-100}>> и т.п.) баллов Выбирается наибольшее a_i<C и в качестве нужного прыжка берётся a_{i+1}, 10.5 при этом множество a_i<C может быть пусто.

снимается не менее 1 балла

снимается не В работе верно сформулировано неравенство, которое надо проверить, однако менее 2 10.5 проверка этого неравенства или неверна, или отсутствует баллов

В работе a_{i+1} выбирается по ходу выполнения алгоритма как сумма двух длин соседних отрезков, когда a_i уже не хватает. При этом утверждается, что 10.5 a_{i+1} >= 2a_i. В некоторых работах это неравенство неверно.

снимается не менее 3 баллов

Только счет углов и переформулировки в терминах углов (в частности, посчитан угол EMF, или если задача сведена к равенству угла EBF и угла 36010.6 2D ), достраивание конструкции до "трезубца" и пр.

баллы не добавляются

(A) Рассмотрение E'B'F' (как в решении А) и сведение задачи к нахождению угла E'B'F' (только переформулировки после гомотетии с центром D не 10.6 достаточно) (критерий не суммируется с другими)

2 балла

(B1) задача сведена к изогональности BE и BF отн. ABC (или к эквивалентному 10.6 равенству углов)

1 балл

(B1') задача сведена к подобию ABE и CBF(явно указано, что нам нужно подобие, или отношение/произведение соответствующих сторон) (не 10.6 суммируется с (B1))

2 балла

(B2) Доказано AE AD = CF CD

1 балл

10.6 (B2') Доказано подобие ABE и CBF (не суммируется с (B2) )

2 балла

10.6 Не рассмотрено различное расположение точек, не влияющее на ход решения незавершенный счет (в синусах, комплексных, недостаточно положений в 10.6 "методе движения точек" и пр.)

не снимаем 0

10.7 Введение графа, доказательство ацикличности, структура графа

10.7 Оценено количество рёбер

"Причёсывание" задачи: выкидывание изолированных отрезков, продление 10.7 отрезков и тд

10.7 Недоведённый подсчёт всех пар подмножеств из x_1 и x_2 отрезков

Разборы частных случаев: x_1=1, чередуются цвета отрезков, одновременно 10.7 y_1 >= 2x_1 и y_2 >= 2x_2 и другие

Доказано только, что каждую пару белых отрезков пересекает не более чем 10.7 один чёрный отрезок

10.7 Равносильные преобразования доказываемого неравенства Рассмотрены циклические сдвиги по x_1 отрезку, недоведённая попытка 10.7 двойного подсчёта

10.8 Сведение задачи к получению всех нечётных чисел

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