Тема Заключительный этап ВсОШ

Закл (финал) 10 класс

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела заключительный этап всош

Разделы подтемы Закл (финал) 10 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#126725Максимум баллов за задание: 7

Найдите все натуральные $n,$ для которых существует такое чётное натуральное $a,$ что число

2 n (a− 1)(a − 1)...(a − 1)

является точным квадратом.

Источники: ВСОШ, ЗЭ, 2025, 9.3 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте сначала вручную разобраться с n = 1, 2, 3. Для этих случаев достаточно вспомнить утверждение о том, что если произведение двух взаимно простых чисел — квадрат, то каждое из них также является квадратом. В частности, при n = 3 надо поработать с нодами скобок a - 1, a + 1, a² + a + 1. Быть может, этот ход мыслей можно развить и для больших n?

Подсказка 2:

Итак, скорее всего вы поняли, что n = 1, 2 подойдёт, а n = 3 — нет. Чем остальные случаи отличаются. Например, если n > 3, то оно находится между двумя натуральными степенями двойки. То есть существует такое натуральное k, что 2^k ≤ n < 2^{k + 1}. Подумайте, как это можно использовать.

Подсказка 3:

Если записать скобку a^{2^k} – 1 как (a^{2^{k – 1}} – 1)(a^{2^{k – 1}} + 1), то становится ясно, что все произведение состоит из скобки a^{2^{k – 1}} + 1 и скобок вида a^m – 1. А как насчёт того, чтобы посмотреть на нод выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с произвольной скобкой a^m – 1?

Подсказка 4:

Нод второго выражения и a^m – 1 кратен ноду первого выражения и a^m - 1. Чтобы было проще работать, вот вам интересный факт: нод второй скобки и a^m – 1 равен a^нод(2^k, m) – 1. Осталось поработать с нодом 2^k и m.

Подсказка 5:

Исходя из выбора k, ясно, что нод 2^k и m не превышает 2^{k – 1}. Попробуйте теперь показать, что ноды выражений a^{2^{k – 1}} + 1 и a^{2^k} – 1 с a^m – 1 совпадают. Кажется, это раскроет идею подсказки 3.

Подсказка 6:

Стало быть, a^{2^{k – 1}} + 1 — точный квадрат. А вас это не смущает?

Показать ответ и решение

Заметим, что для $n= 1$ подойдёт $a =10.$ Для $n =2$ подойдёт $a= 8.$

Предположим, что для $n =3$ нашлось требуемое число $a.$ Тогда число

2 3 3 2 (a − 1)(a − 1)(a − 1)= (a− 1) (a +1)(a + a+ 1)

является точным квадратом. Поскольку

2 a + a+ 1= a(a+ 1)+1,

числа $a+ 1$ и $a2+ a+ 1$ взаимно просты. Раз число $a+1$ нечётно, числа $a+ 1$ и $a− 1$ также взаимно просты. Следовательно, числа $a+ 1$ и $(a− 1)(a2+a +1)$ — точные квадраты. В частности, число $a+ 1$ при делении на 3 может давать лишь остаток 0 или 1, а тогда число $a− 1$ не делится на 3. Отсюда

2 НО Д(a− 1,a + a+1)= НОД (a − 1,(a +2)(a − 1)+ 3)= НО Д(a − 1,3)=1,

значит, числа $a− 1$ и $a2 +a+ 1$ также являются точными квадратами. Но второе являться квадратом не может, поскольку

a2 < a2 +a+ 1< (a+1)2.

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

Осталось доказать, что требуемого $a$ не существует при $n ≥4.$ Предположим, что такое $a$ нашлось. Возьмём такое натуральное $k ≥2,$ что $2k ≤n < 2k+1.$ Поскольку

a2k − 1= (a2k−1 − 1)(a2k−1 + 1),

число

(a− 1)(a2 − 1)...(an− 1)

представляется в виде произведения $2k−1 a +1$ и нескольких множителей вида $m a − 1,$ где $1≤ m ≤n$ и $k m ⁄=2 .$

Докажем, что множитель $2k−1 a +1$ взаимно прост со всеми остальными множителями в этом разложении. Пусть $2k−1 a + 1$ и $am − 1$ имеют некоторый общий делитель $d.$ Тогда и НОД $k a2 − 1$ и $am − 1$ кратен $d.$ Но

k k НОД(a2 − 1,am− 1)= aНОД(2 ,m)− 1.

Поскольку $k m ⁄= 2$ и $k+1 m ≤n < 2 ,$ число $m$ не может делиться на $k 2 .$ Таким образом, $k Н ОД(2,m )$ — степень двойки, не превосходящая $k−1 2 .$ Следовательно, $2k−1 a − 1$ делится на НОД $2k a − 1$ и $m a − 1,$ а, значит, делится и на $d.$ Поскольку $a$ чётно, числа $2k−1 a − 1$ и $2k−1 a + 1$ не имеют общих делителей, отличных от 1, значит, $d= 1,$ что и требовалось.

Множитель $2k−1 a + 1$ взаимно прост со всеми остальными множителями в произведении, являющемся точным квадратом, поэтому он сам является точным квадратом. Тогда $k−1 a2 +1$ и $k−1 a2$ — отличающиеся на 1 квадраты натуральных чисел, что невозможно. Значит, наше предположение неверно, и для $n≥ 4$ требуемых чисел $a$ не найдётся.

Ответ:

$n =1$ и $n =2$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#127158Максимум баллов за задание: 7

Дано натуральное число $n.$ Натуральные числа $1,2,...,n$ выписывают на доске в строчку в некотором порядке. У каждых двух стоящих рядом чисел вычисляют их НОД (наибольший общий делитель) и записывают этот НОД на листке. Какое наибольшее количество различных чисел может быть среди всех $n − 1$ выписанных на листке чисел?

Источники: ВСОШ, ЗЭ, 2025, 10.5 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Давайте начнем с оценки. Вот если есть два различных числа a, b и их НОД равен d, можно ли как-то оценить эти числа, используя d? И как, используя эти оценки, оценить сверху d некоторым выражением от n?

Подсказка 2:

Одна из самых очевидных оценок: min(a, b) ≥ d, max(a, b) ≥ 2d. Отсюда следует, что n ≥ 2d, откуда d ≤ [n / 2]. Осталось привести пример.

Подсказка 3:

Чтобы найти расстановку, для которой любое число d ≤ [n / 2] будет выписано, можно сделать так, чтобы числа вида d и 2d стояли рядом.

Подсказка 4:

Тут на помощь могут прийти числовые цепочки вида a, 2a, 2²a, ... Подумайте, почему они могут быть полезны, и как реализовать расстановку с ними?

Показать ответ и решение

Оценка. Предположим, что какое-то из выписанных на листке чисел больше $⌊n∕2⌋,$ скажем, $НО Д(a,b)= d> ⌊n∕2⌋.$ Тогда наибольшее из чисел $a,b$ не меньше $2d,$ что больше $n$ – противоречие (НОД двух чисел, не превосходящих $n,$ не превосходит $n$ ). Значит, каждый из написанных $Н ОД$ ов не превосходит $⌊n∕2⌋,$ потому количество различных $Н ОД$ ов не может превышать $⌊n∕2⌋.$

Пример. Разобьём все числа от $1$ до $n$ на цепочки вида $k a,2a,4a,8a,...,2a,$ где $a$ — нечётное число, не превосходящее $n.$ Выпишем в строчку цепочки одну за другой. Тогда для любого натурального $d≤ ⌊n∕2⌋$ найдётся цепочка, в которой встречается $d,$ а следующее за $d$ число будет $2d.$ Видим, что каждое натуральное $d≤⌊n∕2⌋$ будет выписано на листке.

Ответ:

$⌊n⌋ 2$

Ошибка.
Попробуйте повторить позже

Задача 3#127159Максимум баллов за задание: 7

Петя и Вася играют в игру на изначально пустой клетчатой таблице $100× 100,$ делая ходы по очереди. Начинает Петя. За свой ход игрок вписывает в некоторую пустую клетку любую заглавную букву русского алфавита (в каждую клетку можно вписать ровно одну букву). Когда все клетки будут заполнены, Петя объявляется победителем, если найдутся четыре подряд идущие клетки по горизонтали, в которых слева направо написано слово «ПЕТЯ», или найдутся четыре подряд идущие клетки по вертикали, в которых сверху вниз написано слово «ПЕТЯ». Сможет ли Петя выиграть независимо от действий Васи?

Источники: ВСОШ, ЗЭ, 2025, 10.1 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Попробуйте придумать выигрышную стратегию для Васи.

Подсказка 2:

Хорошей идеей будет выбрать некоторую букву, которой нет в слове ПЕТЯ, и некоторым образом с её помощью блокировать появление данного слова. Как это сделать?

Подсказка 3:

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

Показать ответ и решение

Опишем выигрышную стратегию Васи. Пусть Вася все время пишет букву «Ю» в клетку согласно следующим ниже условиям; а если указанная клетка не существует или уже занята, а также если Петя ставит любую букву отличную от «П», «Е», «Т», «Я», то пусть Вася ставит «Ю» в любую свободную клетку.

Если Петя в некоторой клетке пишет букву «П», то Вася пишет «Ю» в клетке, соседней с ней справа; если Петя пишет букву «Е», то Вася пишет «Ю» в клетке, соседней с ней слева; если Петя пишет букву «Т», то Вася пишет «Ю» в клетке, соседней с ней снизу; если Петя пишет букву «Я», то Вася пишет «Ю» в клетке, соседней с ней сверху.

Из первых двух условий следует, что в двух соседних по горизонтали клетках не могло появиться «ПЕ», читаемое слева направо. В самом деле, предположим, что горизонтальное «ПЕ» появилось; тогда после появления первой из этих двух букв Вася, согласно описанной стратегии, сразу займёт место второй из этих букв — противоречие. Аналогично, в двух соседних по вертикали клетках не могло появиться «ТЯ», читаемое сверху вниз.

Ответ:

не сможет

Ошибка.
Попробуйте повторить позже

Задача 4#127160Максимум баллов за задание: 7

Внутри треугольника $ABC$ отмечена точка $P.$ На отрезке $AB$ отмечена точка $Q,$ а на отрезке $AC$ — точка $R$ так, что описанные окружности треугольников $BPQ$ и $CPR$ касаются прямой $AP.$ Через точки $B$ и $C$ провели прямые, проходящие через центр описанной окружности треугольника $BP C,$ а через точки $Q$ и $R$ — прямые, проходящие через центр описанной окружности треугольника $PQR.$ Докажите, что существует окружность, которая касается четырёх проведённых прямых.

Источники: ВСОШ, ЗЭ, 2025, 10.2 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Наличие касания двух окружностей с AP должно вызвать у вас желание написать степень точки A относительно этих окружностей.

Подсказка 2:

Скорее всего вы получили равенство AB • AQ = AC • AR, которое говорит о том, что BCQR — вписанный. Попробуйте найти на рисунке какую-нибудь точку, для которой проще всего доказать, что она равноудалена от нужных четырех прямых.

Подсказка 3:

Проще всего это сделать для точки O — центра окружности, описанной около BCRQ. Что для этого нужно доказать?

Подсказка 4:

Пусть O₁, O₂ — центры окружностей (BPC) и (QPR). Для этого достаточно равенства направленных углов O₁BO и OQO₂. Кстати, почему?

Подсказка 5:

Попробуйте выразить угол OQO₂ через углы RPQ и RCQ. Для этого давайте вспомним, что в треугольнике величина центрального угла его описанной окружности, опирающийся на сторону a, некоторым образом связана с величиной угла, противолежащего а. В дальнейшем доказательстве вам поможет теорема об угле между хордой и касательной.

Показать доказательство

Поскольку

2 AB ⋅AQ = AP = AC ⋅AR,

четырёхугольник $BCRQ$ — вписанный. Пусть $O$ — центр окружности $BCRQ.$ Обозначим через $O1$ и $O2$ центры окружностей $BP C$ и $QPR.$ Покажем, что прямые $BO1,$ $CO1,$ $QO2,$ $RO2$ равноудалены от $O.$ Так как

OB = OC =OQ = OR,

для этого достаточно установить равенство направленных углов

∠OCO1 = ∠O1BO =∠OQO2 = ∠O2RO.

Здесь первое и последнее равенства очевидны из симметрии относительно серединных перпендикуляров к $BC$ и $QR.$

Остаётся доказать равенство $∠O1BO = ∠OQO2 (⋆).$ Из счёта углов получаем

∠OQO2 = ∠OQR − ∠O2QR =(90∘ − ∠RCQ )− (90∘− ∠RPQ )=∠RP Q − ∠RCQ

Аналогично

∠O1BO =∠BP C − ∠BQC

Значит, $(⋆)$ эквивалентно равенству

∠RPQ − ∠RCQ =∠BP C − ∠BQC

или

∠BQC − ∠RCQ = ∠BP C− ∠RP Q (⋆⋆).

Из касания окружностей $BPQ$ и $CP R$ следует

∠RPQ = ∠RCP + ∠PBQ,

что из суммы углов четырёхугольника $BP CA$ равно

∠BP C − ∠BAC.

Тем самым, $(⋆⋆)$ преобразуется к виду

∠BQC − ∠RCQ = ∠BAC,

что верно.

$PIC$

Ошибка.
Попробуйте повторить позже

Задача 5#127161Максимум баллов за задание: 7

На плоскости отмечены $106$ точек, никакие три из которых не лежат на одной прямой, и проведены все отрезки между ними. Гриша поставил на каждом проведённом отрезке вещественное число, по модулю не превосходящее 1, и для каждой шестёрки отмеченных точек посчитал сумму чисел на всех 15 отрезках, соединяющих их. Оказалось, что каждая такая сумма по модулю не меньше числа $C,$ при этом среди таких сумм есть как положительная, так и отрицательная. При каком наибольшем $C$ это возможно?

Источники: ВСОШ, ЗЭ, 2025, 10.4 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Если найдутся две шестёрки с разными знаками сумм, отличающиеся одной вершиной, то их объединение содержит 7 вершин. Чем интересно данное множество из 7 вершин? Сколько подшестёрок оно содержит и можно ли сказать что-то про знаки сумм этих шестёрок?

Подсказка 3

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

Подсказка 4

Классифицируйте вершины в этом 7-вершинном множестве: назовите вершину "типа A", если при её удалении сумма в оставшейся шестёрке отрицательна, и "типа B" — если положительна. Пусть k — количество вершин типа A. Какие значения k существенны, а какие аналогичны между собой?

Подсказка 5

Разделите рёбра на три типа: AA (между вершинами типа A), AB (между A и B), BB (между вершинами типа B). Если заменить веса на рёбрах каждого типа на их среднее арифметическое, то как это преобразование повлияет на суммы в подшестёрках? Сохранятся ли условия задачи?

Подсказка 6

Анализировать такую 7-ку вершин намного легче. Можно записать неравенства на искомую константу С при помощи новых значений на ребрах.

Подсказка 7

Какие бы ограничения на константу ни были найдены ранее, всё равно нужно предоставить числа для рёбер, которые будут её реализовывать. Может быть, вид 7-ки после замены чисел на средние можно распространить на весь граф?

Показать ответ и решение

Рассмотрим граф, вершинами которого являются отмеченные точки, а рёбрами — проведённые отрезки.

Оценка. Докажем оценку $15- C ≤ 4 .$ Условие гласит, что в нашем полном графе есть как шестёрки вершин, сумма на рёбрах между которыми положительна, так и шестёрки, сумма на рёбрах между которыми отрицательна. Тогда найдутся две шестёрки, отличающиеся заменой только одной вершины, такие, что у одной из них сумма положительна, у другой отрицательна. В самом деле, возьмём шестёрку с положительной суммой, и будем превращать её в шестёрку с отрицательной суммой, меняя вершины по одной, — на каком-то шаге произошло изменение знака, шестёрки, которые были до и после этого шага – искомая пара.

Далее работаем с полным подграфом на множестве $S$ из семи вершин – объединении вышеописанной пары шестёрок. Рассмотрим все семь шестёрок, которые можно получить выбрасыванием одной вершины из $S.$ Пусть среди них $k$ с отрицательными суммами — получающиеся выбрасыванием вершин $A1,...,Ak,$ будем называть эти вершины $A$ -вершинами, а соответствующие шестёрки – $A$ -шестёрками), и $7− k$ с положительными суммами — получающиеся выбрасыванием вершин $B1,...,B7−k$ (будем называть эти вершины $B$ -вершинами, а соответствующие шестёрки – $B$ -шестёрками). Рёбра между двумя $A$ -вершинами будем называть $AA$ -рёбрами, между двумя $B$ -вершинами — $BB$ -рёбрами, а рёбра, соединяющие $A$ -вершину с $B$ -вершиной — $AB$ -рёбрами.

Из изначальной расстановки чисел на рёбрах, соединяющих вершины множества $S,$ получим новую расстановку, заменив все числа на $AA$ -рёбрах на число $x,$ равное их среднему арифметическому, и аналогично заменив все числа на $AB$ -рёбрах на их среднее арифметическое $y,$ а все числа на $BB$ -рёбрах на их среднее арифметическое $z.$ Очевидно, $|x|≤1,|y|≤ 1,|z|≤ 1,$ так как все старые числа по модулю не превосходят 1.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Подграф $S$ с новыми числами на рёбрах удовлетворяет условию с той же константой $C.$

Доказательство леммы. Заметим, что для каждого $AA$ -рёбра есть одно и то же количество $A$ -шестёрок, в которые входят оба его конца. И наоборот, для любой $A$ -шестёрки среди 15 рёбер между её вершинами есть одно и то же количество $AA$ -рёбер. То же верно для $AB$ -рёбер и для $BB$ -рёбер. Значит, сумма $∑A$ чисел на рёбрах в $A$ -шестёрке в новой расстановке есть среднее сумм по всем $A$ -шестёркам в старой расстановке, то есть среднее нескольких чисел, не больших – $C;$ значит, $∑A ≤ −C.$ Аналогичное утверждение верно для сумм в $B$ -шестёрках. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Далее изучаем новую расстановку. Рассмотрим случаи.

Случай $k= 1.$ Иными словами, есть ровно одна $A$ -шестёрка, на которой пятнадцать $BB$ -рёбер, и шесть $B$ -шестёрок, на каждой из которых десять $BB$ -рёбер и пять $AB$ -рёбер. Имеем систему неравенств:

15z ≤ −C, 5y +10z ≥ C.

Умножим первое на $−2,$ сложим со вторым, умноженным на 3, получим $15y ≥5C,$ откуда $C ≤ 3.$

Случай $k= 2.$ Теперь у нас две $A$ -вершины и пять $B$ -вершин, то есть на $A$ -шестёрке есть десять $BB$ -рёбер и пять $AB$ -рёбер, а на $B$ -шестёрке – шесть $BB$ -рёбер, восемь $AB$ -рёбер и одно $AA$ -ребро. Имеем

5y+ 10z ≤ −C,

x+ 8y +6z ≥ C

Исключая $z,$ получаем

8C ≤5x+ 25y ≤ 30,

значит, $15 C ≤ 4 .$

Случай $k= 3.$ Аналогично предыдущему, имеем

x+ 8y+ 6z ≤− C

3x+ 9y+ 3z ≥C

Избавляясь на этот раз от $y,$ получаем $17C ≤ 15x − 30z ≤ 45,$ откуда $C ≤ 45< 15. 17 4$

Случаи $k≥ 4$ сводятся к рассмотренным умножением всех чисел на $− 1,$ что ведёт к замене $k ↦→ 7− k.$ Итак, оценка $C ≤ 15 4$ доказана.

Пример. Любое число вершин от двух до 999995 объявим вершинами типа $A,$ остальные – вершинами типа $B.$ На всех рёбрах между двумя вершинами типа $B$ напишем число $− 7, 8$ на всех остальных – число 1. Тогда, если в шестёрке вершин хотя бы пять $B$ -вершин, то сумма в ней не больше $− 15, 4$ а иначе – не меньше $15. 4$

Ответ:

$15 4$

Ошибка.
Попробуйте повторить позже

Задача 6#128205Максимум баллов за задание: 7

На периметре треугольника $ABC$ выбраны точки $D , 1$ $D , 2$ $E , 1$ $E , 2$ $F , 1$ $F 2$ так, что при обходе периметра точки встречаются в порядке $A,$ $F1,$ $F2,$ $B,$ $D1,$ $D2,$ $C,$ $E1,$ $E2.$ Оказалось, что

AD1 = AD2 = BE1 = BE2 = CF1 =CF2.

Докажите, что периметры треугольников, образованных тройками прямых $AD1,$ $BE1,$ $CF1$ и $AD2,$ $BE2,$ $CF2,$ равны.

Источники: ВСОШ, ЗЭ, 2025, 9.8 (см. olympiads.mccme.ru)

Показать доказательство

Начнём со следующей полезной леммы.

Лемма. Пусть точки $F$ и $E$ выбраны соответственно на сторонах $AB$ и $AC$ параллелограмма $ABKC$ так, что $BE =CF.$ Тогда точка $K$ равноудалена от прямых $BE$ и $CF.$

Доказательство. Поскольку $BK ∥EC$ и $CK ∥FB,$ имеем $SKBE =SKBC = SKFC.$ Так как $BE = CF,$ отсюда и следует, что расстояния от точки $K$ до прямых $BE$ и $CF$ равны.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Перейдём к решению. Пусть прямые из условия образуют треугольники $X1Y1Z1$ и $X2Y2Z2$ (точки обозначены как на рис.). Выберем точку $K$ так, что $ABKC$ — параллелограмм; согласно лемме, точка $K$ равноудалена от прямых $BE1,CF1,BE2$ и $CF2$ ; значит, существует окружность с центром $K,$ касающаяся этих прямых в некоторых точках $P1,Q1,P2$ и $Q2$ соответственно. Тогда из равенств отрезков касательных вытекает, что

BX − CX = BP + X P − X Q + CQ =BP +CQ = 1 1 1 1 1 1 1 1 2 2

BP2− X2P2+ X2Q2+ CQ2 = CX2 − BX2.

$PIC$

Аналогично получаем, что $CY1− AY1 = AY2− CY2$ и $AZ1− BZ1 =BZ2 − AZ2.$ Складывая полученные три равенства, получаем требуемое равенство периметров.

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#128210Максимум баллов за задание: 7

При каком наименьшем $k$ для любого многочлена $f(x)$ степени 100 с вещественными коэффициентами найдётся такой многочлен $g(x)$ степени не выше $k$ с вещественными коэффициентами, что графики $y = f(x)$ и $y = g(x)$ имеют ровно 100 общих точек?

Источники: ВСОШ, ЗЭ, 2025, 10.6 (см. olympiads.mccme.ru)

Показать ответ и решение

Положим $n= 100.$

Покажем, как подобрать нужный многочлен $g$ степени не выше $n− 2$ для данного многочлена $f$ степени $n.$ При домножении $f$ на ненулевую константу условие не поменяется (многочлен $g$ можно домножить на ту же константу), поэтому считаем, что старший коэффициент $f$ равен $1,$ так что

n n−1 f(x)=x +a1x + ...+an.

Возьмём произвольный набор $n$ различных чисел $x , 1$ $x ,...,x , 2 n$ дающих в сумме $− a , 1$ и положим

h(x)= (x− x1)...(x− xn), g(x)= f(x)− h(x),

так что $h= f − g.$ Видим, что у $f$ и $h$ совпадают коэффициенты при $xn$ и при $xn−1,$ поэтому степень $g$ не превышает $n − 2.$ С другой стороны, абсциссы точек пересечения графиков $f$ и $g$ — это в точности корни многочлена $h,$ а их ровно $n.$

Покажем, что $k ≤n − 3$ не работает. Пусть дан многочлен $f(x)= xn,$ а $g(x)$ — многочлен степени не выше $n− 3.$ Предположим, что графики $f$ и $g$ пересекаются в $n$ точках, имеющих абсциссы $x , 1$ $x,...,x . 2 n$ Но тогда многочлен $f − g$ степени $n$ имеет $n$ вещественных корней $x , 1$ $x,...,x . 2 n$ С другой стороны, у $f − g$ коэффициенты при $xn−1$ и $xn−2$ равны 0. Но тогда по теореме Виета

s1 = x1+ x2+...+xn =0,

s2 = x1x2+ x1x3+...+xn−1xn = 0.

Отсюда

x2+ x2+ ...+x2 =s2− 2s = 0, 1 2 n 1 2

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

x1 = x2 = ...= xn = 0,

что противоречит тому, что $xi$ различны.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 8#128212Максимум баллов за задание: 7

В программу соревнования входит 25 видов спорта, в каждом из которых определяется один победитель, получающий золотую медаль. В соревновании участвуют 25 спортсменов, каждый — во всех 25 видах спорта. Имеется 25 экспертов, каждый из которых должен сделать прогноз, сколько золотых медалей получит каждый спортсмен, при этом в его прогнозе количества медалей должны являться целыми неотрицательными числами с суммой 25. Эксперта признают компетентным, если он верно угадает количество золотых медалей хотя бы у одного спортсмена. При каком наибольшем $k$ эксперты могут сделать такие прогнозы, что хотя бы $k$ из них будут признаны компетентными независимо от исхода соревнования?

Источники: ВСОШ, ЗЭ, 2025, 10.7 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Казалось бы, задача на оценку + пример. Обычно в этом случае мы сначала делаем оценку, потом под неё подгоняем пример. Здесь же стоит делать наоборот, объясним мотивацию. Пусть мы хотим доказать, что 20 нельзя (например). Доказывать это прямо абсолютно непонятно как, значит, можно попробовать от обратного. Но условие на то, что 20 можно, нам не даёт ровным счётом ничего, мы просто знаем этот факт, и про оценки каждого эксперта мы ничего сказать не можем. В таких случаях оценка чаще всего тривиальна (что-то около границ), а основную сложность составляет пример. Подумайте, какие наборы оценок у экспертов нам лучше использовать для примера?

Подсказка 2:

Поисследуем наборы. Имеем 25 человек и 25 медалей, которые распределены между ними. По принципу Дирихле, всегда найдётся человек, у которого не более одной медали. Что мы тогда можем сказать про спортсменов, у которых вовсе нет медалей (будем называть таких нулевыми)?

Подсказка 3:

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

Подсказка 4:

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

Подсказка 5:

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

Подсказка 6:

Маска вида: 1 единица, 23 нуля и все остальные. Какой набор тогда мы получаем для остальных 24 спортсменов?

Подсказка 7:

Например: (1, 0, ..., 0, 24), (0, 1, 0, ..., 0, 24), ..., (0, ..., 0, 1, 24). Очевидно, если единичный компетентен, то у нас 25 компетентных экспертов. Что же происходит, когда он некомпетентен?

Подсказка 8:

Докажите, что в этом случае хотя бы 3 спортсмена являются нулевыми. Отсюда немедленно следует, что все остальные эксперты компетентны. Итого, имеем пример на 24. Осталось сделать оценку.

Подсказка 9:

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

Подсказка 10:

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

Показать ответ и решение

Оценка. Покажем, что $k≤ 24,$ то есть, что любой эксперт может оказаться некомпетентным. Если этот эксперт считает, что все спортсмены возьмут по одной медали, опровергнем его результатом $(25,0,0,...,0).$ Иначе эксперт считает, что несколько (хотя бы один) спортсменов получат 0 медалей. Тогда распределим все медали между этими спортсменами так, чтобы каждый из них получил хотя бы одну медаль. В таком случае эксперт не угадает ни одного количества медалей.

Пример. Пусть прогноз одного эксперта — $(1,1,1,...,1),$ а прогнозы остальных — (1, 0, …, 0, 24), (0, 1, …, 0, 24), …, (0, 0, …, 1, 24) (на последнем месте 24, и ещё одна единица).

Если некомпетентным оказался первый эксперт, то в исходе точно есть хотя бы три нуля, иначе хотя бы в 23 позициях количество медалей не меньше 2, и тогда общее количество медалей не меньше $23⋅2> 30$ — противоречие. Но тогда каждый из остальных экспертов компетентный.

Предположим теперь, что двое экспертов, отличных от первого, оказались некомпетентными. Тогда в двух позициях их прогнозы — 0 и 1 медалей, а значит, в реальном исходе в этих позициях не менее 2 медалей. Кроме того, ещё в 22 позициях прогнозы обоих экспертов — нули, значит, в реальном исходе в этих позициях не менее 1 медали. Тогда общее количество медалей не меньше $2⋅2+ 22⋅1> 25$ — противоречие.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 9#129648Максимум баллов за задание: 7

Пусть $p$ и $q$ — различные простые числа. Дана бесконечная убывающая арифметическая прогрессия, в которой встречается каждое из чисел $23 p ,$ $24 p ,$ $23 q$ и $24 q .$ Докажите, что в этой прогрессии обязательно встретятся числа $p$ и $q.$

Источники: ВСОШ, ЗЭ, 2024, 10.1 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

Сформулируем несколько утверждений, которые помогут решить задачу. Во-первых, если в целочисленной арифметической прогрессии есть два числа a и b, то a − b кратно d. Во-вторых, если в прогрессии с разностью d есть a, то b ей будет принадлежать тогда и только тогда, когда a − b кратно d.

Подсказка 4:

Значит, d является делителем p²⁴ − p²³. Нужно, чтобы оно также делило p²³ − p. Чтобы было проще, подумайте, может ли d делиться на p?

Показать доказательство

Вычеркнем все нецелые числа из прогрессии (если они есть). Ясно, что после вычёркивания остаётся бесконечная убывающая арифметическая прогрессия, состоящая из целых чисел. Пусть её разность равна — $d.$

Заметим, что $23 23 q − p$ делится на $d,$ значит, $d$ не делится на $p,$ иначе $23 q$ должно будет делиться на $p,$ что неверно. С другой стороны, $d$ должно являться делителем числа

24 23 23 p − p = p (p− 1).

Поскольку $p$ и $d$ взаимно просты, $p− 1$ делится на $d.$ Далее, $p23− p$ делится на $p − 1,$ поскольку оно равно

21 20 p(p− 1)(p + p + ⋅⋅⋅+ 1).

Поэтому $p23− p$ делится на $d,$ и, поскольку $p< p23,$ получаем, что $p$ лежит в нашей прогрессии. Аналогично, $q$ лежит в этой прогрессии.

Ошибка.
Попробуйте повторить позже

Задача 10#129649Максимум баллов за задание: 7

Дано нечётное число $n ≥3.$ В клетчатом квадрате $2n× 2n$ закрашивают $2(n − 1)2$ клеток. Какое наибольшее количество трёхклеточных уголков можно гарантированно вырезать из незакрашенной клетчатой фигуры?

Источники: ВСОШ, ЗЭ, 2024, 10.2 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

Представьте, что мы хотим гарантированно найти много уголков. Как можно разбить большой квадрат 2n×2n на более мелкие области, чтобы каждый возможный уголок целиком лежал в одной такой области?

Подсказка 2

Предположим, мы разбили квадрат на n² квадратиков 2×2. Сколько клеток в одном таком квадратике? Сколько из них нужно оставить незакрашенными, чтобы гарантированно можно было вырезать один уголок? Похоже на принцип Дирихле.

Подсказка 3

Допустим, для нечётного размера m мы уже знаем, как построить пример с 2(m−1)² закрашенными клетками, позволяющий вырезать 2m−1 уголков. Можно "вставить" этот меньший квадрат внутрь 2(m+2)×2(m+2) и получить пример для m+2? Какая часть большого квадрата останется "непокрытой" этим меньшим квадратом?

Подсказка 4

В этой рамке ширины 2 нам нужно закрасить дополнительные клетки. Сколько всего клеток нам нужно закрасить в большом квадрате? Сколько уже "запланировано" закрасить во внутреннем квадрате? Сколько клеток нужно закрасить в рамке? Как можно закрасить эти клетки в рамке так, чтобы они "мешали" вырезать уголки только минимальное необходимое количество?

Подсказка 5

Для покраски рамки остаётся 2((m+1)² − (m−1)²) = 8m, такой же длины периметр квадрата 2m×2m. Что, если закрасить клетки, граничащие с "вставленным" квадратом?

Показать ответ и решение

Оценка. Разобьём квадрат $2n ×2n$ на $n2$ квадратиков $2× 2.$

Среди этих квадратиков не более

2(n− 1)2 2 ---2---= (n− 1)

квадратиков, в которых покрашено хотя бы 2 клетки.
Остальных квадратиков $2× 2$ — не менее

n2− (n − 1)2 = 2n− 1.

Из каждого из них можно вырезать трёхклеточный уголок.

Пример. Построим пример индукцией по нечётным $n ≥ 1.$ При $n= 1$ закрашенных клеток нет, и можно вырезать один уголок.

Для перехода выделим в квадрате внешнюю «рамку» шириной в две клетки. В этой рамке закрасим все $8(n − 2)$ клетки, примыкающие к внутренней границе рамки (см. рис.), а в квадрате внутри рамки закрасим клетки по предположению индукции. Общее количество закрашенных клеток равно

2(n− 3)2 +8(n− 2) =2(n− 1)2.

$PIC$

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

2(n− 2)− 1 =2n − 5.

Из рамки же нельзя вырезать более $4$ уголков — каждый такой уголок должен содержать хотя бы $2$ клетки одного из угловых квадратов $2 ×2,$ а двух уголков, пересекающихся с одним квадратом, вырезать нельзя. Значит, общее количество уголков не больше

(2n− 5)+4 =2n − 1.

Ответ:

$2n− 1$

Ошибка.
Попробуйте повторить позже

Задача 11#129650Максимум баллов за задание: 7

Дано натуральное число $n.$ Илья задумал пару различных многочленов степени $n$ (с вещественными коэффициентами), аналогично Саша задумал пару различных многочленов степени $n.$ Лёня знает $n;$ его цель — выяснить, одинаковые ли пары многочленов у Ильи и Саши. Лёня выбирает набор из $k$ вещественных чисел $x1 < x2 < ...< xk$ и сообщает эти числа. В ответ Илья заполняет таблицу $2× k:$ для каждого $i= 1,2,...,k$ он вписывает в две клетки $i$ -го столбца пару чисел $P(xi),Q (xi)$ (в любом из двух возможных порядков), где $P$ и $Q$ — задуманные им многочлены. Аналогичную таблицу заполняет Саша. При каком наименьшем $k$ Лёня сможет (глядя на таблицы) наверняка добиться цели?

Источники: ВСОШ, ЗЭ, 2024, 10.3 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

Предположим, Лёня выбрал k = 2n точек. Можем ли мы придумать две разные пары многочленов степени n (P₁, Q₁ и P₂, Q₂), при которых таблицы Ильи и Саши будут одинаковыми, хотя пары многочленов разные. Как можно использовать факт, что в таблице порядок значений P(xᵢ) и Q(xᵢ) не фиксирован?

Подсказка 2

Попробуем "разделить" точки на два набора по n штук. Пусть A(x) обращается в ноль на первом наборе точек, а B(x) — на втором. Какие значения будут принимать многочлены вида ±A ± B в выбранных точках?

Подсказка 3

Теперь пусть Лёня выбрал k = 2n + 1 точек. Предположим, что таблицы Ильи и Саши совпали. Сколько раз каждый многочлен Ильи (P₁ или Q₁) обязан совпасть по значению с каким-то многочленом Саши (P₂ или Q₂) в одной и той же точке xᵢ?

Подсказка 4

Найдется пара многочленов, один Сашин, второй Ильи, у которых значения совпадают хотя бы n + 1 точке. Если два многочлена степени не выше n принимают одинаковые значения в более чем n различных точках, что можно сказать об этих многочленах?

Показать ответ и решение

Покажем, что при $k =2n$ (а тем более при $k <2n$ ) Лёня не сможет однозначно определить определить пару $P,$ $Q.$ Пусть он назвал

x1 < x2 < ...< x2n.

Положим

A =(x− x)(x− x)...(x− x ), B = (x − x )(x − x )...(x− x ), 1 2 n n+1 n+2 2n

так что $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$ таблице Ильи может удовлетворять не более одной пары многочленов $P,Q.$ Предположим противное, и есть две такие пары: $P1,Q1$ и $P2,Q2.$ Тогда $P2$ совпадает с $P1$ или $Q1$ хотя бы при $n +1$ различных значениях аргумента, пусть, скажем, с $P1.$ Но тогда $P1$ и $P2$ — одинаковые многочлены (поскольку их разность — многочлен степени не выше $n,$ имеющий не менее $n+ 1$ различных корней). Из таблицы тогда получаем, что значения $Q1$ и $Q2$ совпадают в $2n +1$ точке, а тогда и $Q1 = Q2.$

Ответ:

$2n+ 1$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#129651Максимум баллов за задание: 7

Дан выпуклый четырёхугольник $ABCD,$ в котором $∠A + ∠D =90∘.$ Его диагонали пересекаются в точке $E.$ Прямая $ℓ$ пересекает отрезки $AB,$ $CD,$ $AE$ и $ED$ в точках $X,$ $Y,$ $Z$ и $T$ соответственно. Известно, что $AZ =CE$ и $BE = DT.$ Докажите, что длина отрезка $XY$ не больше диаметра окружности, описанной около треугольника $ETZ.$

Источники: ВСОШ, ЗЭ, 2024, 10.4 (см. olympiads.mccme.ru)

Показать доказательство

Обозначим через $ω$ окружность $(ET Z)$ и через $d$ — её диаметр. Поскольку $BE = DT,$ то

BT = BE + ET =DT + ET =DE.

Из условия $∠A + ∠D =90∘$ следует, что лучи $AB$ и $DC$ пересекаются в некоторой точке $F$ под прямым углом. Проведем диаметр $EB ′$ в окружности $(ABE ).$ Поскольку $∠ABE >90∘,$ точки идут на окружности в порядке $A− B− E − B ′.$ Тогда

′ ′ ∘ ∠AB B = ∠AEB = ∠CED, ∠BAB = 90 +∠F AC =∠ECD.

Следовательно, треугольники $CED$ и $AB ′B$ подобны по двум углам, поэтому

AB′= CE- = AZ. BB′ ED BT

Полученное равенство означает, что прямоугольные треугольники $AB′Z$ и $BB ′T$ подобны по отношению катетов. Тогда $∠BT B′ = ∠AZB ′,$ поэтому точка $B′$ лежит на окружности $ω.$ Заметим, что $AB$ — прямая Симcона точки $B′$ для треугольника $ZET,$ поскольку $∠B′AE = ∠B ′BE = 90∘.$ Тогда и проекция $B′$ на прямую $ZT$ тоже лежит на $AB,$ то есть $B ′X ⊥ ZT.$

Рассуждая аналогично, мы получаем, что точка $C′,$ диаметрально противоположная $E$ на окружности $(CED ),$ лежит на окружности $ω,$ а также $′ C Y ⊥ ZT.$ Таким образом, $′ ′ BC$ — хорда окружности $ω,$ а $X$ и $Y$ — проекции точек $′ B$ и $′ C$ на прямую $ZT,$ поэтому $′ ′ XY ≤ B C ≤ d,$ что и требовалось.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Замечание 1. Приведём схему другого решения.

Нетрудно показать, что $XZ = TY$ (например, используя Теорему Менелая). Пусть $M,N,K$ — середины $AC$ (и $ZE$ ), $BD$ (и $T E$ ), $XY$ (и $ZT$ ) соответственно. Пусть $F = AB ∩CD,$ Из прямоугольного треугольника $XF Y$ имеем $FK = XY∕2.$ Далее, $KMN$ — серединный треугольник для треугольника $EZT.$ Легкий счет углов (с использованием медианы прямоугольного треугольника) дает

∠MF N = 180∘− ∠MEN = 180∘− ∠MKN.

Значит, точки $M,K,N,F$ лежат на одной окружности, тогда $FK$ — хорда окружности ( $MKN$ ). Отсюда

XY ∕2= KF ≤2RMKN = RETZ,

что завершает решение.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание 2. На самом деле $B′C ′$ — диаметр окружности ( $ET Z$ ), что нетрудно установить счётом углов, но для решения этого не требуется. Равенство $XY = d$ достигается в том и только в том случае, когда исходный четырёхугольник — вписанный.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание 3. Приведём план ещё одного подхода к задаче. Используем обозначения из приведённого выше решения, а также введём новые: $x= BF,$ $y = AB,$ $z = CF,$ $t= DC,$ $k = DE, EB$ $m = AE, FC$ $p=ZT,$ $α= ∠AED.$ Из теорем Менелая для $△EZT$ и прямой $AY B,$ $△EZT$ и прямой $CY D$ находим:

--1-- XZ = YT = P ⋅k!− 1

По теореме синусов для треугольника $p ZET :d = sinα,$ в силу сказанного выше

XY = XZ +Y Z+ ZT =p ⋅ k!+-1 k!− 1

Таким образом, достаточно доказать, что $sinα≤ kk!−!+11(⋆).$ Из теорем Менелая для $△AFC$ и прямой $BED,$ $△BF D$ и прямой $AEC$ легко видеть, что

k = t(x+-y), l= y(z+-t), zy xt

отсюда

(x+y)(z+t) k!− 1 (x +y)(z +t)− xz kl= ----xz----+ k!+1-= (x-+y)(z-+t)+xz.

Обозначим

∠FAC = β, ∠F DB = γ,

тогда $α =90∘+ β+ γ.$ Значит,

∘ -------------- sinα = cosγcosβ− sinγsinβ = (x+ y)(z+t)− xz,

последнее равенство получается из прямоугольных треугольников $AFC$ и $BF D.$ Остаётся заметить, что

∘ (x2+(z+-t)2)(z2+-(x-+y)2)-≥xz+ (z+t)(x+ y)

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

Ошибка.
Попробуйте повторить позже

Задача 13#129652Максимум баллов за задание: 7

Дана прямолинейная дорога, выложенная из зелёных и красных дощечек (дорога — отрезок, разбитый на отрезки-дощечки). Цвета дощечек чередуются; первая и последняя дощечки — зелёные. Известно, что длины всех дощечек больше сантиметра и меньше метра, а также что длина каждой следующей дощечки больше предыдущей. Кузнечик хочет пропрыгать вперёд по дороге по этим дощечкам, наступив на каждую зелёную дощечку (или границу между соседними дощечками). Докажите, что кузнечик может сделать это так, чтобы среди длин его прыжков встретилось не более 8 различных значений.

Источники: ВСОШ, ЗЭ, 2024, 10.5 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Чтобы перепрыгнуть красную дощечку длины L (где 1 < L < 100 см), потребуется прыжок длиннее L. Учитывая, что длины дощечек строго возрастают, подумайте: если мы перепрыгнули красную дощечку прыжком длины D, то для следующей (ещё более длинной) красной дощечки потребуется прыжок примерно вдвое больше. Как можно организовать набор прыжков, чтобы покрыть весь диапазон от 1 до >100 см, используя мало различных длин?

Подсказка 3

Рассмотрим прогрессию длин прыжков: l, 2l, 4l, 8l, 16l, 32l, 64l. Будет ли такая последовательность эффективна? Какие ограничения надо наложить на l?

Подсказка 4

Как выбрать l и ε? Самый большой прыжок (64l) должен быть > 100 см (чтобы перепрыгнуть самую длинную красную дощечку), но не сильно. Возьмём l < 2 см (чтобы ε = l/N было достаточно мало при большом N), ε < 0.01 см. Существует ли такое l?

Показать доказательство

Считаем, что дощечки выложены на числовой прямой. Примем $1 =1 см.$

Возьмем $0 <𝜀 <0,01$ такое, что разность длин любой пары соседних дощечек больше $10𝜀.$ Отметим на прямой бесконечную в обе стороны арифметическую прогрессию с разностью $𝜀$ так, чтобы концы дощечек не были отмечены. Кузнечик будет прыгать только по отмеченным точкам, и длины его прыжков будут из множества

{𝜀,l,2l,4l,8l,16l,32l,64l},

где $l= N 𝜀,$ а натуральное $N$ подберём так, что $l< 2$ и $64l> 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.$ Противоречие.

Ошибка.
Попробуйте повторить позже

Задача 14#129653Максимум баллов за задание: 7

Дан параллелограмм $ABCD.$ Точка $M$ — середина дуги $ABC$ окружности, описанной около треугольника $ABC.$ На отрезке $AD$ отмечена точка $E,$ а на отрезке $CD$ — точка $F.$ Известно, что $ME = MD =MF.$ Докажите, что точки $B,M, E$ и $F$ лежат на одной окружности.

Источники: ВСОШ, ЗЭ, 2024, 10.6 (см. olympiads.mccme.ru)

Показать доказательство

Первое решение. Пусть $∠ADC =x.$ Из равнобедренных треугольников $DME$ и $DMF$ (или из того, что $M$ — центр окружности $(DEF )$ ) имеем $∘ ∠EMF = 360 − 2x.$ Для решения задачи остаётся понять, что тому же равен $∠EBF.$

При гомотетии с центром $D$ и коэффициентом $1∕2$ точки $E,$ $F,$ $B$ перейдут соответственно в $′ E ,$ $′ F ,$ $′ B$ — середины отрезков $DE,$ $DF$ и $DB.$ . Вместо $∠EBF$ найдём $′ ′ ′ ∠E B F ,$ заметив, что $′ E$ и $′ F$ — проекции $M$ на $AD$ и $CD,$ а $′ B$ — центр параллелограмма, или середина $AC,$ тем самым, $′ B$ — проекция $M$ на $AC.$ Видим, что $′ ′ M,E ,A,B$ лежат на одной окружности с диаметром $MA.$ Отсюда

∠DE ′B ′ =∠AMB ′ =∠AMC ∕2 =∠ABC ∕2= x∕2.

Аналогично $′′ ∠DF B = x∕2.$ Из четырёхугольника $′ ′′ E B F D$ видим, что

′ ′ ′ ∘ ∘ ∠E B F =360 − x− x∕2− x∕2= 360 − 2x,

что и требовалось.

$PIC$

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

Равенство углов $∠ABE =∠CBF,$ в свою очередь, эквивалентно подобно $ABE ∼ CBF.$ Докажем это подобие.

Отметим на луче $AB$ за точкой $B$ точку $X$ так, что $BX = BC,$ а на луче $CB$ за точкой $B$ точку $Y$ так, что $BY =BA.$ Легко понять, что треугольники $BMC$ и $BMX$ равны по двум сторонам и углу между ними. Тогда $MX = MC = MA.$ Рассмотрим серединный перпендикуляр к $DF,$ тогда он является перпендикуляром к параллельной прямой $AX,$ а поскольку $MA = MX,$ то он же является серединным перпендикуляром к $AX.$ Таким образом, трапеция $ADF X$ равнобедренная, а раз $ABCD$ — параллелограмм, то $CXBF$ — также равнобедренная трапеция, причём $CB = BX = XF$ и $∠XBC = 180∘− ∠ABC.$ Аналогичное получим для трапеции $AY BE.$ Видим, что $AY BE ∼ CXBF,$ откуда следует нужное нам $ABE ∼ CBF.$

$PIC$

Ошибка.
Попробуйте повторить позже

Задача 15#129654Максимум баллов за задание: 7

Пусть даны натуральные числа $x 1$ и $x . 2$ На прямой даны $y 1$ белых отрезков и $y 2$ чёрных отрезков, при этом $y ≥ x 1 1$ и $y ≥x . 2 2$ Известно, что никакие два отрезка одного цвета не пересекаются (даже не имеют общих концов). Также известно, что при любом выборе $x1$ белых отрезков и $x2$ чёрных отрезков обязательно какая-то пара выбранных отрезков будет пересекаться. Докажите, что

(y1 − x1)(y2− x2)< x1x2.

Источники: ВСОШ, ЗЭ, 2024, 10.7 (см. olympiads.mccme.ru)

Показать доказательство

Первое решение. Пронумеруем белые отрезки слева направо как $w , 1$ $w , 2$ …, $w , y1$ а чёрные — как $b , 1$ $b, 2$ …, $b . y2$ Для каждого чёрного отрезка $bj$ назовём его силой $S(bj)$ количество индексов $i≤y1− 1$ таких, что $bj$ пересекается как с $wi,$ так и с $wi+1.$ Если с какой-то парой $(wi,wi+1)$ пересекаются два чёрных отрезка, то они имеют общую точку, что невозможно по условию. Поэтому каждая такая пара учтена в силе не более, чем одного чёрного отрезка, а значит,

y∑2 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

группа $G i$ состоит из отрезков $w , i+1$ $w , i+2$ …, $w , y1$ а также из $w , 1$ $w , 2$ …, $w i+x1−y1$ (иначе говоря, каждая группа состоит из $x 1$ последовательных отрезков в циклическом порядке). Для группы $G i$ обозначим через $N(G) i$ количество чёрных отрезков, не пересекающихся ни с одним из отрезков в $G . i$ По условию, $N(G )≤x − 1; i 2$ поэтому

y1∑−1 N(Gi)≤ y1(x2− 1). i=0

С другой стороны, каждый чёрный отрезок $b j$ пересекается максимум $1 +S(b) j$ белыми отрезками, и все эти белые отрезки расположены подряд. Тогда количество групп, содержащих хотя бы один из этих белых отрезков, не превосходит

1+ S(bj)+ (x1 − 1)= S(bj)+x1.

Поэтому отрезок $bj$ учтён хотя бы в $y1 − (S(bj)+ x1)$ числах вида $N(Gi).$ Поэтому

y1∑−1N (Gi)≥ y∑2(y1− S(bj)− x1)= y2(y1− x1)− y∑2S(bj)≥y2(y1− x1)− (y1− 1). i=0 j=1 j=1

Из полученных двух оценок на сумму $N (Gi)$ вытекает, что

y1(x2− 1)≥ y2(y1− x1)− (y1− 1) ⇐⇒ (y1− x1)(y2− x2)≤ x1x2− 1,

что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что утверждение задачи для некоторых $x1,$ $x2,$ $y1,$ $y2$ неверно:

(y1 − x1)(y2− x2)≥ x1x2,

и при этом условии сумма $y1 +y2$ — минимальная возможная.

Без ограничения общности тогда $y1 − x1 ≥ x1.$ Возьмём $x1$ -й слева белый отрезок $W$ и $(y2− x2)$ -й слева чёрный отрезок $B.$ У какого-то из них правый конец левее.

1) Пусть правый конец $W$ левее (или концы совпадают). Тогда правые $x2$ чёрных отрезков не пересекаются с левыми $x1$ белыми. Противоречие.

2) Пусть правый конец $B$ левее. Выкинем все белые отрезки слева от $W$ (включая его) и все чёрные отрезки слева от $B$ (включая его). Оставшиеся белые отрезки (их хотя бы $x 1$ ) не пересекаются с выкинутыми $y − x 2 2$ чёрными; отсюда уже следует, что $y2− x2 < x2.$

Положим

′ ′ ′ ′ x1 = x1, y1 = y1 − x1 ≥ x1, x2 =x2 − (y2− x2)

′ ′ y2 =y2− (y2− x2)= x2 ≥x2;

тогда осталось $y′ 1$ белых и $y′ 2$ чёрных отрезков. Рассмотрим любые $x′ 1$ оставшихся белых и $x′ 2$ оставшихся чёрных отрезков. Если среди них нет пересекающихся, то, добавив к ним все выкинутые чёрные отрезки, получим набор из $x1 = x′ 1$ белых и

′ x2 =x2+ (y2 − x2)

чёрных отрезков исходного набора, среди которых нет пересекающихся; это невозможно. Значит, оставшийся набор удовлетворяет условию для новых чисел $x′1,y′1,x′2$ и $y′2,$ при этом в нём меньше отрезков, чем в исходном, поэтому

0< x′x′ − (y′− x′)(y′− x′)= 12 1 1 2 2

= x1(2x2− y2)− (y1 − 2x1)(y2− x2)=

=x1x2− (y1− x1)(y2− x2)≤ 0.

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

Ошибка.
Попробуйте повторить позже

Задача 16#129657Максимум баллов за задание: 7

Дано натуральное $n >2.$ Маша записывает по кругу $n$ натуральных чисел. Далее Тая делает такую операцию: между каждыми двумя соседними числами $a$ и $b$ она пишет некоторый делитель числа $a+ b,$ больший 1; затем Тая стирает исходные числа и получает новый набор из $n$ чисел, стоящих по кругу. Всгда ли Тая может выполнять операции таким образом, чтобы через несколько операций все числа оказались равными?

Источники: ВСОШ, ЗЭ, 2024, 10.8 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

В случае, когда все числа нечётные, Тая может победить. Можно ли какие-либо ситуации свести к данной?

Подсказка 3

Допустим, что ни одна сумма соседних чисел не является степенью двойки, как свести данную ситуацию к нечётным числам?

Подсказка 4

Пусть среднее арифметическое s всех чисел не является степенью двойки. Рассмотрим операцию: заменить каждое число на сумму соседей. Можно ли с её помощью уравнять числа в круге?

Подсказка 5

Лемма: После k таких операций числа становятся близки к s · 2ᵏ. Для любого ε > 0 при достаточно большом k все числа попадут в интервал (s − ε)·2ᵏ, (s − ε)·2ᵏ). Как выбрать ε, чтобы этот интервал не содержал целых степеней двойки?

Подсказка 6

Если в наборе есть пара (a, b) с суммой a + b = 2ᵏ (k ≥ 2), мы можем выбрать для неё делитель либо 2, либо 4.

При выборе 2 новое среднее s₁

При выборе 4 новое среднее s₂ = s₁ + 2/n
Почему числа s₁ и s₂ не могут одновременно быть степенями двойки? Может ли Тая победить в данной ситуации?

Подсказка 7

Что делать, если в начальном наборе есть 1?

Показать ответ и решение

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

(1) Пусть у нас $n$ нечётных чисел. Тогда за одну операцию можно получить $n$ двоек.

(2) Пусть никакая сумма двух соседних чисел не является степенью двойки. Тогда за одну операцию можно получить ситуацию (1).

(3) Пусть среднее арифметическое $s$ всех чисел не равно степени двойки. Покажем, что сможем прийти к ситуации (2). Воспользуемся следующей леммой.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $a1,$ $a2,$ …, $an$ — вещественные числа, $s$ их среднее арифметическое. За один ход меняем набор $a1,$ $a2,$ …, $an$ на

a +a a + a a +a 1-2-2,-22--3,...,-n-2-1.

Тогда для любого $𝜀 >0$ через несколько ходов все числа будут лежать в интервале $(s− 𝜀,s+ 𝜀).$

Доказательство леммы. Сделаем переобозначения, пусть

s+x0,s+x1,...,s+xn

— данные числа, так что

x0+ ...+ xn = 0.

Пусть

M =max{|x0|,...,|xn|}.

Ясно, что после хода $M$ не увеличится. Достаточно понять, что через некоторое количество $k$ ходов этот максимум отклонения станет не более $λM$ для некоторого фиксированного $0< λ< 1.$ Ниже увидим, что можно положить $k= n$ и $λ = 2n−nn−1. 2$

Через $n$ ходов у нас будет набор $s+ y0,$ $s +y1,$ …, $s+yn,$ где

-1 ( 1 2 n−1 ) y0 = 2n x0+ Cnx1+ Cnx2+ ...+ Cn xn−1 +xn и т.д.

Так как

x0+ x1+ ...+xn =0,

имеем

1 2 n− 1 1 2 n−1 x0+ Cnx1+ Cnx2+...+Cn xn−1+ xn = (Cn− 1)x1+ (Cn− 1)x2+ ...+ (Cn − 1)xn− 1.

Отсюда

|y|≤ -1((C1 − 1)+ ...+ (Cn−1− 1))M = 2n− n-− 1M. 0 2n n n 2n

Аналогично все

2n−-n−-1 |yi|≤ 2n M,

что завершает доказательство леммы.

_________________________________________________________________________________________________________________________________________________________________________________

Ясно, что $s >1.$ Выберем $𝜀> 0$ так, чтобы интервал ( $s− 𝜀,s +𝜀$ ) целиком помещался между соседними степенями двойки:

2t−1 < s− 𝜀<s +𝜀< 2t

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

N N (2 (s− 𝜀),2 (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. По сравнению с первой попыткой $s$ увеличилось на $-2 n ,$ поэтому мы окажемся в ситуации (3).

(5) Пусть набор исходных чисел произвольный. Тогда после одной операции замены пары чисел на сумму имеем ситуацию (4).

Ответ:

да

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#75128Максимум баллов за задание: 7

Даны натуральные числа $a$ и $b$ такие, что $a≥ 2b.$ Существует ли многочлен $P (x)$ степени больше $0$ с коэффициентами из множества ${0,1,2,...,b− 1}$ такой, что $P(a)$ делится на $P (b)?$

Источники: Всеросс., 2023, ЗЭ, 10.3(см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Как известно, для целочисленного многочлена P выражение P(a) − P(b) кратно a − b. Если подобрать такой многочлен P, что P(b) = a − b, задача будет решена.

Подсказка 2:

Как насчёт того, чтобы рассмотреть a − b в системе счисления с основанием b?

Показать ответ и решение

Легко видеть, что если $b= 1,$ то всякий многочлен с коэффициентами от 0 до $b− 1$ является нулевым.

Пусть $b >1.$ Представим $a− b$ в $b$ -ичной записи (иными словами, в системе счисления с основанием $b$ ): $n a− b= cnb + ...+ c1b+ c0,$ где $ci ∈{0,1,2,...,b− 1}.$ Поскольку $a− b ≥b,$ в этой записи $n≥ 1.$

Покажем, что $n P (x)= cnx + ...+c1x+ c0$ удовлетворяет условию. Действительно, по теореме Безу, для любого многочлена $f$ с целыми коэффициентами $f(a)− f(b)$ делится на $a− b.$ Значит, $P (a)− P(b)$ делится на $a − b= P(b).$ Но тогда и $P (a)= (P (a)− P(b))+ P(b)$ делится на $P(b).$

Ответ:

Существует при $b> 1$

Ошибка.
Попробуйте повторить позже

Задача 18#90097Максимум баллов за задание: 7

У $100$ школьников есть стопка из $101$ карточки, которые пронумерованы числами от $0$ до $100.$ Первый школьник перемешивает стопку, затем берет сверху из получившейся стопки по одной карточке, и при каждом взятии карточки (в том числе при первом) записывает на доску среднее арифметическое чисел на всех взятых им на данный момент карточках. Так он записывает $100$ чисел, а когда в стопке остается одна карточка, он возвращает карточки в стопку, и далее все то же самое, начиная с перемешивания стопки, проделывает второй школьник, потом третий, и т.д. Докажите, что среди выписанных на доске $10000$ чисел найдутся два одинаковых.

Источники: ВСОШ, ЗЭ, 2023, 10.2 и 11.2 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

Попробуйте посмотреть, какие множества чисел могут получаться у школьников на 1 шаге, на 2 шаге, на 100 шаге?

Подсказка 2

Попробуйте в явном виде найти все возможные значения, находящиеся в этих множествах. Как найти одинаковые среди них?

Подсказка 3

Рассмотрите первое, второе и сотое множества, а именно их объединение. Сколько в нëм чисел?

Показать доказательство

На $1$ -м шаге у каждого из $100$ человек было выписано одно из чисел множества

A1 = {0,1,2,...,100}

На $2$ -м шаге — одно из чисел множества

{ 1 2 3 199} A2 = 2,2,2,..., 2

На $100$ -м шаге выписано одно из чисел множества

{ S S− 1 S− 2 S− 100 } A100 = 100,-100-,-100-,...,-100--

где $S = 100-⋅101- 2$ — сумма всех чисел (а вычитается — число на оставшейся в конце карточке).

Видим, что ${ 1 2 3 199 200} A1 ∪A2 =A2 = 0,2,2,2,..., 2 , 2 ,$ так что $|A1∪ A2|= 201.$ Далее, $|A100|=101,$ но числа $1 1 50− 2,50,50+ 2$ принадлежат $A2∩A100,$ значит, $|A1 ∪A2∪ A100|≤ 201 +101− 3= 299.$

Итак, мы показали, что $300$ чисел, выписанных на $1$ -м, $2$ -м и $100$ -м шагах, могут принимать не более $299$ различных значений. Следовательно, какие-то два из них равны.

Ошибка.
Попробуйте повторить позже

Задача 19#107141Максимум баллов за задание: 7

Дано число $a ∈(0,1).$ Положительные числа $x , 0$ $x , 1$ $x, 2$ …, $x n$ удовлетворяют условиям

x0+ x1+...+xn = n +a

1-+ -1+ ...+ -1 =n + 1. x0 x1 xn a

Найдите наименьшее возможное значение выражения

2 2 2 x0+x1+ ...+ xn.

Источники: Всеросс., 2023, ЗЭ, 10.8(см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

И правда ответ n + a². Теперь попробуйте переписать сумму квадратов x_i через сумму квадратов 1 - x_i для того, чтобы избавится от n в правой части.

Подсказка 3

Теперь нам достаточно доказать, что сумма квадратов (1 - x_i) больше, чем (1 - a)^2. Тут надо рассмотреть два случая. Попробуйте понять почему при x₀ ≤ a задача очевидна, где x₀ — минимальное из x_i.

Подсказка 4

Если же x₀ ≥ a, то попробуйте из каждого слагаемого вынести соответственное x_i и оценить его a.

Показать ответ и решение

Будем доказывать ответ $n+ a2.$ Заметим, что при $x =a 0$ и $x = x = ...= x = 1 1 2 n$ достигается равенство. Перепишем

∑ 2 ∑ 2 ∑ ∑ 2 xk = (1− xk) + 2 xk − (n+ 1)= (1 − xk) +n +2a− 1

Поэтому достаточно доказать, что

∑ 2 2 (1− xk) ≥(1− a)

Пусть $x0$ — наименьшее из чисел. При $x0 ≤ a$ имеем

∑ (1− xk)2 ≥ (1 − x0)2 ≥(1− a)2

Пусть $x0 ≥a,$ то

∑ ∑ ( 1 ) (1− x0)2 = xk x- − 2+ xk k

Так как $xk+ x1k ≥ 2,$ а значит, скобки из суммы неотрицательны. Следовательно,

∑ ( ) ∑ ( ) ( ) xk -1 − 2 +xk ≥a -1 − 2 +xk =a n+ 1− 2(n +1)+ n+ a = (1− a)2 xk xk a

Что и требовалось.

Ответ:

$n +a2$

Ошибка.
Попробуйте повторить позже

Задача 20#128454Максимум баллов за задание: 7

Квадрат $100×100$ разбит на квадраты $2× 2.$ Потом его разбивают на доминошки (прямоугольники $1 ×2$ и $2× 1).$ Какое наименьшее количество доминошек могло оказаться внутри квадратов разбиения?

Источники: ВСОШ, ЗЭ, 2023, 10.6 (см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

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

Подсказка 2:

Находить их в явном виде плохо, это просто не сделать (разбиений на домино очень много). Значит, нужно найти некоторые объекты, которые будут их "детектировать", то есть просто говорить, что они точно есть. Подумаем, какие самые тривиальные детекторы могут быть?

Подсказка 3:

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

Подсказка 4:

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

Подсказка 5:

В такие моменты полезно попробовать обобщить идею! Как же будет звучать наше предположение?

Подсказка 6:

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

Подсказка 7:

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

Подсказка 8:

Итого, мы нашли 50 требуемых доминошек. Кажется, можно найти больше...

Подсказка 9:

Осознайте, каким образом можно найти ещё 50 доминошек. Итого, есть оценка на 100 доминошек. Может, можно ещё больше?

Подсказка 10:

Спустя несколько попыток Вы, скорее всего, потерпели неудачу. Может, тогда пора переходить к примеру?

Подсказка 11:

Пример за Вами, однако скажем, что он достаточно "однородный"... Успехов!

Показать ответ и решение

Пример. Верхнюю и нижнюю горизонтали разобьём на горизонтальные доминошки — они окажутся в квадратах $2×2.$ Остальной прямоугольник $98× 100$ разобьём на вертикальные доминошки — они не окажутся в квадратах $2 ×2.$

Оценка. Рассмотрим квадраты $A1,$ $A3,...,A99$ размеров $1× 1,$ $3× 3,...,99× 99,$ у которых левый нижний угол совпадает с левым нижним углом исходного квадрата $100 ×100.$ Для каждого из квадратов $Ai$ $(i= 1,3,...,99)$ найдётся доминошка $Xi,$ пересекающая его сторону (поскольку квадраты нечётной площади не разбиваются на доминошки). Легко видеть, что $Xi$ лежит внутри квадратика $2× 2$ из разбиения. Аналогично, рассматривая квадраты $B1,B3,...,B99$ размеров $1×1,$ $3× 3,...,99× 99,$ у которых правый верхний угол совпадает с правым верхним углом исходного квадрата $100× 100,$ находим ещё $50$ нужных нам доминошек $Yj$ ( $j = 1,3,5,...,99).$ Это завершает решение (очевидно, что все доминошки $X1,$ $X3,...,X99,$ $Y1,$ $Y3,...,Y99$ различны).

Ответ:

100

Следующая подтема