Тема АЛГЕБРА

Последовательности и прогрессии → .06 Последовательности нестандартного вида

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

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

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

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

Подтемы раздела алгебра

Разделы подтемы Последовательности и прогрессии

Арифметическая прогрессия

Геометрическая прогрессия

Комбинация арифметической и геометрической прогрессий

Рекуррентные соотношения

Периодичность и зацикливание

Последовательности нестандартного вида

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

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

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

Последовательность чисел $a ,a ,... 1 2$ такова, что $a = 2,a = 5 1 2$ и

( 2) ( 2) an+2 = 2− n an+1 + 2+ n an

при всех $n ≥1.$ Существуют ли такие $p,q$ и $r,$ что $a a = a ? p q r$

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

Подсказка 1

Давайте доказывать, что такое невозможно. Как можно доказать, что a_p * a_q ≠ a_r? Попробуйте показать, что такое невозможно по какому-то модулю. Как его найти?

Подсказка 2

Вычислите первые несколько членов. Попробуйте найти модуль? по которому они все сравнимы. Как это можно доказать? Как это помогает доказать задачу?

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

Мы покажем, что для всех $n:a ≡ 2 (mod 3). n$ Это, очевидно, выполнено для $n= 1$ и $n= 2,$ а для всех остальных доказывается по индукции:

( 2) ( 2) ( 2) ( 2) an+2 = 2− n an+1+ 2+ n an ≡ 2 2− n + 2 2+n = 8≡ 2 (mod 3)

Пусть теперь $p,q,r$ – три натуральных числа. Произведение $a a ≡ 1 (mod 3), p q$ поэтому $aa p q$ не может равняться $a , r$ сравнимому с $2 (mod 3).$

Ответ:

Не существуют

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

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

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

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

Дана бесконечная последовательность натуральных чисел $a ,a,a ,.... 1 2 3$ Оказалось, что для любых натуральных $k$ и $ℓ$ число $a + a k ℓ$ делится на $k+ ℓ.$ Докажите, что для любых натуральных $k⁄= ℓ$ число $ak− aℓ$ делится на $k− ℓ.$

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

Выберем натуральное $t$ такое, что $t+ l$ делится на $k − l.$ Тогда $a +a l t$ делится на $l+t,t+l$ делится на $k− l,$ откуда $a +a l t$ делится на $k− l.$ Аналогично, $ak+ at$ делится на $l+ t$ , $t+ k= (t+l)+(k− l)$ делится на $k− l,$ откуда $ak+ at$ делится на $k− l.$ Следовательно, $ak− al = (ak+ at)− (al+ at)$ также делится на $k− l.$

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

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

Последовательность $a,a ,a,... 1 2 3$ получается из последовательности натуральных чисел вычёркиванием всех полных квадратов (то есть $a1 = 2$ , $a2 = 3$ , $a3 =5$ , $a4 = 6$ , $a5 = 7$ , $a6 = 8$ , $a7 = 10$ и т.д.). Найдите $a2023$ .

Источники: ДВИ - 2023, вариант 233, задача 2 (pk.math.msu.ru)

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

Подсказка 1

Давайте рассмотрим число n, которое находится между двумя полными квадратами – m² и (m+1)². Подумайте, какой у него будет порядковый номер в последовательности?

Подсказка 2

Если бы это была последовательность натуральных чисел, то номер был бы равен n, но мы вычеркнули уже m чисел, так что порядковый номер равен n - m! Тогда нам просто нужно подобрать такие m и n, чтобы выполнялось 2023 = n - m и m² < n < (m+1)²

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

Для каждых натуральных чисел $n, m$ таких что

2 2 m < n< (m +1)

справедливо $n =an−m$ . Стало быть, для каждого $n,$ удовлетворяющего условию

2 2 45 = 2025< n< 2116= 46

справедливо $n =an−45.$ Поскольку $n − 45= 2023$ при $n =2068,$ получаем $a2023 = 2068.$

Ответ: 2068

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

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

Последовательность $a n$ задана формулами

4043- 3 2 a1 = 2022,an+1 = an− 3an +3an.

Найдется ли натуральное число $n$ такое, что

2022 |an|≤ 2021?

Обоснуйте свой ответ.

Источники: ПВГ-2022, 11.4 (см. pvg.mk.ru)

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

Подсказка 1

Сразу заметим кое-что в формуле последовательности: да это же выглядит как полный куб! Только единички не хватает) Как тогда будет выглядеть наша последовательность?

Подсказка 2

Раз там не хватало единицы, прибавим ее к обеим частям. Тогда, например, раз a_n = 1 + 2021/2022, то a2+1 = 1 + (2021/2022)^3. Можете ли вы тогда вывести формулу для последовательности?

Подсказка 3

Конечно можете! Это будет a_n = 1 + (2021/2022)^(3^n)! Т.е. у нас какое-то число, меньшее единицы по модулю, возводится в все большую и большую степень....Что это значит?

Подсказка 4

Это значит, что оно уменьшается все время) Теперь просто попробуйте подобрать n, чтобы выполнялось условие!

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

Перепишем данную в условии формулу в виде

3 an+1 = (an− 1) +1

Находим, что если $an = 1+ 𝜀$ , то $an+1 =1 +𝜀3.$ В предложенной задаче $a1 = 1+ 2021, 2022$ поэтому

( 2021)3 (2021)3n−1 a2 =1 + 2022- ,...,an = 1+ 2022

Так как

a ≤ 2022⇔ 1+ (2021)3n−1 ≤ 1+-1--⇔ (2021)3n−1 ≤--1- n 2021 2022 2021 2022 2021

Это неравенство при достаточно больших $n$ выполняется. Для того, чтобы это утверждать, нужно или доказать, что предел этой последовательности равен 0 , или сделать оценку

( 1 ) ( 1 ) 3n−1 ≥ log22002122 2021- ⇔ n≥ 1+ log3 log202022122021-

Отсюда следует, что для любого

[ ( )] n ≥ 1+ log3 log 2022-2021 + 1 2021

неравенство выполняется.

Ответ: да

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

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

Назовём бесконечную числовую последовательность ${a } n$ стабилизирующейся, если при некотором $k 0$ для всех $k ≥k 0$ выполнено $ak = ak+1.$ Тогда $k0$ назовем временем стабилизации, $ak$ $($ при $k≥ k0)$ — стабильным значением.

Пусть $a,b$ — натуральные числа. Дана последовательность ${xn},$ в которой $x1 = x2 = x3 = a$ и для любого натурального $n$ выполнены равенства

x3n+1 = b⋅x3n−2,x3n+2 = x3n−1∘b

$($ здесь $∘b$ — это операция взятия целой части при делении на $b)$ и

x3n+3 =x3n+ x3n−2 ⋅(x3n− 1(modb))

$($ здесь $(modb)$ — операция взятия остатка от деления на $b).$

Какие из последовательностей ${x3n+1},{x3n+2},{x3n}(n∈ ℕ)$ стабилизируются, и чему равны их стабильные значения? Чему равно время стабилизации последовательности ${x3n}?$

Источники: Иннополис-2022 (см. dovuz.innopolis.university)

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

Подсказка 1

Давайте посмотрим, что нам известно из условия? Получается, основная последовательность {Xn} разделяется на три подпоследовательности. Причём первые две, похоже, зависят только от тех элементов основной последовательности, что входят в эту подпоследовательность. Может, для начала рассмотрим их повнимательнее?

Подсказка 2

Верно, мы можем выразить элементы этой последовательности через a, b и n. Третья же подпоследовательность зависит от элементов из других подпоследовательностей, так что здесь так просто не получится расписать. Тогда стоит попробовать выразить x{3n+3} с помощью x{3n+1} и x{3n+2}. Например, записать какое-нибудь равенство с этими тремя переменными.

Подсказка 3

Для составления такого уравнения очень полезно начать с расписывания первых элементов и постепенно находить отношения, которые остаются неизменными. А затем доказать их по индукции

Подсказка 4

Остаётся только проанализировать, при каких значениях b каждая из подпоследовательностей стабилизируется и на каком стабильном значении

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

Сначала рассмотрим последовательность ${x }. 3n+1$ По ее определению имеем $x = a⋅bn 3n+1$ для всех целых $n ≥0$ — значит, при $b= 1$ ее стабильное значение равно $a,$ а при $b >1$ она не стабилизируется.

Теперь рассмотрим ${x3n+2}.$ По определению, если $b= 1,$ то $x3n+2 =a$ для всех целых $n≥ 0,$ а если $b> 1,$ то $-a x3n+2 ≤ bn$ и, поскольку последовательность — целочисленная, имеем $x3n+2 =0$ для всех $n,$ начиная с $⌈logba⌉$ (целая часть от логарифма, взятая с избытком).

Докажем по индукции, что

x3n+1⋅x3n+2+ x3n+3 =a2+ a

для всех целых $n ≥ 0.$

База индукции $(n= 0):$

2 x1⋅x2+ x3 =a + a

по определению.

Индукционная гипотеза: пусть для некоторого $m ≥0$ выполнено

2 x3m+1 ⋅x3m+2+ x3m+3 = a + a

Тогда

x ⋅x +x = (b⋅x3m+1)⋅(x3m+2 ∘b)+ 3(m+1)+1 3(m+1)+2 3(m+1)+3

+(x3m+3+ x3m+1 (x3m+2(modb)))= ((b⋅x3m+1)⋅(x3m+2 ∘b)+

2 x3m+1 (x3m+2(modb)))+ x3m+3 =x3m+1 ⋅x3m+2+ x3m+3 = a + a

Что и требовалось доказать.

Наконец, рассмотрим последовательность ${x3n}$ . В силу доказанного выше, если $b=1$ , то все члены последовательности ${x3n}$ равны $a$ , а если $b> 1$ , то

x = x ⋅0+ x =x ⋅x +x = a2+a, 3n+3 3n+1 3n+3 3n+1 3n+2 3n+3

начиная с $n = ⌈logba⌉,$ следовательно, стабильное значение последовательности ${x3n}$ равно $a2+a.$

Ответ:

Последовательность ${x } 3n+1$ стабилизируется на $a$ при $b =1;$ ${x } 3n+2$ стабилизируется на $a$ при $b= 1$ и на $0$ при $b> 1;$ ${x } 3n$ стабилизируется на $a$ при $b= 1,$ начиная с $n= 1,$ и на $2 a + a$ при $b> 1,$ начиная с $n = ⌈logba⌉.$

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

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

В последовательности ${x } n$ каждый член, начиная со второго, получается сложением его номера с суммой всех предыдущих членов. Найдите сумму первых ста членов этой последовательности, если $x1 = 1$ .

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

Пусть $s i$ — сумма первых $i$ элементов. Тогда

xi+1 = i+1 +si

si+1 =i+ 1+ 2si

Отсюда

(s − 2s )− (s − 2s )= s − 3s +2s =1 i+1 i i i−1 i+1 i i−1

si+1− 4si+ 5si−1− 2si−2 = 0

Значит, нам нужно решить уравнение

x3− 4x2+ 5x− 2= (x− 2)(x2 − 2x+ 1)= (x− 2)(x− 1)2 =0

Тогда $si = a2i+b+ cn$ . Посчитаем первые члены $s1 = 1,s2 = 4,s3 =11$ .

Тогда $2a +b+ c= 1,4a+ b+2c= 4,8a+ b+3c= 11$ . Отсюда $a= 2,b=− 2,c= −1,$ и значит,

s100 = 2⋅2100− 2− 100

Ответ:

$2⋅2100 − 2− 100$

Курсы

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

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

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

Последовательность ${a } n$ положительных чисел такова, что каждый ее член начиная со второго равен полусумме среднего арифметического и среднего геометрического двух соседних с ним членов. Найдите $a2017$ , если $a1 = 4$ , $a64 =9$ .

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

ai−1+ai+1-+√a---a--- ai =---2----2---i−1-i+1-=

√------- (√ ---- √----) = ai−1+-ai+1+-2-ai−1ai+1= --ai−1+--ai+1 2 4 2

Тогда если рассмотреть $b =√a-- i i$ , то

bi−1-+bi+1- bi = 2

Значит, $b$ — это арифметическая последовательность с началом $b1 = 2$ и шагом $b64−b1 -1 d= 63 = 63$ . Значит,

( )2 a2017 = b22017 = 2+ 206163 = 1156

Ответ:

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

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

Дана последовательность натуральных чисел ${a}, n$ определенная рекуррентно: $a = a + 2τ(n), n+1 n$ где $τ(n)$ — количество натуральных делителей числа $n$ ( $1$ и $n$ в том числе). Могут ли два подряд идущих члена последовательности быть точными квадратами?

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

Последовательность возрастает и $a ≥1. 1$ По индукции нетрудно понять, что $a ≥ n. n$ Пусть $a n$ и $a n+1$ — квадраты, тогда $a = m2 n$ и $2 2 an+1 ≥ (m+ 1),m ≥n.$ Отсюда следует, что $2 2 √ - 2τ(n)= an+1− an ≥ (m + 1) − m =2m +1 ≥4 n+ 1.$ Как известно, $√- 2τ(n)≤4 n,$ откуда $√- √- 4 n+ 1≤ 4 n,$ пришли к противоречию.

Ответ:

Нет

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

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

Последовательность натуральных чисел $a,a ,...,a ,... 1 2 n$ такова, что для каждого $n$ уравнение $a x2+a x+ a = 0 n+2 n+1 n$ имеет действительный корень. Может ли число членов этой последовательности быть бесконечным?

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

Все члены последовательности натуральные, а значит уравнение из условия квадратное. Следовательно, $a2 ≥ 4a a n+1 n n+2$ для всех $n ∈ℕ∕$ Теперь будем последовательно применять это неравенство:

a2 an ≤ 4na−n1−2

a2 ( a4a2n−2)2 a3 4na−1-≤ -4na−3--= 43n−a2-2- n−2 n−2 n−3

3 ( a2n−3)3 4 -a3n−22-≤ -4an3−24--= -a6n−33- 4 an−3 4an−3 4 an−4

и так дальше.

Понятно, что в правой части последнего неравенства мы получим выражение $-ax2- 4yaz1$ для некоторых $x,y,z,$ которые мы сейчас найдём.

В правой части первого неравенства мы имеем $a2n−1 4an−2.$ Если в правой части $i$ - го неравенства будет $ai+n−1i 2i(i+1)ain−i−1,$ то в правой части $i+ 1$ - го обязательно будет $----ai+n2−(i+1)----- 2(i+1)(i+2)ain+−1(i+1)−1$ (поподробнее про степень двойки написано чуть ниже). Это правда потому, что правую часть $i+1$ - го неравенства мы получаем, применяя неравенство $an−i ≤ a42na−i−1 n−i−2$ к правой части $i$ - го неравенства. Следовательно, в конце при $i= n− 2$ мы получим следующую правую часть: $---an2−1----- 2(n−2)(n−1)an1−2.$

Теперь про то, как угадать степень двойки в знаменателе. Если в знаменателе правой части $i$ -го неравенства четвёрка будет в степени $bi,$ то в правой части $i+ 1$ - го — в степени $bi+1 =bi+ i+1.$ Теперь нетрудно установить, что $bi = i(i+21),$ учитывая, что $b1 = 1.$

Следовательно, $n−1 an ≤ 2(n−2)a2(n−1)an−2- 1$ при $n ≥3.$

Покажем, что рано или поздно функция $2(n−1)(n−2)$ перерастёт функцию $an2−1.$ Понятно, что $2(n−1)(n− 2) = (2n−2)n−1.$ Рано или поздно $n− 2 2$ станет больше, чем $a2,$ именно в этот момент перерастёт. Таким образом, рано или поздно величина $an2−1 2(n−2)(n−1)an1−2-$ станет меньше $1,$ а тогда и $an < 1,$ то есть последовательность не позже этого момента закончится.

Ответ:

Нет

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

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

Можно ли расположить на прямой систему отрезков длины $1,$ не имеющих общих концов и общих точек так, чтобы любая бесконечная арифметическая прогрессия с любой разностью и любым начальным членом имела общую точку с некоторым отрезком системы?

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

Возьмём на положительной полуоси отрезки $[1,2],[21,31],[33,43],..., 2 2 4 4$ промежутки между которыми имеют длину $1,1,1,... 2 4 8$ На отрицательной полуоси возьмём симметричные им отрезки. Докажем, что эта система обладает требуемым свойством. Рассмотрим арифметическую прогрессию $an$ с положительной разностью $d.$ Пусть $N$ — некоторое положительное число. Выберем $n$ так, что $an >N.$ Между $an$ и $an+1$ расположены выбранные нами отрезки с общей длиной $x$ и промежутки с общей длиной $y$ (возможно, $x =0$ или $y = 0$ ). Ясно, что число $x$ целое. Нас интересует случай, когда $an$ и $an+1$ попадают в промежутки между выбранными отрезками. В таком случае $y > 0.$ Пусть $d1$ — наибольшее целое число, строго меньшее $d,$ а $d2 = d− d1.$ Ясно, что $0< d2 ≤1.$ Если $N$ достаточно велико, то общая длина промежутков между выбранными отрезками, лежащих правее $N,$ меньше $d2.$ В таком случае $y <d2.$ Ясно также, что $x ≤d1.$ Поэтому $d= x+ y < d1+d2 = d.$ Полученное противоречие показывает, что $an$ или $an+1$ попадает в выбранный отрезок. Если $d< 0,$ то аналогичные рассуждения можно применить к отрезкам на отрицательной полуоси.

Ответ:

Да

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

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

Существует ли бесконечная последовательность натуральных чисел $a,a ,a ,... 1 2 3$ такая, что числа $a m$ и $a n$ взаимно просты тогда и только тогда, когда $|m − n|= 1?$

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

Идея решения состоит в том, чтобы рассмотреть последовательность различных простых чисел $p ,p,p ,...; 1 2 3$ покрыть множество натуральных чисел последовательностью конечных непустых множеств $In$ таких, что $Im$ и $In$ не пересекаются тогда и только тогда, когда $m$ и $n$ различаются на $1;$ положить $∏ an = i∈In pi, n ∈ℕ.$ Задать такие множества можно, например, следующим образом. Для всех натуральных $n$ положим

2n ∈Ik для всех k= n,n+ 3,n +5,n+ 7,...; и 2n − 1 ∈Ik для всех k= n,n+ 2,n +4,n+ 6,...

Ясно, что каждое $Ik$ конечно поскольку оно не содержит чисел, превосходящих $2k.$ Далее, наличие числа $p2n$ гарантирует, что $In$ имеет общий элемент с каждым из $In+2i+1,$ а наличие $p2n−1$ гарантирует, что $In$ имеет общий элемент с каждым из $In+2i$ для всех $i∈ ℕ.$ Наконец, можно убедиться в том, что множества $In$ и $In+1$ не пересекаются (рассмотрев, например, остатки по модулю 4 чисел из множеств $In$ и $In+1$ ), а значит $an$ и $an+1$ действительно взаимно просты.

Ответ:

Существует

Интенсивы

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

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

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

Дана бесконечная последовательность чисел $a ,a ,..., 1 2$ в которой нет двух равных членов. Отрезок $a,a ,...,a i i+1 i+m−1$ этой последовательности назовем монотонным отрезком длины $m,$ если выполнены неравенства $ai < ai+1 < ...< ai+m −1$ или неравенства $ai > ai+1 >...>ai+m−1.$ Оказалось, что для каждого натурального $k$ член $ak$ содержится в некотором монотонном отрезке длины $k+ 1.$ Докажите, что существует натуральное $N$ такое, что последовательность $aN ,aN+1,...$ монотонна, т. е. $aN < aN+1 < ...$ или $aN > aN+1 > ....$

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

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

Подсказка 1:

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

Подсказка 2:

Это ашки с "плохими" индексами, которые либо меньше обоих соседей, либо больше. Действительно, если их количество конечное, то тогда нужная последовательность есть. Значит, нужно предположить, что их бесконечно много, и найти противоречие. Как можно это сделать?

Подсказка 3:

Попробуйте выбрать некоторый плохой индекс k и взять произвольное n>k. Тогда рассмотрите монотонный отрезок длины n +1, содержащий a_n. Попробуйте раскрутить дальше до конца решения.

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

Первое решение. Будем называть индекс $k ≥2$ плохим, если $a < a > a k−1 k k+1$ или $a > a <a . k− 1 k k+1$ Заметим, что если среди индексов $N + 1,N + 2,...$ нет плохих, то последовательность $aN ,aN+1,aN+2,...$ монотонна.

Предположим, что утверждение задачи неверно. Тогда найдётся бесконечно много плохих индексов. Выберем некоторый плохой индекс $k.$ Возьмём произвольное $n> k$ и рассмотрим монотонный отрезок $I$ длины $n +1,$ содержащий $an.$ Он не может содержать членов $ak−1,ak$ и $ak+1$ одновременно; следовательно, поскольку $k+ 1≤ n,$ отрезок $I$ точно не содержит $ak−1,$ а следовательно, не содержит и $a1.$

Итак, монотонный отрезок $I$ длины $n+ 1$ содержит $an,$ но не содержит $a1;$ тогда он обязан содержать $an,an+1$ и $an+2,$ так что индекс $n+ 1$ не является плохим. Итак, при любом $n >k$ индекс $n +1$ не плохой, поэтому плохих индексов конечное количество. Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим противное. Не умаляя общности, можно считать, что $a1 <a2$ (иначе можно умножить все члены последовательности на $− 1$ ). Поскольку последовательность $a2,a3,...$ не является возрастающей, существует такое $k ≥2,$ что $ak > ak+1.$ Поскольку последовательность $ak+1,ak+2...$ не является убывающей, существует такое $ℓ> k,$ что $aℓ < aℓ+1.$ Выберем наименьшее $ℓ,$ удовлетворяющее этим двум неравенствам. Тогда либо $ℓ> k+ 1,$ и тогда $aℓ−1 > aℓ$ согласно выбору $ℓ,$ либо $ℓ =k +1,$ и тогда $aℓ−1 =ak >ak+1 = aℓ.$ Итак, в любом случае $aℓ−1 > aℓ.$

Рассмотрим монотонный отрезок длины $ℓ,$ содержащий $aℓ−1;$ он обязан содержать и $aℓ.$ Поскольку $aℓ−1 > aℓ,$ числа этого отрезка монотонно убывают. Значит, он не может содержать числа $a1$ (иначе бы он содержал и $a2 > a1$ ). Но тогда, раз длина отрезка равна $ℓ,$ он обязан содержать и $aℓ+1 >aℓ,$ что невозможно.

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

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

Дано натуральное число $n >5.$ На кольцевой полоске бумаги написана последовательность из нулей и единиц. Для каждой последовательности $w$ из $n$ нулей и единиц посчитали количество способов вырезать из полоски фрагмент, на котором написана $w.$ Оказалось, что наибольшее количество $M$ достигается на последовательности $110◟0n.◝−..◜20 ◞,$ а наименьшее (возможно, нулевое) — на последовательности $0◟0..◝◜.0◞11. n−2$ Докажите, что есть и другая последовательность из $n$ нулей и единиц, встречающаяся ровно $M$ раз.

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

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

Подсказка 1

Обозначим через N количество способов вырезать из полоски последовательность 10...01, где нулей хотя бы n - 2. Перед каждой из них может стоять или 1, или 0. Обозначим количество тех, перед которыми стоят 1, через N_1x, перед которыми стоят 0 — через N_0x. После каждой из N последовательностей может стоять или 0, или 1; аналогично предыдущему предложению введём количества N_x0 и N_x1. Какие равенства на эти количества можно написать?

Подсказка 2

Верно, N_0x + N_1x = N = N_x0 + N_x1! Теперь стоит попробовать представить N_1x, как количество способов вырезать некоторую последовательность из условия.

Подсказка 3

Заметим, что N_1x — это количество способов вырезать последовательность 110..0, где нулей ровно n - 2, а значит, N_1x = M(поймите, почему). Аналогично можно представить остальные N-ки. Потом стоит воспользоваться равенством из подсказки 2.

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

Обозначим через $N$ количество способов вырезать из полоски последовательность $100...01 ◟≥◝n◜− ◞2$ (т.е. количество последовательностей из хотя бы $n− 2$ нулей, перед и после которых стоят единицы). Перед каждой из них может стоять или $1,$ или $0;$ обозначим количество тех, перед которыми стоят $1,$ через $N1x,$ перед которыми стоят $0$ — через $N0x.$ После каждой из $N$ последовательностей может стоять или $0,$ или $1;$ аналогично предыдущему предложению введём количества $Nx0$ и $Nx1.$ Tогда

N + N = N =N +N ∗ 0x 1x x0 x1

Заметим, что $N1x$ — это количество способов вырезать последовательность $110◟0.◝..◜0 ◞1. ≥n−2$ Каждый такой способ соответствует способу вырезать последовательность $11 00◟. ◝.◜.0◞; n−2$ и наоборот, каждый способ вырезать последовательность $110◟0.◝.◜.0◞ n− 2$ можно единственным образом дополнить до способа вырезать последовательность $1100...01. ◟≥◝n◜−◞2$ Значит, количества таких способов одинаковые, и $N1x = M.$ Аналогично $N0x,Nx0$ и $Nx1$ равняются количествам способов вырезать последовательности $010◟0..◝◜.0◞,0◟0.◝.◜.0◞10 n−2 n− 2$ и $0◟0.◝.◜.0◞11 n− 2$ соответственно. По условию, последовательность $00...011 ◟n◝◜−2◞$ встречается наименьшее число раз, откуда $N ≥ N . 0x x1$ Тогда, с учётом $(∗),$ получаем $Nx0 ≥N1x =M,$ что возможно только при $Nx0 = M.$ Значит, последовательность $0◟0.◝..◜0 ◞10 n−2$ также встречается ровно $M$ раз.

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

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

Возрастающая последовательность натуральных чисел $a < a <... 1 2$ такова, что при каждом целом $n> 100$ число $a n$ равно наименьшему натуральному числу, большему чем $an−1$ и не делящемуся ни на одно из чисел $a1,a2,...,an−1$ . Докажите, что в такой последовательности лишь конечное количество составных чисел.

Источники: Тургор - 2021, 11.4, устный тур (см. turgor.ru)

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

Подсказка 1

Нам нужно доказать, что начиная с какого-то m все числа нашей последовательности станут простыми. Допустим, что для какого-то n > m выполняется aₙ = d*t, где t ≤ d. Из условия мы понимаем, что d у нас не является числом вида aₖ, где k < m. Тогда как мы можем оценить d?

Подсказка 2

Точно! Мы можем тогда сказать, что aₖ < d < aₖ₊₁ для k < m. Тогда если мы возьмём достаточно большое m (например, 100), то мы также знаем, что d > a₁₀₀. Что теперь можно сказать про делители числа d, если мы знаем, что d не является членом нашей последовательности?

Подсказка 3

Верно! Мы получаем, что d делится на какое-то aₚ, где p ≤ k. Тогда какое противоречие мы получаем для aₙ?

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

Докажем, что все $a m$ , большие $(a )2 100$ , — простые числа. Предположим противное, тогда некоторое $a >(a )2 m 100$ раскладывается как $am = dt$ , где $1< t≤ d< am$ , и следовательно $a100 < d< am$ . Согласно определению $am,d$ не является ни одним из $a1,a2,...,am−1$ . Тогда $ak < d< ak+1$ для какого-то $k∈ {100,101,...,m− 1}$ . Раз $d$ не было выбрано в качестве $ak+1$ , оно делится на какое-то $ai,i∈ {1,2,...,k}$ . Но тогда и $am$ делится на $ai$ . Противоречие.

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

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

Последовательность $(a ) n$ задана условиями

a1 = 1, a2 = 2 и an+2 = an(an+1 +1) при n ≥1.

Докажите, что $aa n$ делится на $(an)n$ при $n ≥100.$

Источники: СпбОШ - 2020, задача 11.6(см. www.pdmi.ras.ru)

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

Подсказка 1

Будем исследовать степень вхождения простого p в элементы последовательности. Пусть k - первый номер, для которого a_k делится на p. Тогда что можно сказать про k+2-й член последовательности?

Подсказка 2

Степень вхождения p в него хотя бы на 1 больше, чем в a_k. Аналогично можно получить, что степень вхождения в (k+2n)-ый член последовательности, больше хотя бы на n. Нам нужно проверить, что для всех p a_m-ый член последовательности имеет степень вхождения p хотя бы в m раз больше, чем m-ый.

Подсказка 3

Заметим, что m и a_m одной чётности, тогда мы хотим понять, что (a_m - m) это достаточно много, чтобы степень вхождения p точно получилась большой.

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

Пусть простое число $p$ входит в $a n$ в $k$ -й степени. Докажем, что $a an$ делится на $pkn.$ Тогда утверждение задачи будет выполнено.

Пусть $ai$ — первое число в нашей последовательности, кратное $p.$ Если $p⁄= 2,$ то $i> 2$ и $ai = ai−2(ai−1+ 1).$ Следовательно,

ai−1 ≡ −1 (modp)

Заметим, что для $p= 2$ будет $i= 2,$ и выведенное сравнение тоже выполнено.

Итак, $ai−1 ≡ −1,ai ≡ 0,$ а тогда дальше в последовательности чередуются остатки $− 1$ и $0$ от деления на $p:$

a = a (a + 1)≡ −1 ⋅(0+ 1)=− 1 (modp) i+1 i−1 i ai+2 = ai(ai+1+ 1)≡ 0⋅(−1+ 1)=0 (modp) и т.д.

Более того, как видно из последнего вычисления, степени числа $p,$ на которые делятся члены последователыности, растут: если $ai$ делилось на $p,$ то $ai+2$ делится на $2 p$ и т. д. Отсюда следует, что если $an$ делится на $k p,$ то $an+2t$ делится на $k+t p .$ Кроме того, учтем, что числа $an$ и $n$ одинаковой четности, поскольку $a1 =1,$ $a2 = 2$ и остатки по модулю $2$ чередуются. Следовательно, $aan$ делится на $k+(a −n)∕2 p n .$ Остается заметить, что $n an > 2$ при $n≥ 5$ (это значит, что $an$ существенно крупнее $n$ ) и $k an ≥2 ,$ так как делится на $k p$ (это значит, что $an$ существенно крупнее $k$ ), поэтому $an− n >2kn$ , откуда следует требуемое.

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

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

Докажите, что существуют такие последовательности натуральных чисел $a n$ и $b , n$ что одновременно выполнены следующие условия:

- последовательности $an$ и $bn$ являются неубывающими;

- последовательности $-1 -1 -1 An =a1 +a2 +...+ an$ и $1- 1- -1 Bn = b1 + b2 +...+ bn$ неограниченно возрастают;

- последовательность $---1--- ---1--- ---1---- Cn = max(a1,b1) + max(a2,b2) + ...+ max(an,bn)$ ограничена.

Источники: Курчатов - 2020, 11.6 (см. olimpiadakurchatov.ru)

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

Подсказка 1

Попробуем строить последовательности а и b вокруг последовательности С. Пусть каждый k-тый член в ней равен 2 в степени (-k) — такая последовательность, конечно, ограничена. Как теперь собрать такие последовательности а и b, чтобы max(aₙ, bₙ)=cₙ?

Подсказка 2

Вспомним про раскраски! Разобьём натуральный ряд на цветные отрезки, и для каждого цвета одно число (аₙ или bₙ) равно 2^n, а второе число должно быть меньше него. Как бы это реализовать?

Подсказка 3

Для каждого числа "не на своём цвете" будем брать 2 и возводить в самое маленькое число на этом отрезке! То есть, если красный отрезок начинается с числа k, то (не умаляя общности) аₙ равен 2^n, а bₙ равен 2^k (для синих отрезков аналогично с точностью наоборот). Тогда мы действительно можем составить нашу последовательность c, а так же обе последовательности а и b будут неубывающими. Но как сделать так, чтобы и последовательности А и В были неограниченно возрастающими? Хорошо бы было, если бы на каждом красном отрезке сумма обратных значений b не была слишком маленькой...

Подсказка 4

Конечно! Пусть длина каждого отрезка, начинающегося на k, равна 2^k! Тогда сумма обратных на каждом отрезке равна единице, и последовательности будут не ограничены сверху!

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

Рассмотрим последовательность $c = 2k k$ . Ясно, что все суммы

1 1 1 Cn = c1 + c2 + ...+ cn

ограничены. Будем строить исходные последовательности $an$ и $bn$ так, чтобы $max(an,bn)=cn$ . Последовательно разобьём натуральный ряд на отрезки подряд идущих чисел так, что если отрезок начинается с числа $k$ , то его длина равна $ck$ . После этого раскрасим все эти отрезки поочередно в красный и синий цвета.

Теперь зададим последовательность $an$ следующим образом:

- если $n$ - красное число, то положим $an$ равным числу $cn$ ;

- если $n$ - синее число, то положим $an$ равным $ck$ , где $k$ - первое число отрезка, содержащего $n$ .

Последовательность $bn$ зададим аналогично, но инвертируя цвета:

- если $n$ - синее число, то положим $bn$ равным числу $cn$ ;

- если $n$ - красное число, то положим $bn$ равным $ck$ , где $k$ - первое число отрезка, содержащего $n$ .

Заметим, что для каждого синего отрезка сумма обратных значений последовательности $an$ на нём равна $1,$ поэтому последовательность сумм $1a1 + 1a2 + ...+ 1an$ не ограничена сверху. Аналогично, для последовательности $bn$ сумма обратных значений на каждом красном отрезке равна $1,$ поэтому последовательность сумм $b1+ 1b-+ ...+ 1bn- 1 2$ не ограничена сверху.

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

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

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

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

Для бесконечной последовательности $a,a ,... 1 2$ её первая производная — это последовательность $a′= a − a n n+1 n$ (где $n= 1,2,...),$ а её $k$ -я производная — это первая производная её $(k− 1)$ -й производной $(k =2,3,...).$ Назовём последовательность хорошей, если она и все её производные состоят из положительных чисел. Докажите, что если $a1,a2,...$ и $b1,b2,...$ — хорошие последовательности, то и $a1⋅b1,a2⋅b2,...$ — хорошая последовательность.

Источники: Тургор - 2020, 11.4, устный тур (см. turgor.ru)

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

Подсказка 1

Давайте попробуем доказать некоторые простые свойства производной последовательности. Например, производная суммы равна сумме производных.

Подсказка 2

Теперь попробуйте показать, что вторая производная последовательности aₙbₙ состоит только из положительных чисел. Не забывайте использовать, что последовательности a и b — хорошие.

Подсказка 3

Попробуйте расширить рассуждения из предыдущей подсказки. Пусть есть некоторые хорошие последовательности a_m и b_k. Что можно сказать про вторую производную последовательности a_m • b_k?

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

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

Утверждение 1. Покажем, что при таком определении производной для последовательности выполняется: производная суммы — это сумма производных.

Пусть дана последовательность, являющаяся суммой нескольких других последовательностей:

(1) (2) (t) kn =kn + kn + ...+ kn ,

где $k(1),...,k(t)$ — какие-то $t$ произвольных последовательностей. Тогда производная этой суммы:

$pict$

В силу произвольности $t,$ наше утверждение доказано.

Утверждение 2. Пусть $a1,a2,...$ и $b1,b2,...$ — две произвольные хорошие последовательности. Тогда покажем, что производная произведения двух произвольных членов этих последовательностей положительна. То есть для всех $m,k∈ {1,2,...}$ выполнено:

(am ⋅bk)′ > 0

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

Запишем по определению производной:

$pict$

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

Теперь вернёмся к решению задачи. Пусть $cn = an⋅bn.$ Тогда по утверждению 2 для любого $n:$

(cn)′ = (an⋅bn)′> 0

Значит, первая производная $cn$ (и, соответственно, произведения любых двух хороших последовательностей) состоит из положительных чисел.

Кроме того, мы представили $c′n$ в виде суммы двух произведений хороших последовательностей. Далее по индукции, используя утверждения 1 и 2, получаем, что и все производные $cn$ состоят из положительных чисел.

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

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

Для зашифрования осмысленного слова его буквы переводят в числа $x ,x ,...,x 1 2 n$ по таблице. Затем выбирают натуральные числа $x 0$ и $k.$ Далее число $x0$ приписывают в начало последовательности $x1,x2,...,xn,$ а число $n+4 xn+1 =x0+ 19$ (где $n−$ длина слова) — в ее конец. Получившаяся в результате последовательность $x0,x1,...,xn,xn+1$ затем преобразуется в последовательность $y0,y1,...,yn,yn+1$ по формуле $( 3 ) yi = r32 xi+ 6xi⋅k + k ,i= 0,1,...,n+ 1,$ где $r32(a)−$ остаток от деления числа $a$ на $32.$ Затем числа $y0,y1,...,yn+1$ заменяют буквами согласно таблице. В результате получили вот что: КЙЫЦНБНЦЛ. Какое слово было зашифровано?


А	Б	В	Г	Д	Е Ё	Ж	3	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Ш	Ъ	Ы	Ь	Э	Ю	Я

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31

Источники: Верченко - 2020, 11.2

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Попробуйте рассмотреть остаток от деления от разности последней и первой букв. Может, так получится оценить k?

Подсказка 4

Опробуйте значение k, используйте правило шифрования в обратную сторону и посмотрите, получилось ли осмысленное слово. Если нет, то может стоит попробовать другое значение k?

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

В слове КЙЫЦНБНЦЛ $9$ букв, значит $n= 9− 2= 7.$ Найдеём остаток

11 25 5 33 3 r32(19 )= r32((19 )⋅19)= r32(9⋅19)= r32((3 ) ⋅57)= r32((− 5) ⋅(−7))= r32(3⋅25)=11

Преобразуем зашифрованный текст в последовательность чисел:

y0 = 10, y1 =9, y2 = 27, y3 = 22, y4 = 13, y5 = 1, y6 =13, y7 = 22, y8 = 11

Из условия следует, что $x8− x0 = 11.$ Рассмотрим разность

r32(y8− y0)=r32(x8+ 6x8⋅k3 +k − x0− 6x0⋅k3 − k)=

= r32((1 +6k3)⋅(x8− x0))= r32(11⋅(1+ 6k3))

Имеем:

r32(11⋅(1+ 6k3))= 1

Заметим, что $r32(3⋅11)= 1.$ Откуда находим $r32(1+ 6k3)= 3.$ Значит,

1+ 6k3 = 3+32t

3 3k =1+ 16t

3 33k = 11+ 11⋅16t

Значит, $r16(33k3)= r16(k3)= 11.$ В итоге

3 k =11+ 16p

При $p= 1$ получим $k3 =27.$ Отсюда $k =3.$ Опробуем полученное значение.

Согласно правилу зашифрования

y = 9= r (x + 6x ⋅27+ 3)= r (x ⋅3+ 3) 1 32 1 1 32 1

3x1+ 3= 9+32t

3x1 =6+ 32t

Т.е. $r32(3x1)= 6,$ тогда $r32(x1)= 2.$ Продолжая дальше получим:

y2 = 27= r32(x2+ 6x2⋅27+3)= r32(x2⋅3+3)

3x2+3 =27+ 32t

3x2 = 24+ 32t

Т.е. $r32(3x2)= 24,$ тогда $r32(x2)= 8.$ В итоге получим слово ВИСОКОС.

Ответ:

ВИСОКОС

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

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

Рассмотрим девять чисел $k,...,k , 1 9$ где $k ∈{0,1,2}. i$ При этом хотя бы одно число $k i$ отлично от нуля. С помощью этих чисел вырабатывают последовательность $u1,u2,...,u2019$ по формулам: $u1 = k1,u2 = k2,...,u9 =k9,ui+9 = r3(ui+ ui+1),$ $i= 1,2,...,2010,$ где $r3(a)$ — остаток от деления числа $a$ на $3.$ Найдите такое наименьшее натуральное число $l,$ что какие бы исходные числа $k1,...,k9$ мы ни взяли, в последовательности $u1,u2,...,ul$ каждое из чисел $0,1$ и $2$ гарантированно встретится хотя бы один раз.

Источники: Верченко - 2020, 11.6

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

Подсказка 1

Нам никто не говорил, какой конкретный набор для k будет дан. Давайте разбирать все варианты, которые могут возникнуть и мы уже решим задачу! Какой будет самым простым для нас?

Подсказка 2

В наборе k могут быть варианты: встречаются все три числа, набор состоит только из единиц или только из двоек, в наборе есть 1 и 2, но нет 0, в наборе есть только 1 и 0 и последний вариант - в наборе только 0 и 2. Для первых вариантов найти l не составляет проблем, осталось понять, что происходит в последних двух случаях!

Подсказка 3

Отдельного внимания стоит случай, где в k единицы не стоят рядом. Нам опять нужен перебор (посмотрим, что будет, если 1 стоит только на первой и/или последней позициях). Но не забудем, что мы решаем через полный перебор, поэтому остальные случаи тоже требует рассмотрения

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

Для каждого набора $k =(k ,...,k ) 1 9$ укажем такое минимальное $l$ , что в соответствующей последовательности $u ,u,...,u 1 2 l$ присутствует каждое из чисел 0, 1 и 2. Затем среди всех таких $l$ останется выбрать наибольшее — это и будет ответом в задаче.

1.

В наборе $k$ встречается каждое из чисел 0, 1 и 2. Тогда искомое $l$ не превосходит 9.

2.

Набор $k$ состоит только из 1. Тогда $u10 =...=u17 = 2$ и $u18 =0.$ Значит, $l= 18.$

Заметим, что случай « $k$ состоит только из 2» эквивалентен, так как если в последовательности ${un},$ отвечающей набору $2k =(2k1,2k2,...),$ заменить все 2 на 1, а 1 — на 2, то получится последовательность, соответствующая набору $k.$

3.

В наборе $k$ присутствуют и 1, и 2, но нет 0. Значит, среди чисел $u1,u2,...,u9$ есть два соседних $(us и us+1),$ одно из которых равно 1, а второе — 2. Тогда $us+9 = 0$ и $l≤ 17.$

4.

Набор $k$ состоит из 0 и 1.

Сразу заметим, что случай « $k$ состоит только из 0 и 2» эквивалентен, так как если в последовательности ${un},$ отвечающей набору $2k = (2k1,2k2,...),$ заменить все 2 на 1, а 1 — на 2, то получится последовательность, соответствующая набору $k.$

Теперь перейдем к разбору. Число 2 впоследствии дадут только две рядом стоящие 1. Поэтому рассматриваем варианты:

а) В $k$ есть рядом стоящие 1. Тогда $l≤19.$

б) В $k$ нет рядом стоящих 1.

Предположим, что 1 есть только на первой и/или последней позициях.

$∙$ Пусть $k = (1,0,...,0).$ В этом случае начало последовательности $u ,u ,... 1 2$ можно вычислить непосредственно:

{un} ={1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,2,1,0,...}

Тогда $l= 27.$

$∙$ Пусть $k = (1,0,...,0,1).$

{un}= {1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,2,1,0...}

Тогда $l= 18.$

$∙$ Пусть $k = (0,...,0,1).$

{un}= {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,2,1,0,...}

Тогда $l= 26.$

Итак, мы рассмотрели все случаи, когда 1 есть только на первой и/или последней позициях.

Иначе найдется номер $s$ такой, что $2≤ s≤ 8$ и $ks = 1.$ Рядом стоящих 1 нет, поэтому $ks− 1 =ks+1 = 0.$ Тогда $us+8 = us+9 = 1.$ Следовательно, $us+17 = 2$ и $l≤25.$

Ответ:

$l= 27$

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

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

Последовательность целых (необязательно различных) чисел $a,a ,a ,... 0 1 2$ удовлетворяет свойству $0≤ a ≤i i$ для всех целых неотрицательных $i$ , а также