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

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

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

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

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

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

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

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

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

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

Задача 1#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$

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

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

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

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

На доску выписали 777 попарно различных комплексных чисел. Оказалось, что можно ровно 760 способами выбрать два числа $a$ и $b,$ записанных на доске, так, чтобы выполнялось равенство

2 2 a + b +1= 2ab.

Способы, которые отличаются перестановкой чисел, считаются одинаковыми. Докажите, что можно выбрать такие два числа $c$ и $d,$ записанных на доске, что

2 2 c +d + 2025 =2cd.

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

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

Подсказка 1:

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

Подсказка 2:

Верно! На квадрат разности. Имеем (a − b)² = −1, то есть a − b = ±i. Аналогично преобразуем выражение, которое нужно доказать: (с − d)² = −45. Итого, нужно найти пару с разницей 45i. Что это означает?

Подсказка 3:

Нужно найти 46 "подряд идущих" чисел с разницей в i. Формально, мы хотим найти числа a₁, a₂, ..., a₄₆ с разницей ровно i между соседними. Тогда a₁ и a₄₆ будут являться искомой парой. В подобных задачах бывает полезно ввести граф.

Подсказка 4:

Разумеется, вершины — числа, ребро проводим, если разница между числами равна i. Хотим найти путь длины 46. Какие замечания можно сделать про этот граф?

Подсказка 5:

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

Подсказка 6:

Граф представляет собой набор непересекающихся простых путей (так называемых бамбуков). Докажите это самостоятельно. Каждый такой путь — отдельная компонента связности, являющаяся деревом. Вершин в графе 777, рёбер — 760. Какой вывод из этих фактов можно сделать?

Подсказка 7:

В графе ровно 17 компонент связности (докажите это), то есть 17 путей, общая длина которых 760. Дело за малым — докажите, что путь длины хотя бы 45 найдется. Успехов!

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

Заметим, что условие $a2+ b2+ 1= 2ab$ равносильно тому, что

2 (a− b) =− 1

или же $a − b= ±i.$ Рассмотрим граф, вершины которого — записанные на доску числа, а ребро проводится между двумя числами, которые отличаются на $i.$ Согласно условию задачи, в таком графе ровно 760 рёбер. Каждая компонента связности этого графа представляет собой путь и состоит из вершин-чисел вида $z,$ $z+ i,$ $z+ 2i,$ …, $z +(n− 1)i.$ Предположим, что в этом графе $k$ компонент связности. Тогда в нём $777− k$ рёбер, поэтому $k= 17.$ Поскольку $17⋅45= 765< 777,$ то в какой-то компоненте связности хотя бы 46 вершин, поэтому какие-то две из этих вершин — это числа $c$ и $d= c+ 45i.$ Тогда

2 2 2 (c− d) =45 ⋅i =− 2025,

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

2 2 c +d + 2025 =2cd,

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

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

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

Дана прямая призма $ABCA B C . 1 1 1$ Известно, что треугольники $A BC, 1$ $AB C, 1$ $ABC 1$ и $ABC$ — остроугольные. Докажите, что точки пересечения высот этих треугольников вместе с точкой пересечения медиан треугольника $ABC$ лежат на одной сфере.

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

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

Обозначим через $M$ и $H$ точки пересечения медиан и высот треугольника $ABC,$ а также отметим точку $T$ так, что

−−→ −−→ −−→ −−→ 3MT = AA1 = BB1 = CC1.

Пусть сфера $ω$ построена на отрезке $HT$ как на диаметре. Поскольку прямая $MT$ перпендикулярна плоскости $ABC,$ то точка $M$ лежит на $ω.$ Покажем, что на сфере $ω$ лежит точка пересечения высот $H1$ треугольника $A1BC;$ рассуждение для двух других треугольников аналогично.

$PIC$

Обозначим через $N$ середину отрезка $BC.$ Поскольку $NA = 3NM,$ точка $T$ лежит на отрезке $A1N,$ в частности, она лежит в плоскости $A1BC.$ Пусть $AA ′$ — высота треугольника $ABC.$ Поскольку прямая $AA1$ перпендикулярна плоскости $ABC,$ то $∠A1AA ′ =90∘,$ а также $A′A1 ⊥ BC$ по теореме о трёх перпендикулярах, то есть точка $H1$ лежит на отрезке $A1A′.$ Поскольку точка, симметричная точке пересечения высот $H$ треугольника $ABC$ относительно прямой $BC,$ лежит на его описанной окружности, то $A′H ⋅A′A= A′B⋅A′C.$ Применяя то же рассуждение для треугольника $A1BC,$ мы получаем, что

A ′H1 ⋅A′A1 =A ′B ⋅A′C = A′H ⋅A′A.

Следовательно, четырёхугольник $AHH1A1$ вписанный, поэтому $∠HH1A1 = 180∘− ∠A1AH =90∘.$ Поскольку ещё $HA ′ ⊥BC$ и $H1A ′ ⊥BC,$ вновь применяя теорему о трёх перпендикулярах, мы получаем, что прямая $HH1$ перпендикулярна плоскости $A1BC.$ Значит, $∠HH1T =90∘,$ то есть точка $H1$ лежит на сфере $ω,$ что и требовалось.

Аналогично доказывается, что точки пересечения высот треугольников $AB1C$ и $ABC1$ также лежат на сфере $ω.$ Таким образом, все пять точек (точки пересечения высот четырёх треугольников и точка пересечения медиан треугольника $ABC$ ) лежат на сфере $ω.$

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

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

Пару многочленов $F(x,y)$ и $G(x,y)$ с целыми коэффициентами назовём важной, если из делимости на 100 обеих разностей

F(a,b)− F (c,d) и G (a,b)− G(c,d),

где $a,b,c,d$ — целые, следует, что числа $a− c$ и $b− d$ делятся на 100. Существует ли такая важная пара многочленов $P(x,y)$ и $Q (x,y),$ что пара многочленов $P(x,y)− xy$ и $Q(x,y)+ xy$ тоже является важной?

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

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

Подсказка 1:

Запишем в условие задачи в общем виде. У нас есть достаточное условие (А) для выполнения утверждения (В). Как вообще можно исследовать подобные конструкции? Например, подставить какой-то особенный набор в А, чтоб получить два утверждения В про него, которые либо наложат какие-то ограничения, либо приведут к противоречию. Разумеется, нас интересуют только остатки чисел по модулю 100, поэтому дальнейшие рассуждения ведутся в F₁₀₀. Подумайте, какие наборы было бы полезно подставить.

Подсказка 2:

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

Подсказка 3:

Начнём вводить обозначения в лоб. Пусть есть два набора (a ≥ b) и (c ≥ d) такие, что F(a, b) = F(c, d), G(a, b) = G(c, d). Тогда из условия А получаем, что a − c и b − d делятся на 100. Всё бы ничего, если a − c, b − d > 99. Такое вполне может быть. Но мы же хотим получить дополнительные ограничения...

Подсказка 4:

Значит, нужно ограничить a, b, c, d так, что a − c, b − d < 100. Какой самый простой способ это сделать?

Подсказка 5:

Просто взять a, b, c, d ≤ 99. То есть при этих ограничениях мы знаем, что если F(a, b) = F(c, d), G(a, b) = G(c, d), то (a, b) = (c, d). Отлично, давайте запишем теперь это построже и более масштабно.

Подсказка 6:

Рассмотрим всевозможные пары (a, b), где a, b ∈ F₁₀₀. Для каждой пары рассмотрим пару O(a, b) = [F(a, b), G(a, b)]. Мы поняли, что O(a, b) различны для различных пар (a, b). Но и пары (a, b) и пары O(a, b) — это просто комбинации остатков (mod 100). Что это значит?

Подсказка 7:

Что все пары O(a, b) — всевозможные пары остатков, причём каждая пара встречается один раз. Вернёмся к тому, о чём спрашивают в задаче. Если многочлены P(x, y) − xy и Q(x, y) + xy являются важной парой, то для них должно выполняться то же условие, что мы получили. Пока что не особо понятно, какой всё-таки ответ. В таких случаях нужно попробовать сначала доказать, что не существует, а если не получится это доказать (или хотя бы что-то нащупать), то уже пробовать строить пример. Итак, попробуем доказать, что не существует.

Подсказка 8:

Пусть для удобства теперь F(x, y) = P(x, y) − xy, G(x, y) = Q(x, y) + xy. O(x, y) = [F(x, y), G(x, y)], R(x, y) = [P(x, y), Q(x, y)]. Предположим, что F(x, y), G(x, y) — важные. Знаем, что набор {O(x, y), x, y ∈ F₁₀₀} = {R(x, y), x, y ∈ F₁₀₀} = {(x, y), x, y ∈ F₁₀₀}. Хотим найти противоречие. Доказывать, что какой-то пары остатков в {O(x, y)} нет — гиблый номер, ибо мы для этого ничего не знаем. Значит, нужно действовать хитрее и посмотреть на эти пары с другой точки зрения.

Подсказка 9:

Вся задача крутится вокруг модульной арифметики. Не будем же нарушать тенденции. Поскольку в {R(x, y)} есть всевозможные пары остатков, то там есть всевозможные пары с точки зрения чётности. Какой вывод из этого можно сделать?

Подсказка 10:

Осознайте, что если рассмотреть R(Ч, Н), R(Н, Ч), R(Ч, Ч), R(Н, Н) то мы получим перестановку набора (Н, Ч), (Ч, Н), (Н, Н), (Ч, Ч), где Ч, Н — произвольное чётное число и нечётное соответственно. Значит, для O(x, y) должно выполняться то же самое свойство. Но так ли это?

Подсказка 11:

Осталось просто разобрать случаи и осознать, что вот в этом и кроется проблема. У вас всё получится!

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

Пусть пара многочленов $F$ и $G$ — важная. Рассмотрим пары остатков от деления на 100 чисел $F(a,b)$ и $G (a,b),$ где $a,b$ — всевозможные пары целых чисел от 0 до 99. Согласно условию задачи, все такие пары остатков разные. Поскольку всего пар чисел $2 100,$ то каждая пара остатков от деления на 100 достигается ровно один раз. Значит, достигаются все 4 возможные пары чётностей чисел $F(a,b),$ $G(a,b).$ Поскольку чётность значения многочлена с целыми коэффициентами в точке $(a,b)$ зависит только от чётности чисел $a$ и $b,$ мы получаем, что пары значений

(F(0,0);G(0,0)), (F(1,0);G (1,0)), (F(0,1);G (0,1)), (F(1,1);G(1,1))

дают все четыре возможные пары чётностей. Однако заметим, что для пар многочленов $F = P,G= Q$ и

F(x,y)= P(x,y)− xy, G(x,y) =Q(x,y)+xy

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

Ответ:

не существует

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

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

Дано натуральное число $N.$ Куб со стороной $2N +1$ сложен из $(2N + 1)3$ единичных кубиков, каждый из которых — либо чёрный, либо белый. Оказалось, что среди любых 8 кубиков, имеющих общую вершину и образующих куб $2× 2× 2,$ не более 4 чёрных кубиков. Какое наибольшее количество чёрных кубиков могло быть использовано?

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

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

Подсказка 1:

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

Подсказка 2:

Раз куб со стороной 2N + 1, то логичнее всего начать рассматривать случай куба 3×3×3. Исследуйте возможные примеры, удовлетворяющие условию.

Подсказка 3:

Уверены, пример на 18 вы построили, подумайте ещё и осознайте, что пример на 20 тоже строится несильно сложно. Теперь стоит подумать насчёт оценки...

Подсказка 4:

Она здесь тривиальная, рассмотрим два диагонально противоположных куба 3×3×3 и вот уже оценка на ≤ 20 готова (осознайте это). Итого, мы поняли, что для этого куба ответ 20. В такие моменты бывает очень полезно изучить число 20, а тем более то, как оно зависит от N (в нашем случае N = 1).

Подсказка 5:

20 = 2 * 2 * 5 = (N + 1)²(4N + 1) = 4N²(4N + 1) = 20N = 4N²(N+4) = ... (в случае N = 1). Также понятно, что ответ около трети от (2N+1)³. Очевидно, что в общем виде это многочлен с коэффициентом 4 при N³. Также естественное желание свести константы к минимуму (ну или оставить ± единички). На что это намекает?

Подсказка 6:

На то, что ответ, скорее всего, равен (N+1)²(4N + 1). Попробуем доказать эту гипотезу. С чего мы начнём?

Подсказка 7:

Разумеется, с примера, ведь подогнать пример под ответ проще, чем оценку (банально в силу наглядности). Итак, вперёд пробовать!

Подсказка 8:

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

Подсказка 9:

А от подобных мыслей недалеко до декартовой системы координат. Введём же её так, что все вершины единичных кубиков будут иметь целые координаты от 0 до 2N + 1. Рассмотрим произвольный куб 2×2×2. Хотим как-то в зависимости от координат вершин его кубиков определять его цвет.

Подсказка 10:

Но наборов координат всего 27, а кубиков 8, не хотелось бы рассматривать все эти наборы координат, в идеале для каждого кубика оставить свою координату, а ещё круче, если они будут выбраны "одинаково".

Подсказка 11:

Попробуем выбрать "наконечник" куба 2×2×2, то есть в каждом маленьком кубике рассмотрим вершину, которая ближе всего к началу координат. Этот наконечник образует куб из 8 вершин. Как координаты этих вершин записываются в общем виде?

Подсказка 12:

(a, b, c); (a + 1, b, c); (a, b + 1, c); (a, b, c + 1); (a + 1, b + 1, c); (a + 1, b, c + 1); (a, b + 1, c + 1); (a + 1, b + 1, c + 1). С какой точки зрения мы можем посмотреть на эти числа, учитывая, что a, b, c — произвольные?

Подсказка 13:

С точки зрения чётности! И нам нужно покрасить ровно 4 кубика в чёрный цвет. Как же это сделать?

Подсказка 14:

Давайте сделаем так, чтобы кубики, у которых в выбранном наборе координат хотя бы 2 чётные, будут чёрными, а остальные — белыми. Осознайте, что это искомый пример. Путём несложных вычислений докажите, что всего чёрных кубиков при такой раскраске ровно (N+1)²(4N+1). Осталось подогнать оценку под пример, однако наш пример уже достаточно сложный и идейный, может попробовать как-то использовать его в оценке?

Подсказка 15:

Давайте вместо отдельной оценки попробуем доказать оптимальность нашего примера (осознайте, что эти идеи разные). Пусть в общем виде кубик тёмный, если в нашем примере он чёрный, и светлый — если в примере он белый (то есть кубик вполне может быть тёмным и светлым одновременно). Раз пример аналитический, то оценка, скорее всего, такая же. В примере мы используем идеи чётности и расстояний, и они отлично работают, может стоит вновь прибегнуть к ним? Давайте для каждой целочисленной точки в нашей ДСК (a, b, c) введём определение t-ранга. t-ранг — минимальное расстояние до грани куба, перпендикулярной соответствующей оси (разумеется, t ∈ {x, y, z}). Значения рангов — r_x, r_y, r_z. А просто рангом точки (a, b, c) — r будем называть min(r_x, r_y, r_z). Вспомним про наши идеи, что можно сделать дальше?

Подсказка 16:

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

Подсказка 17:

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

Подсказка 18:

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

Подсказка 19:

Разумеется, ∑ = сумма всех кратностей чёрных кубиков — сумма кратностей белых кубиков. Итого, опираясь на некоторую "интуицию", мы ввели много обозначений и что-то поняли про ∑. Кажется, пришло время вновь немного поисследовать, посмотреть случаи. Рассмотрим произвольный кубик 2×2×2, пусть ранги его центра — r_x, r_y, r_z. Для однозначности будем считать, что r_x ≤ r_y ≤ r_z. Разберём несколько случаев.

Подсказка 20:

1) r_x < ry;
2) r_x = r_y = 1/2 + d, где d — чётно;
3) r_x = r_y = 1/2 + d, где d — нечётно.
Аккуратно разберите каждый случай и осознайте, что кратности всех тёмных кубиков не больше 4, а всех светлых — не меньше 4 (именно тёмных и светлых, а не чёрных и белых). Отличное продвижение. Давайте теперь для удобства введём обозначения кратностей: s₁ ≤ s₂ ≤ ... ≤ s_{(2N+1)³} С учётом продвижения и построенного примера, что можно сказать про эти кратности?

Подсказка 21:

Что s₁ + ... + s_{(N+1)²(4N+1)} = s_{(N+1)²(4N+1)+1} + ... + s_{(2N+1)³}, так как в примере ∑ = 0. Фух, осталось совсем немного. Осталось красиво завершить оценку противоречием. Пусть в раскраске чёрных кубиков > (N+1)²(4N+1). Что тогда?

Подсказка 22:

0 ≥ ∑ > s₁ + ... + s_{(N+1)²(4N+1)} − s_{(N+1)²(4N+1)+1} − ... − s_{(2N+1)³} = 0. В этой цепочке неравенств есть одно упущение (осознайте какое и допишите его, не забудьте обосновать). В итоге мы получили, что 0 > 0, если кубиков > (N+1)²(4N+1). Кажется, это победа)

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

Положим $k= (N + 1)2(4N + 1).$ Введём систему координат так, что все вершины единичных кубиков будут иметь целые координаты от 0 до $2N + 1.$

Начнём с примера, показывающего, что количество чёрных кубиков действительно может быть равно $k.$ У каждого кубика рассмотрим его вершину, ближайшую к началу координат (её координаты принимают значения от 0 до $2N$ ). Пусть кубик чёрный, если хотя бы две координаты этой вершины чётны, и белый иначе. Ясно, что тогда в любом кубе $2 ×2× 2$ будет ровно 4 чёрных и 4 белых кубика. При этом количество чёрных кубиков, у которых все три соответствующих координаты чётны, равно $3 (N + 1),$ а количество кубиков, у которых чётны ровно две координаты, равно $2 3(N + 1)N,$ поэтому общее количество чёрных кубиков будет равно $k.$

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

Для каждой точки с координатами $(a,b,c)$ в большом кубе назовём её $x,$ $y$ - и $z$ -рангом соответственно числа

rx = min(a,2N + 1− a)

ry = min(b,2N + 1− b)

rz = min(c,2N + 1− c)

Назовём рангом этой точки число $r =min(r,r,r ). x y z$ Иначе говоря, $x,$ $y$ - или $z$ -ранг точки — это расстояние от неё до ближайшей грани большого куба, перпендикулярной соответствующей оси, а её ранг — это просто расстояние от неё до ближайшей грани большого куба.

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

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

Пусть $rx,$ $ry$ и $rz$ — это $x$ -, $y$ - и $z$ -ранги центра некоторого кубика; пусть для определённости $rx ≤ ry ≤ rz.$ Тогда нетрудно видеть, что

если $rx < ry,$ то кратность этого кубика равна 4;
если
$rx =ry = 1 +d, 2$
где $d$ чётно, то кратность кубика меньше 4, и он тёмный;
если
$rx =ry = 1 +d, 2$
где $d$ нечётно, то кратность кубика больше 4, и он светлый.

Итак, кратности всех тёмных кубиков не больше 4, а всех светлых — не меньше 4.

Пусть теперь

s1 ≤s2 ≤ ⋅⋅⋅≤ s(2N+1)3

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

s1 +s2+ ⋅⋅⋅+ sk − sk+1− ⋅⋅⋅− s(2N+1)3 = 0,

поскольку в приведённом выше примере значение $∑$ было равно 0.

Если теперь в рассматриваемой раскраске $ℓ>k$ чёрных кубиков, то

∑ 0 ≥ ≥ s1+s2+ ⋅⋅⋅+ sℓ − sℓ+1 − sℓ+2− ⋅⋅⋅− s(2N+1)3 >

> s1+ s2+ ⋅⋅⋅+sk− sk+1− ⋅⋅⋅− s(2N+1)3 = 0,

поскольку $sk+1 ≥4.$ Это противоречие показывает, что $ℓ≤ k,$ что и требовалось доказать.

Ответ:

$(N +1)2(4N +1)$

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

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

По кругу выписаны 100 единиц. Петя и Вася играют в игру, каждый делает по $1010$ ходов. Петя каждым своим ходом выбирает 9 стоящих подряд чисел и уменьшает каждое из них на 2. Вася каждый своим ходом выбирает 10 стоящих подряд чисел и увеличивает каждое из них на 1. Ребята ходят по очереди, начинает Петя. Докажите, что Вася сможет действовать так, чтобы после каждого его хода среди 100 выписанных чисел было не менее пяти положительных, как бы ни играл Петя.

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

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

Подсказка 1:

Нам нужно гарантировать 5 положительных чисел в любой момент. Есть несколько способов доказывать подобные утверждения. Первый способ: для любого момента доказать, что эти 5 чисел где-то найдутся, то есть просто доказать их существование. Второй способ: построить некоторый алгоритм ходов за Васю, зафиксировав некоторые числа, и доказать, что в любой момент именно они будут подходить (ну либо какие-то из них). Что же нам выбрать?

Подсказка 2:

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

Подсказка 3:

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

Подсказка 4:

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

Подсказка 5:

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

Подсказка 6:

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

Подсказка 7:

Вася может сделать так, чтобы она не уменьшалась. А изначально сумма в паре положительна. Кажется, стратегия за Васю напрашивается сама собой, осталось найти 5 нужных пар. Успехов!

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

Обозначим записанные по кругу числа $a, 1$ $a , 2$ …, $a . 100$ Вася будет следить лишь за десятью числами, которые он разобьёт на пары: $(a9,a18),$ $(a27,a36),$ …, $(a90,a99).$ За один ход Петя может уменьшить не более, чем одно из этих 10 чисел. Если Петя уменьшил одно из чисел пары $(ai,ai+9),$ Вася в ответ добавит 1 к числам $ai,$ $ai+1,$ …, $ai+9.$ Если же Петя не уменьшил ни одно из этих 10 чисел, Вася сделает любой разрешённый ход. Таким образом, после пары ходов Пети и Васи сумма чисел в каждой из пяти Васиных пар не уменьшится. Поскольку изначально пять сумм в парах положительны, то после каждого Васиного хода сумма в каждой из этих пяти пар будет положительной, поэтому в каждой из пар будет хотя бы одно положительное число. Таким образом, после любого Васиного хода будет хотя бы 5 положительных чисел, что и требовалось.

Курсы

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

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

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

Четырёхугольник $ABCD,$ в котором нет параллельных сторон, вписан в окружность $Ω.$ В треугольники $DAB,$ $ABC,$ $BCD,$ $CDA$ вписаны окружности $ωa,$ $ωb,$ $ωc,$ $ωd$ соответственно. Проведены общие внешние касательные к окружностям $ωa$ и $ωb,$ $ωb$ и $ωc,$ $ωc$ и $ωd,$ $ωd$ и $ωa,$ не содержащие сторон четырёхугольника $ABCD.$ Четырёхугольник, последовательные стороны которого лежат на четырёх проведённых прямых (именно в таком порядке), вписан в окружность $Γ .$ Докажите, что прямые, соединяющие центры окружностей $ωa$ и $ωc,$ $ωb$ и $ωd,$ $Ω$ и $Γ ,$ пересекаются в одной точке.

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

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

Пусть, не умаляя общности, лучи $AD$ и $BC$ пересекаются в точке $Q,$ лучи $AB$ и $DC$ пересекаются в точке $P.$ Обозначим через $I a$ центр окружности $ωa,$ точки $Ib,Ic,Id$ определим аналогично.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Четырехугольник $IaIbIcId$ является прямоугольником, стороны которого параллельны биссектрисам внутренних углов $P$ и $Q.$

Доказательство. Докажем, что прямая $IaId$ параллельна биссектрисе внутреннего угла $Q.$

Действительно, пусть $W$ и $N$ — середины дуг $AB$ и $CD,$ не содержащие остальные вершины четырехугольника, соответственно. Тогда в силу леммы о трезубце $WIa = W Id,$ но прямая $WN$ является биссектрисой угла $IaW Id,$ поэтому $IaId ⊥ WN.$

$PIC$

С другой стороны, углы между парами прямых $W N,BC$ и $W N,AD$ равны полусуммам пар дуг $BN,CW$ и $AW, ND,$ а значит, равны, следовательно, $W N$ перпендикулярна биссектрисе угла $Q.$ Аналогично, $IbIc$ параллельна последней.

$PIC$

Как известно, биссектрисы внутренних углов $P,Q$ перпендикулярны, следовательно, четырехугольник $II II a bc d$ суть прямоугольник, поскольку пары его противоположных стороны параллельны биссектрисам.

_________________________________________________________________________________________________________________________________________________________________________________

Перейдем к решению. Таким образом, в силу доказанной леммы точка пересечения прямых $IaIc,IbId$ является центром описанной окружности $ω$ прямоугольника, т.е. достаточно показать, что окружности $Ω,Γ ,ω$ имеют общую радикальную ось.

Обозначим четырёхугольник, образованный четырьмя касательными через $′ ′ ′ ′ A B C D$ (прямая $′ ′ AB$ — общая внешняя касательная к $ωa$ и $ωb,$ аналогично с тремя другими сторонами). Пусть прямая $IaId$ пересекает прямую $AD$ в точке $Xad.$ Точки обозначим через $γ$ описанную окружность четырёхугольника $AIaIdD.$

Тогда точка $Xad$ — радикальный центр окружностей $γ,$ $ω$ и $Ω,$ поскольку она лежит на двух их радикальных осях. Значит, радикальная ось окружностей $ω$ и $Ω$ проходит через точку $Xad,$ аналогично, на ней лежат и точки $Xab,Xbc,Xcd.$ В частности, эти 4 точки лежат на одной прямой.

$PIC$

Пусть прямая $B′C ′$ пересекает сторону $AB$ в точке $S$ и сторону $CD$ в точке $T.$ Поскольку $B′C′ ∥AD,$ то $∠BST = ∠BAD = 180∘− ∠BCT,$ поэтому четырёхугольник $BCT S$ — вписанный. Поскольку $C′D′ ∥AB$ и $A′B ′ ∥CD,$ то по теореме Фалеса

XbcB′ = XbcXab-= XbcS. XbcT XbcXcd XbcC ′

Из этого равенства отношений и вписанности $BCT S$ мы получаем, что

XbcB′⋅XbcC ′ =XbcS ⋅XbcT =XbcB ⋅XbcC,

то есть степень точки $Xbc$ относительно окружностей $Ω$ и $Γ$ одинакова. Рассуждение для точек $Xab,Xad,Xcd$ аналогично. Итого доказано требуемое утверждение.

$PIC$

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

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

Пусть $f :ℝ→ ℝ$ — непрерывная функция. Хордой будем называть отрезок целой длины, параллельный оси абсцисс, концы которого лежат на графике функции $f.$ Известно, что у графика функции $f$ ровно $N$ хорд, причём среди них есть хорда длины 2025. Найдите наименьшее возможное значение $N.$

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

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

Для натурального $n$ положим $g (x)= f(x+ n)− f(x). n$ Тогда число хорд длины $n$ равно количеству нулей функции $gn(x).$

В качестве примера выберем следующую кусочно-линейную функцию $f$ : $f(x)= x$ при $-9 x≤ 202410$ и

20249 f(x)= -10--⋅|2025− x|

при $9 x≥ 202410.$ Заметим, что при $[ 1 ] a ∕∈ 0;202510$ функция $f(x)$ принимает значение $f(a)$ только в точке $a.$ Следовательно, если $gn(x)=0,$ то обе точки $x$ и $x+ n$ лежат в отрезке $[ ] 0,2025 110.$ В частности, $n ≤ 2025,$ и нули функции $gn(x)$ лежат в промежутке $[ ] 0;2025110 − n .$ Для $n =2025$ при $[ ] x∈ 0, 110$ имеем $g2025(x)= 20248x.$ Значит, $g2025(x)$ имеет единственный нуль $x= 0,$ то есть хорда длины 2025 у функции $f$ единственна. При натуральном $n≤ 2024$ функция $gn(x)$ монотонно убывает при $x∈[0,2025− n]$ и монотонно возрастает при $[ ] x ∈ 2025− n,2025110 − n ,$ при этом $gn(0)> 0,$ $gn(2025− n)< 0,$ $gn(2025 110-− n)> 0.$ Таким образом, у этой функции ровно два нуля, то есть функция $f$ имеет по две хорды длины $n =1,2,...,2024.$ Итого у неё 4049 различных хорд.

Теперь перейдём к оценке. Без ограничения общности будем считать, что хорда длины 2025 соединяет точки $(0;0)$ и $(2025;0),$ то есть $f(0)=f(2025)= 0.$

Положим

g(x)=g1(x) =f(x+ 1)− f(x).

Из условия следует, что у функции $g$ конечное число нулей, а также эта функция непрерывна. Пусть все её нули лежат в промежутке $[−M, M].$ Тогда функция $g$ знакопостоянна на лучах $x> M$ и $x< −M.$ При необходимости, заменив функцию $f$ на $− f,$ будем считать, что $g(x)> 0$ при $x> M.$

Предположим, что $g(x) <0$ при $x< −M.$ Заметим, что

gn(x)= g(x)+ g(x+ 1)+...+g(x+ n− 1),

поэтому $gn(x)> 0$ при $x> M$ и $gn(x)< 0$ при $x <− M − n.$ Значит, функция $gn(x)$ имеет нуль, то есть у функции $f$ есть хорда любой натуральной длины, что противоречит условию.

Таким образом, $g(x)> 0$ при $x< −M.$ Значит, $gn(x)> 0$ при $x >M$ и при $x <− M − n.$ Далее мы докажем, что при натуральных $k$ и $m,$ в сумме дающих 2025, функция $f$ имеет хотя бы 4 хорды длин $k$ и $m.$ Применяя это утверждение для каждой такой пары, получим оценку. Иными словами, докажем, что у функций $gk(x)$ и $gm(x)$ при $k+ m = 2025$ суммарно хотя бы 4 нуля.

Предположим, что это не так. Тогда функция $gk$ имеет не более одного нуля. Значит, $gk(x)$ не может быть отрицательной. Действительно, если $gk(t)< 0,$ то по непрерывности и знакам при больших $|x|$ функция имеет хотя бы два нуля, противоречие.

Итого $gk(x)≥0,$ причём равенство нулю достигается не более чем в одной точке. Покажем, что $gm (t)> 0$ для некоторого $t∈ (0,k).$ Рассмотрим наименьшее натуральное $N,$ для которого $Nk$ делится на 2025, и обозначим остатки $r1,$ $r2,$ …, $rN−1$ от деления чисел $k,$ $2k,$ …, $(N − 1)k$ по модулю 2025. Если $gk(0)> 0,$ положим $r0 =rN = 0;$ если $gk(0)= 0,$ положим $r0 = rN =2025.$ Рассмотрим разности

dj = f(rj+1)− f(rj), j = 0,1,...,N − 1.

Если $rj+1 > rj,$ то $rj+1 = rj + k$ и $dj =gk(rj)≥ 0;$ если же $rj+1 <rj,$ то $rj = rj+1+ m$ и $dj =−gm (rj+1).$ Если $r0 = 0,$ то $d0 = gk(0)> 0.$ В случае $rN =2025$ получаем $dN−1 = gk(2025 − k)> 0,$ поскольку $gk(0)= 0$ и $2025− k⁄= 0.$ Таким образом,

d0+ d1+...+dN−1 =0,

и одно из крайних слагаемых положительно. Значит, найдётся $dj < 0,$ что возможно только при $rj = rj+1+ m$ и $dj = −gm (rj+1).$ Тогда для $t= rj+1 ∈[0,k]$ получаем $gm(t)= −dj > 0.$

Заметим, что

gk(0)+ gm(k) =gm(0)+gk(m)= f(2025)− f(0)= 0.

Поскольку $gk ≥ 0,$ то $gm(0)≤ 0$ и $gm(k)≤0,$ в частности, $t⁄= 0$ и $t⁄=k,$ то есть $t∈ (0,k).$ В случае $gk(0)>0$ и $gk(m )> 0$ получаем $gm(0)< 0,$ $gm(t)> 0,$ $gm(k)<0,$ а также $gm (x)> 0$ при больших $|x|.$ Тогда у $gm$ есть нули на промежутках $(−∞,0),$ $(0,t),$ $(t,k),$ $(k,∞ ),$ то есть хотя бы 4 нуля.

Если $gk(0)= 0,$ то $gk(m)> 0,$ так как у $gk$ не более одного нуля. Тогда $gm(k)=0,$ $gm(t)>0,$ $gm(0)< 0.$ В этом случае у $gm$ есть нули на $(−∞, 0)$ и $(0,t),$ а также в точке $k,$ и ещё один нуль в точке $0$ есть у $gk,$ что даёт хотя бы 4 нуля. Случай $gk(m )= 0$ разбирается аналогично.

Ответ:

4049

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

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

Квартал представляет собой клетчатый квадрат $10× 10.$ В новогоднюю ночь внезапно впервые пошёл снег, и с тех пор каждую ночь на каждую клетку выпадало ровно по 10 см снега; снег падал только по ночам. Каждое утро дворник выбирает один ряд (строку или столбец) и сгребает весь снег оттуда на один из соседних рядов (с каждой клетки — на соседнюю по стороне). Например, он может выбрать седьмой столбец и из каждой его клетки сгрести снег в клетку слева от неё. Сгребать снег за пределы квартала нельзя. Вечером сотого дня года в город приедет инспектор и найдёт клетку, на которой лежит сугроб наибольшей высоты. Цель дворника — добиться, чтобы эта высота была минимальна. Сугроб какой высоты найдёт инспектор?

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

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

Подсказка 1.

Хочется верить, что в оптимальном примере во всех непустых ячейках почти поровну снега.

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

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

Докажем, что после сотого утра найдется сугроб высотой не менее $112$ дм. Предположим, что такого сугроба нет. Так как дворник в сотое утро полностью сгреб снег с какого-то ряда, в десяти клетках квадрата снега нет. В каждой из оставшихся $90$ клеток, по нашему предположению, не более $111$ $3 дм$ снега, то есть всего снега не больше, чем $9990$ $3 дм .$ Однако за $100$ ночей суммарно выпало $10000$ $3 дм$ снега. Противоречие.

Покажем, как может действовать дворник, чтобы после сотого утра каждый сугроб имел высоту не более $112$ дм, то есть в каждой клетке было не более $112$ $3 дм$ снега.

Способ 1. Первые $11$ дней дворник сгребает снег из второго столбца в первый, следующие $11$ дней дворник сгребает снег из третьего столбца во второй, затем $11$ дней из четвёртого в третий, и т. д. Через $99$ дней в десятом столбце не будет снега. Посчитаем, сколько снега стало в столбце $i≤ 9$ через $99$ дней. Вечером $11(i− 1)$ -го дня в столбце номер $i$ не было снега, а в столбце $i+ 1$ в каждой клетке было по $11(i− 1)$ $дм3$ снега. На следующий вечер в столбце $i$ станет по $11(i− 1)+ 2$ $дм3$ снега в каждой клетке. Затем ещё десять дней количество снега в каждой клетке $i$ -го столбца будет увеличиваться на $2,$ а затем $11(9− i)$ дней — на $1.$ Итого, через $99$ дней в каждой клетке столбца $i$ будет по

11(i− 1)+22+ 11(9− i) =110 дм3 снега.

В сотую ночь выпадет ещё по $1$ $дм3$ в каждую клетку. А сотым утром дворник сгребёт снег из десятого столбца в девятый. Таким образом, в каждой клетке будет не более $112$ $дм3$ снега.

_________________________________________________________________________________________________________________________________________________________________________________

Способ 2. Пусть дворник сгребёт снег из $2$ -го столбца в $1$ -ый, из $3$ -го во $2$ -й, …, из $10$ -го в $9$ -ый. Тогда вечером девятого дня в первых девяти столбцах будет по $10$ дм $3$ снега в каждой клетке, а в десятом столбце снега не будем. Затем дворник проделывает аналогичный процесс в обратном порядке: из $9$ -го в $10$ -ый, из $8$ -го в $9$ -ый, …, из $2$ -го в первой. Тогда вечером $18$ -го дня в клетках последних девяти столбцов будет по $20$ $дм3$ снега, а в первом столбце не будет снега. Аналогично повторим такие сдвиги (каждый длится $9$ дней) ещё $9$ раз (всего $11$ сдвигов), и через $99$ дней получим в клетках девяти столбцов по $110$ $дм3$ снега и один крайний столбец пустой. Сотым утром сгребаем снег из этого крайнего в соседний и получаем не более $112$ $дм3$ снега в каждой клетке.

Ответ:

1120 см

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

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

В пространстве расположен бесконечный цилиндр (т.е. геометрическое место точек, удалённых от данной прямой $ℓ$ на данное расстояние $R > 0$ ). Могут ли шесть прямых, содержащих рёбра некоторого тетраэдра, иметь ровно по одной общей точке с этим цилиндром?

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

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

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

Подсказка 4:

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

Подсказка 5:

Либо на ту, которая содержит ось цилиндра, либо на ту, которая перпендикулярна ей. В первом случае цилиндр станет двумя параллельными прямыми, в другом — окружностью. Какой же случай нравится нам больше, учитывая, что мы рассуждаем о касаниях?

Подсказка 6:

Разумеется, второй. Пусть A, B, C, D — образы вершин тетраэдра после проецирования. Подумаем, чем стали прямые, содержащие рёбра?

Подсказка 7:

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

Подсказка 8:

Могли, но не более 3 (подумайте почему). То есть, не умоляя общности, можно сказать, что прямые AB, AC, AD различны. Ничего не смущает?...

Подсказка 9:

Они же все касаются окружности (образа цилиндра) и имеют общую точку. Кажется, такое бывает примерно никогда) Успехов!

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

Предположим, что такая конструкция существует. Спроецируем тетраэдра на плоскость $α,$ перпендикулярную прямой $ℓ.$ Проекцией цилиндра будет некоторая окружность $ω.$ Обозначим проекции вершин тетраэдра через $A,$ $B,$ $C,$ $D,$ они все будут различны (в противном случае одна из прямых, содержащих стороны тетраэдра, будет параллельна $ℓ,$ такая прямая не может иметь с цилиндром ровно одну общую точку). Каждая из прямых, соединяющих точки $A,$ $B,$ $C,$ $D$ должна иметь с окружностью $ω$ одну общую точку, то есть касаться этой окружности. При этом точки $A,$ $B,$ $C,$ $D$ не могут лежать на одной прямой (поскольку вершины тетраэдра не лежат в одной плоскости). Значит, либо на одной прямой лежат какие-то три из них, не умаляя общности $B,$ $C,$ $D,$ либо никакие три из этих точек на одной прямой не лежат. В любом случае прямые $AB,$ $AC,$ $AD$ попарно различны, однако они все касаются окружности $ω$ и проходят через точку $A,$ противоречие.

$PIC$

Ответ:

не могут

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

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

Тройку положительных чисел $(a,b,c)$ назовём загадочной, если

∘-----1------ ∘ ----1------- ∘-----1------ a2+ a2c2 + 2ab+ b2+ b2a2 + 2bc+ c2+ c2b2 +2ca= 2(a +b+ c)

Докажите, что если тройка $(a,b,c)$ — загадочная, то тройка $(c,b,a)$ — тоже загадочная.

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

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

Подсказка 1

Рассмотрите условие загадочности. Попробуйте свести сложное равенство к более простому условию на a, b, c.

Подсказка 2

Проанализируйте первое подкоренное выражение: a² + 1/(a²c²) + 2ab. Заметьте: если бы 1/(a²c²) равнялось b², то получился бы полный квадрат. Что в этом случае можно сказать о загадочности тройки?

Подсказка 3

Если abc = 1, то b = 1/(ac) ⇒ b² = 1/(a²c²). Тогда, сворачивая полные квадраты в подкоренных выражениях, получаем загадочное равенство. Можно ли похожие преобразования провести в случаях неравенства?

Подсказка 4

Если abc < 1, то b < 1/(ac) ⇒ b² < 1/(a²c²). Можно ли и дальше проводить преобразования аналогично случаю для равенства, меняя "=" на знак неравенства?

Подсказка 5

Если abc > 1, то b > 1/(ac) ⇒ b² > 1/(a²c²). Получим: √(a² + 1/(a²c²) + 2ab) < √(a² + b² + 2ab) = a + b. Как это повлияет на всю сумму?

Подсказка 6

Загадочное равенство достигается только при abc = 1. Почему это доказывает, что (c, b, a) тоже загадочная тройка?

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

Покажем, что тройка $(a,b,c)$ — загадочная в том и только в том случае, когда $abc= 1,$ из этого немедленно последует требуемое в задаче.

Пусть $abc= 1,$ тогда $-1 b =ac$

∘-----1------ ∘---------- ∘ ------ a2+ a2c2-+2ab= a2+ b2+ 2ab= (a +b)2 =a +b,

ведь $a,b,c$ положительны. Аналогично

∘------------ ∘ ------------ b2+ -1--+2bc= b+c, c2+ -1-+ 2ca =c+ a, b2a2 c2b2

из этого следует, что тройка замечательная.

Предположим, что $abc< 1.$ Тогда $b2 <-1- a2c2$ и аналогично случаю для равенства, получаем неравенство:

∘ -----1------ ∘---------- a2+ a2c2 + 2ab> a2+ b2 +2ab= a+ b,

аналогично

∘------------ ∘ ------------ b2+ -122-+2bc> b+c, c2+ 212 + 2ca >c+ a. ba cb

Итого, в этом случае левая часть равенства из условия больше правой. Рассуждая аналогично, в случае $abc>1$ имеем, что правая часть больше левой, и только в случае $abc= 1$ достигается равенство, что и требовалось.

Интенсивы

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

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

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

Юрий подошёл к великой таблице майя. В таблице 200 столбцов и $2200$ строк. Юрий знает, что в каждой клетке таблицы изображено солнце или луна, и любые две строки отличаются (хотя бы в одном столбце). Каждая клетка таблицы закрыта листом. Поднялся ветер и сдул некоторые листы: по два листа с каждой строки. Могло ли так случиться, что теперь Юрий хотя бы про 10000 строк может узнать, что в каждой из них изображено в каждом из столбцов?

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

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

Подсказка 1.

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

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

Заметим, что существует всего $2200$ различных строк длины $200,$ в которых каждый символ — солнце или луна; значит, каждая такая строка встречается в таблице ровно один раз. Разобьём все позиции на две половины по $100$ столбцов — «левую» и «правую». Предположим, что в каждой строке, в которой есть два солнца в одной половине (назовём их солнечными), ветер сдул листья с одной из таких пар солнц, а в каждой несолнечной строке — таких строк $2 101$ — ветер обнаружил положения всех солнц, ведь в несолнечной строке не более двух солнц, так что ветер мог так поступить. Тогда Юрий сообразит, что те строки, где открыты два солнца в одной половине — точно солнечные, а значит, несолнечные строки — это в точности те $2 101$ строк, в которых ветер не открывал два солнца в одной половине. У каждой из них открыты все солнца, так что закрытые листьями изображения в этих строках — луна.

Ответ:

могло

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

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

Четырёхугольник $ABCD,$ в котором нет параллельных сторон, вписан в окружность $ω.$ Через вершину $A$ проведена прямая $ℓ ∥BC, a$ через вершину $B$ — прямая $ℓb ∥CD,$ через вершину $C$ — прямая $ℓc ∥DA,$ через вершину $D$ — прямая $ℓd ∥AB.$ Четырёхугольник, последовательные стороны которого лежат на этих четырёх прямых (именно в этом порядке), вписан в окружность $γ.$ Окружности $ω$ и $γ$ пересекаются в точках $E$ и $F.$ Докажите, что прямые $AC,BD$ и $EF$ пересекаются в одной точке.

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

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

Подсказка 1.

Если в задачах с окружностями требуется доказать, что 3 прямые пересекаются в одной точке, часто помогает найти 3 окружности, радикальными осями которых являются эти прямые. К тому же в нашей задаче EF определяется как радикальная ось каких-то окружностей.

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

Первое решение. Без ограничения общности можно считать, что лучи $AB$ и $DC;$ $CB$ и $DA$ пересекаются. Пусть отрезки $AC$ и $BD$ пересекаются в точке $G,$ а также $′ ′ ′′ AB C D$ — четырёхугольник, образованный прямыми $ℓa,$ $ℓb,$ $ℓc,$ $ℓd.$ Также обозначим через $X$ пересечение $AB$ и $′ CD ,$ через $Y$ — пересечение $CD$ и $′ AB .$

Пусть $′ ∠BAB = α.$ Из вписанности четырёхугольника $′ ′′ ′ AB C D$ и условий $AX ∥ ℓd,$ $CY ∥ ℓb$ имеем:

′ ∘ ′ ′ ′ ′ ′ ′ α= ∠B AX = 180 − ∠A B C = ∠C D X = ∠Y CA.

Значит, во-первых, точки $A,$ $D ′,$ $X,$ $C′$ лежат на одной окружности, обозначим её $γ1 :$ во-вторых, точки $C,$ $Y,$ $A′,$ $B′$ лежат на одной окружности, обозначим её $γ2 :$ в-третьих, точки $A,$ $X,$ $C,$ $Y$ лежат на одной окружности, обозначим её $γ0.$ Заметим, что точка $B$ — радикальный центр окружностей $γ,$ $γ , 0$ $γ 1$ (поскольку она лежит на прямых $AX$ и $C ′D ′);$ точка $D$ — радикальный центр окружностей $γ,$ $γ , 0$ $γ 2$ (так как она лежит на прямых $CY$ и $A ′B′).$ Таким образом, $BD$ — радикальная ось окружностей $γ 0$ и $γ;$ $AC$ —радикальная ось окружностей $γ 0$ и $ω;$ $EF$ — радикальная ось окружностей $ω$ и $γ,$ поэтому эти три прямые пересекаются в одной точке, что и требовалось доказать.

$PIC$

Второе решение. Введём обозначения как в первом решении. Для точки плоскости $P$ обозначим через $f(P)$ разность степеней точки $P$ относительно окружностей $ω$ и $γ.$ Поскольку $EF$ — радикальная ось окружностей $ω$ и $γ,$ то достаточно доказать, что $f(G )=0.$ Кроме того, легко видеть, что $f(A)= −AC ′⋅AB ′$ и $f(C)= CD ′⋅CA ′.$

Заметим, что функция $f$ — линейная, то есть для точки $P$ на отрезке $QR$ выполнено равенство

f(P)= PR-⋅f(Q)+-PQ-⋅f(R-)(⋆). QR

Мы докажем это утверждение позднее. Пока, применив его для точек $A,G,C,$ мы получим, что

AG-⋅f(C)+-CG-⋅f(A-) f(G)= AC .

Таким образом, достаточно доказать, что $−ff((AC)) = ACGG-(∗∗).$

Заметим, что

AG- d(A,BD-) SADD- AB-⋅AD- GC = d(C,BD ) = SBCD = CB ⋅CD

(последнее равенство следует из того, что $∠BAD + ∠BCD =180∘;$ через $d(P,ℓ)$ мы обозначаем расстояние от точки $D$ до прямой $ℓ).$ Следовательно, равенство ( $∗∗$ ) переписывается в виде:

′ ′ AC′-⋅ AB′ = AB-⋅AD-. CD CA CB ⋅CD

Из вписанности четырёхугольника $ABCD$ и данных в условии параллельностей прямых следуют равенства углов:

∠CAD = 180∘− ∠ADB ′ = ∠BAD = 180∘− ∠BCD = ∠CBC′ = ∠AC ′B,

∠ABC ′ = ∠CDA ′ =∠BCD ′ = ∠B′AD.

Таким образом, $′ △ABC$ и $′ △CDA ,$ а также $′ △DAB$ и $′ △BCD$ подобны по двум углам. Из подобия получаем равенства отношений

′ ′ AC′ = AB + AB-′ = AD-, CA CD CD BC

остаётся лишь перемножить эти равенства.

$PIC$

Вернёмся к доказательству линейности функции $f.$ Введём декартовы координаты таким образом, чтобы центры окружностей $ω$ и $γ$ лежали на оси абсцисс, пусть их координаты будут $(x1,0)$ и $(x2,0),$ а радиусы окружностей $− R1$ и $R2.$ Тогда для произвольной точки $P$ с координатами $(x,y)$ по определению степени точки мы получаем, что

(x− x )2 f(P)= (x− x1)2+ y2− R21−--y22--+R22 = ax +b,

где $a$ и $b$ — две константы. Если точка $P$ лежит на отрезке $QR$ и $xq$ , $xr$ — координаты точек $Q$ и $R$ по оси абсцисс, то $x = PR⋅xqQ+RPQ⋅xr,$ откуда немедленно следует (*).

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

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

Остроугольный неравнобедренный треугольник $ABC$ вписан в окружность $ω$ с центром в точке $O,$ его высоты пересекаются в точке $H.$ Через точку $O$ проведена прямая, перпендикулярная $AH,$ а через точку $H$ — прямая, перпендикулярная $AO.$ Докажите, что точки пересечения этих прямых со сторонами $AB$ и $AC$ лежат на одной окружности, которая касается окружности $ω.$

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

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

Подсказка 1.

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

Подсказка 2.

Основным способом является угадывание точки касания. У неё должен быть какой-то способ построения, поэтому есть смысл рассмотреть частные случаи, чтобы понять побольше про него.

Подсказка 3.

Например, разберите случаи AB=AC и ∠B=90°.

Подсказка 4.

В случае AB=AC видим, что точка касания лежит на AH, причём она совпадает или с A, или с диаметрально противоположной A. В случае же ∠B=90° получаем, что точка касания лежит на AH (даже совпадает с H), причём не совпадает с A. На какую мысль это может натолкнуть?

Подсказка 5.

Хочется выдвинуть гипотезу того, что точка касания D — второе пересечение AH с описанной окружностью ABC. Тем более у неё есть множество хороших свойств.

Подсказка 6.

Сначала докажем, что D лежит на искомой окружности. Заметим, что A и D симметричны относительно XY, H и D симметричны относительно BC. Отсюда можем получить различные равенства углов.

Подсказка 7.

Получим, что ∠XYD = ∠BHD, тогда остаётся доказать, что BZHD вписан. Сделайте это несложным счётом углов.

Подсказка 8.

А теперь докажите, что описанная окружность DXY касается описанной окружности ABC, учитывая, что D и A симметричны относительно XY.

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

Пусть прямая $AH$ повторно пересекает окружность $ω$ в точке $D.$ Тогда прямая, проведённая по условию через $O$ — серединный перпендикуляр к хорде $AD,$ пусть она пересекает стороны $AB$ и $AC$ в точках $X$ и $Y,$ а прямая через $H$ из условия задачи пересекает их в точках $Z$ и $T.$ Поскольку $XY ∥ AC,$ то окружность $(AXY )$ касается окружности $ω$ в точке $A.$ При симметрии относительно $XY$ окружность $ω$ переходит в себя, а окружность $(AXY )$ переходит в окружность $(DXY ),$ тогда она тоже касается окружности $ω.$

$PIC$

Поскольку $ZH ⊥ AO,$ то

∠AZH = 90∘− ∠OAB = ∠ACB = ∠ADB.

Следовательно, четырёхугольник $BZHD$ — вписанный. Тогда

∠BZD = ∠BHD =90∘− ∠HCB = ∠ACB.

Значит, в силу сказанного выше,

∠XY D =∠AY X = ∠ACB = ∠BZD,

поэтому точка $Z$ лежит на окружности $(DXY ).$ Аналогично, на этой окружности лежит и точка $T,$ откуда и следует требуемое.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Можно рассуждать несколько иначе: установить (похожими равенствами углов), что точки $X,Y,Z,T$ лежат на одной окружности, а также что окружности $(DXY )$ и $(DZT )$ касаются окружности $ω$ в точке $D.$ Однако эти три окружности не могут быть различными, поскольку в таком случае их радикальные оси не пересекаются в одной точке, в чём нетрудно убедиться. Значит, все эти окружности совпадают, что нам и требовалось.

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

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

В стране $n >100$ городов и пока нет дорог. Правительство наугад определяет стоимость строительства дороги (с двусторонним движением) между каждыми двумя городами, используя по разу все суммы от 1 до $n(n− 1)∕2$ талеров (все варианты равновероятны). Мэр каждого города выбирает самую дешёвую из $n − 1$ возможных дорог, идущих из этого города, и она строится (это может быть взаимным желанием мэров обоих соединяемых городов или только одного из двух).

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

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

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

Подсказка 1

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

Подсказка 2

Может ли существовать путь между двумя такими дорогами? Не противоречит ли его существование правилам, по которым мэры выбирают дороги для строительства?

Подсказка 3

Из предыдущего следует: число компонент M равно числу надёжных дорог. Как найти математическое ожидание? Вспомните линейность математического ожидания. На какие простые случайные величины стоит разложить M?

Подсказка 4

Введите для каждой пары городов {A,B} индикатор ξ(AB) = 1 (если AB — надёжная дорога), иначе 0. Тогда M — это сумма индикаторов по всем парам. Чему равно математическое ожидание одного из них?

Подсказка 5

Для фиксированной пары {A,B}: AB надёжна ⇔ AB дешевле всех дорог, инцидентных A или B. Сколько таких дорог? Зная их количества и равномерное распределение цен, можно подсчитать вероятность, что дорога AB надежна.

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

Дорогу, которую хотят строить сразу два мэра, назовём надёжной. Рассмотрим в каждой компоненте самую дешёвую дорогу $AB.$ Тогда она является надёжной. Предположим, что в этой компоненте есть ещё одна надёжная дорога $CD$ (ясно, что города $C,$ $D$ отличны от $A,$ $B$ ) и рассмотрим путь по дорогам от одного из городов $A,$ $B$ до одного из городов $C,$ $D$ — не умаляя общности, он имеет вид $AX1X2...XkC$ (города $X1,...,Xk$ отличны от $A,$ $B,$ $C,$ $D,$ возможно, $k =0$ ). Тогда дорогу $AX1$ хочет строить мэр города $X1$ (мэр города $A$ хочет строить $AB$ ), дорогу $X1X2$ — мэр города $X2$ (мэр города $X1$ хочет строить $X1A$ ) и так далее, мэр города $C$ хочет строить дорогу $CXk,$ а не $CD$ — противоречие.

Итак, в каждой компоненте есть ровно одна надёжная дорога. Для каждой из $n(n−1) --2--$ пар городов $A,$ $B$ рассмотрим случайную величину $ξAB,$ которая равна $1,$ если $AB$ — надёжная дорога, и 0 в противном случае. Из доказанного следует, что $M$ есть сумма $ξAB$ по всем $n(n−1) --2--$ парам ${A,B }.$ Для данных $A,$ $B$ событие $ξAB = 1$ означает, что дорога $AB$ — самая дешёвая из $2n− 3$ дорог, выходящих из $A$ или $B,$ так что вероятность такого события равна $2n1−3$ (из симметричности распределения цен эти дороги равноправны, так что каждая из них является самой дешёвой с вероятностью $2n1−3$ ). Значит, математическое ожидание $ξAB$ равно $2n1−3,$ а математическое ожидание случайной величины $M$ равно сумме этих математических ожиданий по всем парам, то есть

n(n−-1). 2(2n − 3)

Ответ:

$-n(n-− 1) 2(2n− 3)$

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

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

Докажите, что существует такое $c> 0,$ что для любого нечётного простого $p =2k+ 1$ числа $10,21,32,$ …, $kk− 1$ дают хотя бы $c√p-$ различных остатков при делении на $p.$

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

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

Все сравнения в этом решении производятся по модулю $p.$ Если $a$ и $b$ — целые числа, причём $b$ не делится на $p,$ то через $a b$ мы обозначаем тот единственный остаток $c$ по модулю $p,$ для которого $a ≡bc.$

Пусть числа

0 1 2 k−1 1,2 ,3 ,...,k

дают ровно $d$ различных остатков при делении на $p.$ Обозначим $t= [p∕4].$ Тогда выражения вида

(2a)2a−1 2a−1 f(a)= (aa−1)2 = 2 a

при $1≤ a≤ t$ дают максимум $d2$ различных остатков.

Назовём пару натуральных чисел $(a,b)$ таких, что $1≤ a< b≤ t,$ исключительной, если $f(a)≡ f(b).$ Покажем, что для каждого $δ = 1,2,...,t− 1$ существует не более одной исключительной пары $(a,b),$ в которой $b− a= δ.$ Действительно, если $(a,b)$ — такая пара, то из

22a−1a≡ 22b−1b

вытекает, что

a 2δ b ≡ 2 ,

откуда

b= a+ δ ≡ 22δb+ δ,

или $b(1− 22δ)≡ δ.$ Такой остаток $b$ не более чем единственен (поскольку $δ ⁄= 0$ ), а по нему восстанавливается $a.$

Итого, существует не более чем $t− 1$ исключительная пара; обозначим их количество через $S.$ Пусть числа $f(1),f(2),...,f(t)$ дают ровно $l$ различных остатков по модулю $p,$ встречающихся $a1,a2,...,al$ раз соответственно. Тогда

∑l ai = t, S = ∑lC2 . i=1 i=1 ai

Верна следующая цепочка неравенств:

( l l ) ( ) t− 1≥ S = 1 ∑ a2i − ∑ ai ≥ 1 t2− t , 2 i=1 i=1 2 l

откуда

t2 t l≥ 3t−-2-> 3.

Вспоминая, что $l≤d2,$ получаем оценку

--- ---- d> ∘t∕3≥ ⌊∘ p∕12⌋.

Таким образом, в качестве искомой константы $c$ можно взять, например, число $1∕24:$ для простых $p <12$ неравенство $√p d > 24$ тривиально, а для $p >12$ следует из неравенства $[x]≥ x∕2$ при $x> 1.$

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

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

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

Задача 17#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$ различных значений. Следовательно, какие-то два из них равны.

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

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

Число $x$ таково, что $sin x+tgx$ и $cosx+ ctgx$ — рациональные числа. Докажите, что $sin2x$ является корнем квадратного уравнения с целыми коэффициентами.

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

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

Подсказка 1:

Ясно, что sin(2x) выражается через sin(x)cos(x). Если найти уравнение с таким корнем, то будет несложно получить корень sin(2x).

Подсказка 2:

Давайте заметим, что выражения a + b и ab будут целыми и инвариантными относительно перестановки синуса и косинуса. Почему бы в дополнение к выражению v = sin(x)cos(x) не взять выражение u = sin(x) + cos(x) и попробовать выразить ab и a + b через u и v?

Подсказка 3:

Вы должны были получить такие равенства: a + b = u + 1/v, ab = v + u + 1. Как из них получить нужное уравнение?

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

Положим $a= sinx+ tgx$ и $b= cosx+ ctgx.$ Введём обозначения:

u= sinx+ cosx

v = sinxcosx

По условию рациональными являются числа

c =a+ b= u+ v−1

d =a⋅b= v+ u+ 1

Отсюда

k= d− c= v+1 − v−1

Значит,

t= sin2x= 2v

является решением квадратного уравнения

2 t + 2t− (4+ 2kt)= 0

с рациональными коэффициентами, откуда следует требуемое.

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

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

В каждой строке таблицы $100× n$ в некотором порядке стоят числа от 1 до 100, числа в строке не повторяются (в таблице $n$ строк и 100 столбцов). Разрешается поменять местами в строке два числа, отличающиеся на 1, если они не стоят рядом. Оказалось, что с помощью таких операций нельзя получить двух одинаковых строк. При каком наибольшем $n$ это возможно?

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

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

Подсказка 1:

По условию нельзя одну строку перевести в другую. Что это означает в общем виде?

Подсказка 2:

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

Подсказка 3:

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

Подсказка 4:

Спустя время можно осознать, что арифметика не особо-то и вяжется сюда. Значит, думаем дальше. Мы меняем два элемента с разницей в 1. Хмм, попробуем просто поисследовать, что происходит при операции. Например, можно начать с анализа соседних чисел с теми, которые мы меняем...

Подсказка 5:

Пусть последовательность выглядела так: ...abc...def.... Меняем b и e. Знаем, что |b − e| = 1. Интересно, может ли случиться так, что b > c, а e < c?

Подсказка 6:

Конечно, нет. Иначе b ≥ c + 1, e ≤ c − 1, то есть b − e ≥ 2, ошибочка однако... Хм, на какую более общую идею это наталкивает?

Подсказка 7:

Отношения (в плане больше или меньше) сохраняются при перестановке b и e. Кажется, мы на верном пути! Итак, какая же у нас идея?

Подсказка 8:

Если рассмотреть в какой-то строке отношения между всеми соседними, то оно всегда будет оставаться таким же! Хммм, как бы изящно записать эти отношения?

Подсказка 9:

Наверное, с помощью знаков < и >. То есть каждой строке сопоставляем такую последовательность из 99 знаков, назовём её признаком. Получается, если у двух строк разные признаки, то одну из другой не получить. А если совпадают, всегда ли можно?

Подсказка 10:

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

Подсказка 11:

n ≤ 2⁹⁹ (осознайте почему). Попробуем же теперь построить пример.

Подсказка 12:

В явном виде строить его довольно трудно. Нужно действовать хитрее! Зафиксируем признак и докажем, что для него можно подобрать нужный набор чисел (доказать это необходимо в общем виде). Это будет ещё одна подзадача для самостоятельного решения) Дело за Вами! Мы в Вас верим!

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

Сопоставим строке $x , 1$ $x, 2$ …, $x 100$ чисел от 1 до 100 последовательность из 99 знаков < и > в соответствии с тем, как упорядочены соседние числа. То есть если $xk <xk+1,$ то $k$ -й знак в этой последовательности равен <, в противном случае он равен >.

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

Сопоставим каждой перестановке знаков расстановку чисел по следующему правилу (далее такие расстановки будем называть выделенными). При $k= 1,$ $2,$ …, $99$ если $xk > xk+1$ (т.е. $k$ -й знак <) поставим на место $xk$ наибольшее из не выбранных ранее чисел, если же $xk < xk+1$ — наименьшее из не выбранных ранее чисел.

Заметим, что при такой последовательности операций числа, не выбранные за первые $k$ шагов, будут образовывать отрезок натурального ряда (а выбранными окажутся несколько наибольших и несколько наименьших чисел от 1 до 100). В частности, $x1 = 1$ или $x1 = 100.$ Число $x100$ заменим на единственное оставшееся число.

Нетрудно видеть, что полученная расстановка чисел соответствует выбранной последовательности знаков. Всего выделенных расстановок будет столько же, сколько и различных последовательностей знаков, то есть $299.$ В силу сказанного выше, разрешёнными операциями никакие две из выделенных строк нельзя сделать одинаковыми. Таким образом, заполнив таблицу $100× 299$ выделенными строками, мы получаем пример для $n= 299.$

Теперь докажем, что из любой строки $A$ длины 100 можно получить выделенную строку $B$ с той же расстановкой знаков. Из этого последует, что $n ≤ 299.$

Предположим, что первые $t− 1$ знаков данной строки

A =(x1,...,x100)

и выделенной строки

B =(y1,...,y100)

совпадают. Если $t= 100,$ то и сами строки совпадают. Пусть $t<100.$ Без ограничения общности будем считать, что $xt < xt+1.$

В силу сказанного выше наборы чисел $yt,$ …, $y100$ и $xt,$ …, $x100$ совпадают и образуют отрезок натурального ряда с наименьшим числом $xt.$ Поскольку $yt < yt+1,$ можно менять в строке $A$ на месте $t$ с числом на единицу меньшим, пока на месте $t$ не окажется число $xt.$

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

Ответ:

$299$

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

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

Окружность $ω$ описана около треугольника $ABC,$ в котором $AB < AC.$ Биссектрисы треугольника $ABC$ пересекаются в точке $I.$ Из середины $M$ стороны $BC$ на прямую $AI$ опущен перпендикуляр $MH.$ Прямые $MH, BI$ и $AB$ ограничивают треугольник $Tb,$ а прямые $MH, CI$ и $AC$ ограничивают треугольник $Tc.$ Описанные окружности треугольников $Tb$ и $Tc$ повторно пересекают окружность $ω$ в точках $′ B$ и $′ C$ соответственно. Докажите, что точка $H$ лежит на прямой $′′ B C .$

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

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

Обозначим точки пересечения прямой $MN$ с прямыми $AB,$ $AC,$ $BI$ и $CI$ через $P,$ $Q,$ $X$ и $Y$ соответственно (см. рисунок). Пусть прямые $AI,$ $BI$ и $CI$ повторно пересекают $ω$ в точках $A1,$ $B1$ и $C1$ соответственно. Обозначим

∠BAI = ∠CAI =α,∠ABI = ∠CBI =β,∠ACI = ∠BCI =γ,

тогда $α+ β+ γ = 90∘$ из суммы углов треугольника $ABC.$ Поскольку $MH ⊥AI,$ имеем $∠AQM = 90∘− α.$ Так как четырехугольник $ABA1C$ — вписанный,

∘ ∘ ∠MA1C = 90 − ∠BCA1 = 90 − α

Таким образом,

∠MA1C + ∠MQC =180∘,

поэтому четырёхугольник $A1CQM$ — вписанный. Следовательно, $∠AQA1 = 90∘,$ откуда следует, что точки $A,$ $A1,$ $P,$ $Q$ лежат на окружности $γ,$ построенной на отрезке $AA1$ как на диаметре.

Теперь заметим, что

∠QC′C = ∠QY C = 90∘− ∠CIA1 = 90∘− α − γ =β

Однако из вписанности четырехугольника $BC′CB1$ мы получаем, что

∠CC ′B1 =∠B1BC =β =∠CC ′Q

Следовательно, точки $C ′,$ $Q$ и $B1$ лежат на одной прямой. Аналогично, точки $P,$ $B′$ и $C1$ лежат на одной прямой.

$PIC$

В силу сказанного выше и вписанности четырёхугольника $C1B1CB$ имеем, что

∠CC1B1 =β = ∠CYQ,

поэтому $C1B1 ∥ PQ.$ Поскольку четырёхугольник $B ′C1B1C′$ вписанный,

∠PB ′C′ = ∠C1B1C′ = ∠PQC ′.

Значит, четырёхугольник $′ ′ B QC P$ вписанный. Тогда радикальные оси его описанной окружности, окружности $γ$ и окружности $ω$ пересекаются в одной точке, а это прямые $′ ′ B C ,$ $PQ$ и $AA1.$ Следовательно, точка $H$ лежит на прямой $′ ′ B C ,$ что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Приведём другой способ закончить решение. После того, как установлено, что точки $′ C ,$ $Q$ и $B1$ лежат на одной прямой, и точки $P,$ $B′$ и $C1$ лежат на одной прямой. Обозначим через $N$ середину дуги $BAC.$ Пусть прямая $AX$ повторно пересекает окружность $ω$ в точке $T.$ Заметим, что

′ ∘ 1 ′ ∠CC Y =∠AQY =90 − α= 2∠CC B.

Следовательно, $′ CY$ — биссектриса угла $′ CC B,$ поэтому на прямой $′ C Y$ лежит точка $N.$ Аналогично, она лежит на прямой $′ XB .$ Применяя теорему Паскаля для точек $′ AT C B1BC$ мы получаем, что точка $X,$ точка $Q$ и точка пересечения $′ C T$ и $BC$ лежат на одной прямой. Следовательно, прямые $BC,$ $XQ$ и $′ C T$ Т пересекаются в одной точке, то есть точка $M$ лежит на $′ C T.$ Теперь применяем теорему Паскаля для точек $′ ′ ATC BNA1$ и получаем, что точки $X$ и $M$ вместе с точкой пересечения $AA1$ и $′ ′ B C$ лежат на одной прямой. Значит, точка $H$ лежит на $′ ′ B C ,$ что и требовалось.

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