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

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

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

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

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

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

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

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

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

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

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

В зоопарк прибыли несколько пар особей, у каждой из которых от 1 до 10 детёнышей. Ветеринар выбирал одного детёныша, одну самку и самца из трёх разных семей и проводил осмотр. У него было 3630 способов выбрать нужную тройку животных. Сколько всего детёнышей могло прибыть в зоопарк?

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

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

Пусть в зоопарк было $p$ пар особей и $d$ детёнышей. Тогда каждый детёныш состоял в $(p − 1)(p− 2)$ тройках: самку можно было выбрать из одной из $p − 1$ пар особей, а после её выбора самца можно было выбрать из одной $p− 2$ оставшихся пар. Значит, общее количество троек равно

d(p− 1)(p− 2)= 3630.

Поскольку $d≤ 10p,$ получаем $3630 ≤10p3,$ то есть $p3 ≥ 363> 73.$ Значит, $p ≥8.$

Число $3630= 2⋅3⋅5⋅112$ имеет два делителя $p− 1$ и $p− 2,$ отличающиеся на $1.$ Если один из этих делителей делится на $11,$ то другой даёт остаток $1$ или $10$ при делении на $11.$ Тогда он взаимно прост с $11,$ а значит, делит $2⋅3⋅5= 30$ и при этом не меньше $10.$ Нетрудно видеть, что этим делителем может быть только $10;$ тогда $p − 2 =10,p− 1 =11 и d= 3630 :110= 33.$

Если же оба числа $p− 2 и p− 1$ не делится на $11$ , то число $2⋅3⋅5= 30$ делится на их произведение, а это противоречит тому, что $p ≥8.$

Ответ: 33

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

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

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

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

По кругу расставлено $300$ положительных чисел. Могло ли случиться так, что каждое из этих чисел, кроме одного, равно разности своих соседей?

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

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

Подсказка 1

Давайте поймём, какое именно число не равно разности соседей. Очевидно, что наибольшее. Значит, все остальные равны разности соседей.

Подсказка 2

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

Подсказка 3

Верно, давайте попробуем доказать, что числа от наименьшего к наибольшему не убывают(а заодно вы получите ещё кое-какое соотношение). Какой самый простой для этого способ..? Конечно, индукция. Аналогичным образом получится результат для другой дуги. Попробуйте теперь воспользоваться полученными знаниями для получения противоречия.

Подсказка 4

У вас есть две последовательности чисел(пусть a_i и b_i) и рекуррентное соотношение на них. Попробуйте теперь доказать, что на самом деле a_i<b_i≤a_(i+1). Чем нам это поможет? А ведь мы ещё не пользовались всем условием. Что же не так с числом 300..?

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

Предположим, что требуемая расстановка существует. Ясно, что наибольшее из чисел не может равняться разности соседей; значит, каждое из остальных чисел равно разности соседей. В частности, наибольшее число встречается ровно один раз; обозначим его через $m.$

Пусть $d$ — одно из наименьших чисел в круге. Рассмотрим любую из двух дуг между $d$ и $m;$ пусть на ней стоят подряд числа $d =a0,a1,...,ak = m.$ Докажем индукцией по $i= 0,1,...,k− 1,$ что $ai+1 ≥ ai.$ В базовом случае $i= 0$ утверждение верно, ибо $d$ — наименьшее число. Для перехода от $i− 1$ к $i$ предположим, что $i< k$ и $ai−1 ≤ai.$ Тогда равенство $ai = ai− 1− ai+1$ невозможно, ибо $ai+1 > 0,$ и поэтому $ai = ai+1 − ai−1.$ Значит, $ai+1 > ai,$ что и доказывает переход индукции. Мы заодно показали, что $ai+1 = ai+ ai−1$ при всех $i= 1,...,k− 1.$

Аналогично, если на другой дуге между $d$ и $m$ стоят подряд числа $d= b0,b1,...,bℓ = m,$ то $b0 ≤ b1 ≤ ...≤bℓ$ и $bi+1 = bi+bi−1$ при всех $i= 1,2,...,ℓ− 1.$ Наконец, для числа $a0 = b0 = d$ условие задачи также должно выполняться, так что $d= |a1 − b1|.$ Без ограничения общности можно считать, что $d= b1− a1;$ тогда $a2 = a0 +a1 = b1 > a1.$

Продолжим теперь последовательности $a0,a1,...$ и $b0,b1,...$ согласно формулам $ai+1 = ai+ai−1$ и $bi+1 = bi+ bi−1.$ Докажем индукцией по $i= 1,2,...$ , что $ai <bi ≤ ai+1.$ При $i=1$ это уже доказано выше. При $i=2$ из соотношений $b0 = a0 ≤a1 <b1 = a2$ получаем

a2 = a1+a0 <b1+ b0 =b2 ≤ a2+ a1 =a3

Для перехода индукции предположим теперь, что $i≥ 3,$ и утверждение уже доказано для меньших значений $I.$ По предположению индукции, имеем

ai−2 < bi−2 ≤ ai−1 < bi−1 ≤ai

откуда

ai = ai− 1+ai−2 < bi−1+ bi−2 = bi ≤ai+ ai−1 =ai+1

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

Итак, мы получили, что

a0 =b0 ≤ a1 < b1 ≤a2 < b2 ≤ ...

Значит, равенство $bℓ = ak$ возможно лишь при $k= ℓ+1;$ но тогда общее количество чисел в круге равно $k+ ℓ= 2ℓ+1,$ что не может равняться $300.$ Противоречие.

Ответ:

Не могло

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

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

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

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

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

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

Все члены разностной последовательности равны 0, $± 1$ или $±2,$ так что количество всевозможных разностных последовательностей равно $n−1 5 .$

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

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

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

______________________________________________________________________________________________________________________________________________________

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

Сделаем переход от $n$ к $n+ 1.$ Рассмотрим произвольную $n$ -членную хорошую последовательность; пусть она оканчивается числом $k.$ Тогда к ней можно приписать любое число от $k− 2$ до $k+2;$ полученная последовательность будет хорошей, если приписываемое число натуральное. Если же оно неположительно (то есть равно 0 или $− 1),$ то после приписывания прибавим ко всем числам последовательности по 5. Полученная последовательность будет оканчиваться числом 4 или 5, а значит, будет хорошей.

Заметим, что все полученные последовательности — разные. Для последовательностей, полученных без прибавления 5, это очевидно; при этом таким образом получаются ровно все хорошие последовательности, среди первых $n$ членов которых есть 4 или 5. Последовательности же, полученные прибавлением 5, также попарно различны; при этом это — ровно все хорошие последовательности, первые $n$ членов которых больше 5, и при этом среди них встречается 9 или 10. В частности, эти последовательности отличны от описанных ранее. Итого, мы уже построили $5Sn$ хороших $(n+ 1)$ -членных последовательностей.

Осталось подсчитать число ещё неучтённых последовательностей. В каждой неучтённой последовательности среди первых $n$ членов нет чисел 4, 5, 9 и 10, а последний член равен 4 или 5. Значит, либо первые $n$ её членов — единицы, двойки и тройки, либо все они — шестёрки, семёрки или восьмёрки. Посчитаем количество первых; количество вторых считается аналогично.

Рассмотрим любую последовательность из $n$ единиц, двоек и троек (её соседние члены автоматически отличаются максимум на 2). Если она оканчивается числом 3, то к ней можно приписать 4 или 5, получив неучтённую последовательность. Если она оканчивается числом 2, то можно приписать лишь 4; если же её последнее число — 1, то хорошую последовательность из неё получить нельзя. Значит, количество полученных неучтённых последовательностей равно $n−1 n−1 n 2⋅3 +3 = 3$ (и ещё столько же получаются из последовательностей с числами 6, 7 и 8).

Итого, мы получаем

Sn+1 = 5Sn +2⋅3n =5(5n − 3n)+ 2⋅3n = 5n+1 − 3n+1,

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

Ответ:

$5100 − 3100$

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

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