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

Закл (финал) 10 класс → .11 Закл 2024

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

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

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

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

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

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

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

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

Задача 1#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$ лежит в этой прогрессии.

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

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

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

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

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

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

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

Задача 4#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)

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

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

Задача 5#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.$ Противоречие.

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

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

Курсы

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

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

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

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

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

Задача 8#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).

Ответ:

да

Предыдущая подтема

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