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

Закл (финал) 11 класс → .05 Закл 2018

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

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

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

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

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

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

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

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

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

Дано натуральное число $k.$ На клетчатой плоскости изначально отмечено $N$ клеток. Назовем крестом клетки $A$ множество всех клеток, находящихся в одной вертикали или горизонтали с $A.$ Если в кресте неотмеченной клетки $A$ отмечено хотя бы $k$ других клеток, то клетку $A$ также можно отметить. Оказалось, что цепочкой таких действий можно отметить любую клетку плоскости. При каком наименьшем $N$ это могло случиться?

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

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

Обозначим через $N (k)$ ответ в задаче; положим $f(k)= [k+1]⋅[k+2]. 2 2$ Докажем сначала, что

[k+ 1] N(k)≥N (k− 1)+ -2-- при k ≥2

После отмечания исходных $N (k)$ клеток можно отметить хотя бы одну клетку $A$ ; это значит, что либо в столбце, либо в строке этой клетки уже отмечено $[ ] k+21$ других клеток - пусть для определённости в строке $ℓ.$

Мысленно отметим все клетки строки $ℓ.$ Ясно, что любую клетку по-прежнему можно отметить. Удалим из клетчатой плоскости строку $ℓ$ и сдвинем вместе две получившиеся полуплоскости так, чтобы снова получилась клетчатая плоскость. Теперь мы можем отметить любую клетку этой новой плоскости, отмечая на каждом шагу клетку, в кресте которой уже есть не менее $k− 1$ отмеченных клеток (поскольку из этого креста удалена одна клетка строки $ℓ$ ). Следовательно, изначально на этой плоскости должно было быть отмечено не менее $N(k− 1)$ клеток. Значит, на исходной плоскости сначала должно быть хотя бы $N (k − 1)$ отмеченных клеток не из $ℓ$ ; отсюда и следует $(∗).$

Поскольку $N(1)= 1,$ из доказанного неравенства (*) следует, что

N (k)≥ 1+ 1+ 2+2 +3+ 3+ 4+ ...= f(k) ◟-----k-сла◝га◜емых------◞

$PIC$

Осталось показать, как отметить $f(k)$ клеток так, чтобы затем можно было отметить любую другую клетку плоскости. Покажем по индукции, что подходит пример, показанный на рисунке, состоящий из двух «лесенок» высот $p= [k] 2$ и $q =[k+1] 2$ ; нетрудно понять, что в нём как раз $f(k)$ клеток. При $k= 1$ утверждение очевидно: при одной отмеченной клетке можно отметить любую клетку в её кресте, а затем и любую клетку вообще.

Для перехода индукции заметим, что можно последовательно отметить клетки $a ,a,...,a. 1 2 p$ После этого в строке, в которой они стоят, окажется $p+ q =k$ клеток, и в ней уже можно будет отметить любую клетку. Значит, можно, вычеркнув эту строку, уменьшить значение $k$ на $1$ и применить предположение индукции в оставшейся плоскости.

Ответ:

$[k+1] [k+2] { m(m+ 1), если k= 2m; N = -2- ⋅ 2-- = m2, если k= 2m − 1$

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

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

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

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

Многочлен $P(x)$ таков, что многочлены $P (P (P(x)))$ и $P(P(x))$ строго монотонны на всей вещественной оси. Докажите, что $P(x)$ тоже строго монотонен на всей вещественной оси.

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

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

Первое решение. Предположим, что многочлен $P (x)$ не является монотонным. Тогда найдутся такие $a⁄= b,$ что $P(a)= P(b),$ а значит, и $P(P(P (a))) =P(P(P(b))),$ то есть $P (P(P(x)))$ не монотонен.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Так как многочлен $P(P(x))$ монотонен, то он обязан иметь нечётную степень, а тогда он принимает все вещественные значения.

Пусть $a> b,$ тогда найдутся такие числа $xa$ и $xb,$ что $P (P (xa))= a,P (P (xb))= b.$ Так как старший коэффициент многочлена $P (P(x))$ всегда положителен, то этот многочлен возрастает, поэтому $xa > xb.$

Если старший коэффициент многочлена $P (x)$ положителен, то многочлен $P(P (P (x)))$ возрастает; отсюда получаем, что $P (P (P(xa)))> P(P(P(xb))),$ то есть $P(a)> P(b)$ для любых $a> b.$ Если же старший коэффициент отрицателен, то, аналогично, $P (P (P(xa)))< P(P(P(xb))),$ откуда $P (a)< P(b)$ для любых $a> b.$

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

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

Определим последовательность $a ,a,a ,... 1 2 3$ формулой $a = [n 20201817]. n$ Докажите, что существует такое натуральное число $N,$ что среди любых $N$ подряд идущих членов последовательности есть такой, десятичная запись которого содержит цифру $5.$ (Как обычно, через $[x]$ обозначается наибольшее целое число, не превосходящее $x.$ )

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

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

Обозначим $β =-1-. 2017$ Напомним, что частный случай неравенства Бернулли $(1+ x)2017 ≥ 1+2017x$ (при $x≥ −β$ ) можно переписать в виде $β 1+ βy ≥ (1 +y)$ (при $y = 2017x ≥− 1$ ).

_________________________________________________________________________________________________________________________________________________________________________________

Лемма 1. Для любого натурального п верны неравенства $n+1+β ( 1)β n+β n+1 ≤ 1+ n ≤ n$

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

( )β ( )β nn+-1 = 1− n+11 ≤1 −n-β+1 = n+n-1+−1-β

откуда $( ) (1+ 1n)β = nn+1 −β ≥ n+n+11−β-≥ n+n1++β1 .$

______________________________________________________________________________________________________________________________________________________

Лемма 2. Для любого натурального п верны неравенства $nβ − 1≤ an+1− an ≤ 2nβ + 1.$

Доказательство. Поскольку $n1+β − 1< an ≤ n1+β,$ достаточно доказать, что $nβ ≤(n+ 1)1+β − n1+β ≤ 2nβ,$ или

( 1)β 1≤ (n +1) 1+ n − n ≤2

Применяя лемму $1,$ получаем

( )β (n+ 1) 1+ 1 − n ≥(n+ 1)n+-1+β-− n= 1+ β > 1 n n+ 1

что доказывает левое неравенство. Аналогично, для правого имеем $(n+ 1)(1 +n1)β − n ≤ (n+1)(nn+β)− n = n(1+βn)+β-< 2.$

______________________________________________________________________________________________________________________________________________________

Перейдём к решению задачи. Покажем, что число $N =22017+ 1000$ подходит. Для этого достаточно доказать, что при любом натуральном $n ≥22017$ число с пятёркой в десятичной записи найдётся даже среди чисел $an,an+1,...,an+1000.$ Поскольку $n≥ 22017,$ найдётся натуральное $k$ такое, что $10k−1 ≤$ $≤ nβ∕2 <10k.$ Покажем, что даже среди $(k+ 2)$ -х с конца цифр чисел $an,an+1,...,an+1000$ встретится пятёрка, откуда и будет следовать требуемое.

По лемме $2,$ при каждом $d= n,n +1,...,n+ 999$ имеем $a − a ≤ 2dβ +1 ≤2 ⋅(2n)β +1 <4⋅nβ +1< 9⋅10k d+1 d$ это означает, что $(k+ 2)$ -я цифра при переходе от $a d$ к $a d+1$ либо не изменяется, либо увеличивается на $1$ (при этом $9$ переходит в $0$ ). С другой стороны, по той же лемме

( ) ad+100− ad ≥ 100 nβ − 1 ≥ 2⋅10k+1− 100 ≥10k+1;

это означает, что за $100$ таких переходов $(k+ 2)$ -я цифра обязана хотя бы раз изменить своё значение (на следующее по циклу). Значит, за $1000$ переходов она примет все $10$ возможных значений, в частности, побывает и пятёркой.

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

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

На сторонах $AB$ и $AC$ треугольника $ABC$ выбраны точки $P$ и $Q$ соответственно так, что $PQ ∥BC.$ Отрезки $BQ$ и $CP$ пересекаются в точке $O.$ Точка $′ A$ симметрична точке $A$ относительно прямой $BC.$ Отрезок $′ A O$ пересекает окружность $ω,$ описанную около треугольника $AP Q,$ в точке $S.$ Докажите, что окружность, описанная около треугольника $BSC,$ касается окружности $ω.$

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

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

$PIC$

Случай $AB = AC$ следует из симметрии; без ограничения общности будем считать, что $AC > AB.$

Выберем на $ω$ точку $X$ так, что $PAXQ$ — равнобокая трапеция. Тогда $∠XQP = ∠APQ = ∠ABC = ∠CBA′$ и, аналогично, $∠XP Q =∠BCA ′.$ Значит, $XQ ∥ BA′$ и $XP ∥CA′.$ Поэтому гомотетия с центром $O,$ переводящая отрезок $PQ$ в $CB,$ переводит треугольник $XP Q$ в $A′CB;$ следовательно, точка $O$ (а потому и точка $S$ ) лежит на $A ′X.$

Пусть $M$ — центр окружности, описанной около треугольника $ASA′.$ Тогда $∠MAA ′ = 90∘− ∠ASX.$ Поскольку $XA ∥ BC ⊥AA ′,$ получаем $∠MAX =∠MAA ′+ 90∘ = 180∘− ∠ASX,$ то есть $MA$ касается $ω$ в точке $A.$ Так как $MA =MS,$ то $MS$ также касается $ω.$

Пусть $Ω$ — окружность, описанная около треугольника $ABC;$ тогда $ω$ и $Ω$ гомотетичны с центром в $A,$ поскольку $P Q∥ BC.$ Значит, $MA$ также является касательной к $Ω.$ Кроме того, $M$ лежит на серединном перпендикуляре $BC$ к отрезку $AA′;$ поэтому $MA2 = MB ⋅MC.$ Итак, $MS2 = MA2 = MB ⋅MC,$ то есть $MS$ касается описанной окружности треугольника $BSC$ и $ω$ в точке $S.$ Отсюда и следует требуемое.

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

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

Даны положительные числа $x ,x ,...,x 1 2 n$ , где $n ≥ 2$ . Докажите, что

1 +x2 1+ x2 1+x2n−1 1 +x2 1+x11x2 + 1+-x22x3 + ...+ 1+xn−1xn-+1-+xnnx1 ≥n.

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

По неравенству о средних

-1+x21- -1+x22 1+x2n−1- -1+x2n-- ∘ -------------------- 1+x1x2-+1+x2x3 +...+-1+xn−1xn +-1+xnx1-≥ n-(1+-x21)⋅...⋅(1+-x2n)- n (1 +x1x2)⋅...⋅(1+ xnx1)

В условии требуют доказать, что левая часть этого неравенства не меньше 1, поэтому достаточно доказать, что правая часть (оценка снизу) не меньше 1, то есть

(1 +x21)⋅...⋅(1 +x2n)≥ (1 +x1x2)⋅...⋅(1+ xnx1)

В силу положительности чисел неравенство эквивалентно возведённому в квадрат

(1+ x2)(1+ x2)⋅(1+ x2)(1+x2)⋅...⋅(1+x2 )(1+ x2)⋅(1+ x2)(1+ x2)≥(1+ x x)2⋅(1 +x x )2...⋅(1+ x xn)2⋅(1 +xnx )2 1 2 2 3 n−1 n n 1 12 2 3 n− 1 1

Здесь последовательная пара скобок слева не меньше соответствующей скобки справа. Например,

2 2 2 (1+ x1)(1+ x2)≥ (1+x1x2),

поскольку

x21+ x22 ≥ 2x1x2.

Аналогично с остальными скобками.

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

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