Тема Региональный этап ВсОШ и олимпиада им. Эйлера

Регион 9 класс → .02 Регион 2015

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

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

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

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

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

Разделы подтемы Регион 9 класс

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

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

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

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

Источники: Всеросс., 2015, РЭ, 9.8(см. olympiads.mccme.ru)

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

Подсказка 1

С последовательностями из условия работать трудно. Попробуйте заменить их на более простые последовательности.

Подсказка 2

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

Подсказка 3

Подумайте, какое условие необходимо для того, чтобы в интересной последовательности появилась 3? (Учитывая, что соседние члены отличаются не более чем на 1)

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

Первое решение.

Обозначим $n =100.$ Назовём последовательность из $n$ натуральных чисел, любые два соседних члена которой различаются не больше, чем на $1,$ интересной. Каждой интересной последовательности $a1,a2,...,an$ сопоставим разностную последовательность $bi = ai+1− ai(i= 1,2,...,n− 1).$ Все члены разностной последовательности равны $0$ или $±1,$ так что количество всевозможных разностных последовательностей равно $n−1 3 .$

Посчитаем сначала количество $S$ всех интересных последовательностей, минимальный член которых не превосходит $3.$ Рассмотрим произвольную разностную последовательность $b1,b2,...,b99.$ Любые две интересные последовательности, соответствующие ей, отличаются прибавлением одного и того же числа к каждому члену. Значит, среди них ровно по одной последовательности с минимальным членом, равным $1,2$ и $3.$ Таким образом, $n−1 n S =3⋅3 = 3 .$

В $S$ учтены все последовательности, выписываемые Петей, и несколько лишних - тех, в которых не встречается $3.$ Ясно, что, если в интересной последовательности встречаются как числа, большие $3,$ так и меньшие $3,$ то и $3$ тоже встречается. Но минимальный член каждой лишней последовательности не больше $2,$ значит, и все их члены не превосходят $2.$ Итак, все лишние последовательности состоят из единиц и двоек. С другой стороны, каждая последовательность из единиц и двоек является интересной, и, стало быть, лишней.

Итого, лишних последовательностей ровно $2n,$ а значит, искомое количество равно $S − 2n = 3n− 2n.$

______________________________________________________________________________________________________________________________________________________

Второе решение.

Назовём хорошей последовательность из $n$ натуральных чисел, в которой хотя бы раз встречается тройка, а любые два соседних члена различаются не больше, чем на $1.$ Обозначим через $Sn$ количество хороших последовательностей длины $n.$ Мы докажем индукцией по $n,$ что $Sn =3n − 2n.$ База индукции при $n= 1$ очевидна.

Сделаем переход от $n$ к $n+ 1.$ Назовём хорошую $(n +1)$ членную последовательность $A$ отличной, если среди первых её $n$ членов встречается тройка. Откинем от каждой отличной последовательности её последний член; в каждом случае мы получим хорошую $n$ -членную последовательность. При этом, если хорошая $n$ -членная последовательность $A′$ оканчивается числом $1,$ то она получается таким образом из двух отличных — оканчивающихся числом $1$ или $2.$ Если же $A′$ оканчивается числом $k> 1,$ то она получается из трёх отличных, у которых в конце стоит $k − 1,k$ или $k+ 1.$ Итак, если количество $n$ -членных хороших последовательностей, оканчивающихся числом $1,$ равно $Tn,$ то количество отличных $(n+ 1)$ -членных последовательностей равно $2Tn+ 3(Sn− Tn)=3Sn− Tn.$

Осталось посчитать количество неотличных $(n+ 1)$ -членных последовательностей. Ясно, что каждая из них оканчивается числом $3;$ если эту тройку откинуть, получится $n$ -членная последовательность $A′$ без троек. Поскольку её соседние члены отличаются не больше, чем на $1,$ то либо все они больше $3,$ либо все меньше $3.$

Если все члены $A′$ меньше $3,$ то $A′$ состоит из чисел $1$ и $2,$ оканчиваясь числом $2.$ При этом любая такая последовательность, дополненная в конце тройкой, даст хорошую. Значит, такие последовательности $A′$ получаются ровно из $2n−1$ неотличных.

Пусть теперь все члены $A′$ больше $3;$ тогда она оканчивается на четвёрку. Вычтя из всех её членов по $3,$ мы получим либо хорошую последовательность, оканчивающуюся числом $1$ (если в полученной последовательности содержится $3$ ) — таких ровно $T; n$ либо последовательность из единиц и двоек, оканчивающуюся числом $1$ — таких ровно $2n−1.$ Итого, последовательностей последнего типа есть $n−1 Tn +2 .$

В итоге мы получаем, что $n−1 ( n−1) n n+1 n+1 Sn+1 =(3Sn− Tn)+2 + Tn+ 2 = 3Sn+ 2 = 3 − 2 .$ Переход доказан.

Ответ:

$3100 − 2100$

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

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

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

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

Дан прямоугольный треугольник $ABC$ с прямым углом $C.$ Пусть $BK$ — биссектриса этого треугольника. Окружность, описанная около треугольника $AKB,$ пересекает вторично сторону $BC$ в точке $L.$ Докажите, что $CB + CL= AB.$

Источники: Всеросс., 2015, РЭ, 9.6(см. olympiads.mccme.ru)

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

Решение 1.

$PIC$

Отложим на продолжении $BC$ за точку $C$ отрезок $CN =LC.$ Тогда $CB +CL = NB,$ и нам надо доказать, что $AB = NB.$

Так как четырёхугольник $ABLK$ вписан, имеем

∠CKB =180∘− ∠AKB = 180∘ − ∠ALB = ∠ALC

С другой стороны, прямоугольные треугольники $ACL$ и $ACN$ равны по двум катетам, так что $∠ANC = ∠ALC = ∠CKB = 90∘− ∠B∕2.$ Тогда из треугольника $ABN$ имеем

∘ ∘ ∘ ∘ ∠BAN = 180 − ∠B − ∠ANB = 180 − ∠B − (90 − ∠B∕2)=90 − ∠B∕2= ∠ANB

Из полученного равенства $∠ANB = ∠BAN$ и следует, что $AB = NB.$

______________________________________________________________________________________________________________________________________________________

Решение 2.

$PIC$

Опустим из точки $K$ перпендикуляр $KH$ на гипотенузу $AB.$ Прямоугольные треугольники $KCB$ и $KHB$ равны по гипотенузе и острому углу ( $∠KBC = ∠KBH ).$ Значит, $CB = HB$ и $KC =KH.$ Далее, в окружности, описанной около $AKLB,$ на хорды $AK$ и $KL$ опираются равные углы, поэтому $AK = KL.$ Значит, прямоугольные треугольники $KHA$ и $KCL$ равны по катету и гипотенузе, откуда $HA = CL.$ Итак, $CB + CL= HB + HA = AB,$ что и требовалось доказать.

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

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

Назовём натуральное число интересным, если сумма его цифр – простое число. Какое наибольшее количество интересных чисел может быть среди пяти подряд идущих натуральных чисел?

Источники: Всеросс., 2015, РЭ, 9.2(см. olympiads.mccme.ru)

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

Среди пяти подряд идущих натуральных чисел могут найтись $4$ интересных числа. Например, суммы цифр чисел $199,200,201,202,203$ равны $19,2,3,4$ и $5.$ Все пять чисел оказаться интересными не могут. Среди наших этих пяти чисел есть три, лежащих в одном десятке. Их суммы цифр – последовательные числа; значит, все они не могут одновременно быть простыми. Действительно, хотя бы одно из них четно, значит равняется 2. Тогда последовательность из трех сумм цифр это либо ${1,2,3},$ либо ${2,3,4},$ и ни одна из них не состоит из простых чисел.

Ответ:

$4$

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

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