Тема АЛГЕБРА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#120664

Пусть $a = [√1]+[√2]+...+[√n]. n$ Докажите, что среди элементов последовательности $a,a ,... 1 2$ есть лишь конечное количество простых чисел, и найдите наибольшее из них.

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

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

Подсказка 1:

Пусть k — наибольше целое число такое, что k² ≤ n. Значит, n < (k+1)². Ясно, что [√n] = k. Вас это ни на что не наталкивает?

Подсказка 2:

А давайте представим n как k² + t. Но ведь мы же тогда можем вычислить n-й член, используя переменные k и t, потому что t+1 последних слагаемых равны k, следующие k² - (k-1)² слагаемых равны k-1 и так дальше.

Подсказка 3:

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

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

Пусть $k$ — натуральное и $k2 ≤ n< (k +1)2.$ Тогда $[√n]= k.$ Значит, $[√n-]$ принимает фиксированное значение, равное $k,$ пока $n$ пробегает отрезок $2 2 [k ,(k +1) − 1],$ длина которого равна $2k+1.$ Значит, если $2 n = k +t,$ где $0≤ t≤2k,$ то

k∑−1 k∑−1 k∑−1 an = i(2i+ 1)+ k(t+1)= 2 i2+ i+k(t+1)= i=1 i=1 i=1

(k − 1)k(2k− 1) (k − 1)k (k − 1)k(4k+ 1) = -----3------+ --2---+ k(t+ 1)= -----6------+ k(t+ 1)

Заметим, что дробь $(k−1)k(4k+1) ----6----$ принимает целые значения при натуральных $k.$ Если множитель $k$ в числителе этой дроби не сокращается полностью со знаменателем, то данная дробь не взаимно проста с числом $k(t+1)$ (у них обоих есть общий делитель, входящий в $k$ и не сократившийся после деления на $6).$ Ясно, что при $k> 6$ такой множитель заведомо останется. Поэтому $k≤ 6$ и $n ≤72− 1= 48.$ Значит, при $n≥ 49$ все числа $an$ составные.

При $k= 6$ получаем формулу $an =125+ 6(t+ 1),$ где $t≤ 12.$ При $t= 12$ находим $a48 =203= 7⋅29,$ а при $t= 11$ получаем $a47 = 197$ — простое. Таким образом, наибольшее простое число в последовательности $an$ равно $197$ и соответствует индексу $n =47.$

Ответ:

$197$

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

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

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

Задача 2#122404

Дана последовательность $a = n!(n2− 2025n +1) n$ для всех натуральных $n.$ Найдите сумму первых $2025$ членов этой последовательности.

Источники: ММО - 2025, первый день, 11.2(см. mmo.mccme.ru)

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

Подсказка 1

Выглядит наша последовательность сложно, но явно намекает на разложение или замену. А нельзя ли n² - 2025n + 1 как-то переписать через факториалы? Попробуйте раскрыть скобки и посмотреть, не получится ли что-то телескопическое.

Подсказка 2

Хм, а если представить n² - 2025n как (n + 1)(n + 2) минус что-то? Тогда n! умножится на скобки, и может получиться разность факториалов. Как бы это оформить?

Подсказка 3

Окей, допустим, мы разложили аₙ в сумму вида (n + 2)! - (n + 1)! - 2027 • (n + 1)! + 2027 • n!. Теперь посмотрим на сумму а₁+ a₂+ … + a₂₀₂₅. Почти все слагаемые должны сократиться! Что останется в конце?

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

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

Представим $an$ в виде

an = n!((n +1)(n +2)− (n +1)− 2027n)= (n +2)!− (n+ 1)!− 2027n⋅n!=

=((n+ 2)!− (n+ 1)!)− 2027((n+ 1)!− n!).

Тогда получаем

a + a +...+ a = (2027!− 2!)− 2027⋅(2026!− 1!)= 2025 1 2 2025

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

Перейдём к более общей задаче: будем рассматривать последовательности $ak,n = n!(n2− kn +1),$ где k — фиксированное натуральное число, а $n$ — номер члена последовательности, и искать сумму первых $k$ членов таких последовательностей.

При $k= 1$ получаем, что сумма равна $a1,1 =1!(1− 1+ 1)=1.$

При $k= 2$ получаем, что сумма равна $a2,1+ a2,2 = 1!(1− 2+1)+ 2!(4− 4+1)= 2.$ Аналогично можно получить, что при $k= 3$ сумма равна $3$ . Возникающую гипотезу о том, что при произвольном $k$ искомая сумма равна $k,$ нужно строго доказать. Это можно сделать методом математической индукции.

База индукции уже проверена. Из предположения о том, что

ak,1+ ak,2+ ak,3+ ...+ak,k = k,

требуется вывести

a + a +a + ...+ a = k+1. k+1,1 k+1,2 k+1,3 k+1,k+1

Заметим, что

a =n!(n2 − (k+ 1)n+ 1)= n!(n2− kn +1 − n)= a − n!n =a − n!((n +1)− 1)= a − (n+ 1)!+ n!. k+1,n k,n k,n k,n

Следовательно,

ak+1,1 +ak+1,2+ ak+1,3+...+ak+1,k+1 =

=ak,1 +ak,2+ ak,3+ ...+ ak,k− ((k+ 1)!− 1!)+ (k+ 1)!((k+ 1)2− (k+ 1)(k+ 1)+1)=

=k− (k+ 1)!+1 +(k+ 1)!= k+ 1

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

Ответ:

$2025$

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

Задача 3#128022

Последовательность ${a} n$ задана по правилу: $a =2, 1$

an+1 = anan−1an−2 ...a1+1.

Докажите, что

1- 1- 1- a1 + a2 + ...+ an < 1.

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

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

-1 -1 -1 ----1--- a1 + a2 + ...+ an +a1a2...an ≤1

База для $n= 2$ очевидна. Докажем переход от $n$ к $n+ 1.$ По предположению индукции:

a1+ a1+ ...+ a1 ≤1− a-a-1...a- 1 2 n 1 2 n

Тогда

1-+ 1-+ ...+ 1-+ -1--+ ----1-----≤ 1− ---1----+ -1--+ ----1-----=1, a1 a2 an an+1 a1a2...an+1 a1a2...an an+1 a1a2...an+1

так как

--1- -----1---- a1a2...an+-1 ----1--- an+1 + a1a2...an+1 = a1a2...an+1 = a1a2...an

Переход доказан. Из доказанного выше следует утверждение задачи.

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

Задача 4#78964

Одиннадцати мудрецам завязывают глаза и надевают каждому на голову колпак одного из $1000$ цветов. После этого им глаза развязывают, и каждый видит все колпаки, кроме своего. Затем одновременно каждый показывает остальным одну из двух карточек — белую или черную. После этого все должны одновременно назвать цвет своих колпаков. Удастся ли это? Мудрецы могут заранее договориться о своих действиях (до того, как им завязали глаза); мудрецам известно, каких 1000 цветов могут быть колпаки.

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

Существует ровно $21111$ —разрядных последовательностей из $0$ и $1,$ из них с четным числом единиц — ровно половина, то есть $10 2 = 1024.$ Закодируем 1000 цветов тысячей таких последовательностей. Распределим разряды между мудрецами. Мудрец номер $k$ действует так: среди видимых им 10 цветов колпаков подсчитывает число $ak$ тех, у кого в $k$ -м разряде стоит $1.$ Если это число четно, он показывает черную, а иначе-белую карточку.

После этого каждый мудрец может вычислить все разряды в коде цвета своего колпака, кроме одного — за который он сам отвечает. Для этого он подсчитывает число $bk$ единиц в $k$ -х разрядах девяти мудрецов (кроме себя и мудреца номер $k$ ), и если четность $bk$ совпадает с показанной четностью $ak,$ у него в $k$ м разряде $0,$ иначе $1.$ Недостающий разряд восстанавливается благодаря четности общего числа единиц в коде.

Ответ:

Да

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

Задача 5#82677

Дана последовательность $a n$ : 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, $...$
(одна единица, две двойки, три тройки, четыре четверки и т.д.) и еще одна последовательность $bn$ такая, что $abn =ban$ для всех натуральных $n$ .

Известно, что $bk = 1$ при некотором $k> 100$ . Докажите, что $bm =1$ при всех $m >k$ .

Источники: СПБГОР - 2024, 11.2 (см. www.pdmi.ras.ru)

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

Подсказка 1

Для начала давайте поймем что-то про последовательность {a_i}. Как минимум поймем на каких местах у нас стоит число k. Это важно для нас, так как если мы хотим выбрать какое-то конкретное m(и посмотреть откуда же может быть получено противоречие), то нам надо понимать, как связан номер и значение a_m. Как зависит значение от m?

Подсказка 2

Для любых номеров m, которые располагаются между t(t + 1)/2 + 1 и (t + 1)(t + 2)/2, a_m = t + 1. Если от нас требуется доказать, что начиная с какого-то номера у нас b_i = 1, не будем мелочиться и докажем, начиная почти для всех(с какого-то маленького), по индукции. Но давайте, для начала, так сказать, для создания благоприятной обстановки, поймем, как все таки делать индукцию. Ведь переход от n к n + 1 здесь кажется странным. Однако переход от k(k + 1)/2 к (k + 1)(k + 2)/2 выглядит более разумно, ведь мы знаем все значения a_i, для i из этого отрезка.

Подсказка 3

Верно, переход такой нам легко дается, так как a_i из этого промежутка равно t + 1, а значит, это b_(t + 1), но для всех меньших мы доказали. Что осталось написать по этой задаче? Является ли это полным решением?

Подсказка 4

Не является, так как t + 1 не всегда входят в уже доказанный промежуток. Для t = 1, 2 - это неверно. Значит, надо в качестве базы использовать t >= 3. Но это подходит под условие нашей задачи, а значит, если у нас b_k = 1, то и все последующие будут равны 1.

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

Возьмём число $m : t(t+1)+ 1≤ m ≤ (t+1)(t+2) 2 2$ , заметим, что для любого такого $m$ $a = t+1 m$ , тогда $b = b = a t+1 am bm$ , тогда если $bm =1$ , то $abm =1$ , тогда $bt+1 =1$ , и наоборот.

Значит, $bt+1 = 1 ⇐⇒ bm = 1$ для $t(t+1) (t+1)(t+2) m ∈ [ 2 + 1; 2 ]$

Значит, и $bt+1 ⁄=1 ⇐⇒ bm ⁄= 1$

Если $b3 =1$ , то

2× 3 3× 4 ∀m ∈ [-2-+ 1;-2--]:bm = 1 т.е. b4 = b5 =b6 = 1

Докажем тогда по индукции, что $∀m > 3 bm = 1.$

База уже есть. Переход будем делать от $m ∈ [3;t(t+21)]$ к $m ∈[3;(t+1)2(t+2)].$

Заметим, что $t+ 1< t(t+21)$ при $t>3 ⇒ bt+1 = 1$ , но по предположению индукции $∀m ∈ [t(t+21)+ 1≤ m≤ (t+1)2(t+2)]:bm =1$ , значит,

∀m ≥3 :bm = 1, если b3 = 1

Аналогичными рассуждениями

∀m ≥3 :bm ⁄= 1, если b3 ⁄= 1

Итого т.к. $bk =1$ , $k> 100$ , то $b3 =1$ , а значит, $∀m > 3$ :

bm = 1⇒ ∀m > k bm =1

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

Задача 6#83743

Дана последовательность:

∘ ∘ n ∘ a1 = cos10 ,a2 =cos100,...,an = cos(10) ,...

Найдите наименьшее значение выражения

a1⋅cosx +(a2+ a2023+a2024)⋅sinx, где x∈ ℝ

Источники: Звезда - 2024, 11.4 (см. zv.susu.ru)

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

Подсказка 1

Даны косинусы углов в градусах. Мы же знаем, что косинус — периодичная функция с периодом 360 градусов. Попробуем заметить что-нибудь, связанное с периодичностью косинуса, про аргументы двух соседних членов последовательности, то есть 10^n и 10^(n+1).

Подсказка 2

После того, как мы поняли, что из себя представляют а_2023 и а_2024, осталось преобразовать выражение с x по известным тригонометрическим формулам. В этот момент уже будет понятно, как искать наименьшее значение, ведь тригонометрические функции принимают ограниченные значения.

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

Посмотрим на разность градусных мер углов у соседних членов последовательности:

n n−1 n−1 n−3 n−3 10 − 10 = 10 (10− 1)=9⋅1000⋅10 =360⋅25⋅10

Если $n≥ 3,$ то эта разность делится на 360. Тогда косинусы равны, то есть $a3 =a4 = ...= a2024.$

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

∘ ∘ ∘ ∘ a2+a2023+ a2024 = cos100 + 2cos1000 =cos100 + 2cos(360 ⋅3− 80)=

= cos(90∘+ 10∘)+ 2cos80∘ =− sin10∘+2 sin10∘ =sin 10∘

Теперь подставим в искомое выражение:

a1⋅cosx +(a2+ a2023+a2024)⋅sinx =

= cos10∘⋅cosx+ sin10∘⋅sinx= cos(x− 10∘)

Наименьшее значение косинуса, как известно, равно $− 1.$

Ответ:

$− 1$

Курсы

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

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

Задача 7#85565

Последовательность многочленов $P(x),P (x),... 0 1$ задана условиями $P (x)= x,P (x)= P (x− 1)P (x+ 1) 0 n n− 1 n−1$ при $n≥ 1.$ Найдите наибольшее число $k,$ для которого $P100(x)$ делится на $k x .$

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

Заметим, что $k$ совпадает с кратностью корня $x =0.$ Каждый из данных корней был получен из корня $1$ или $− 1$ у многочлена $P99(x),$ каждый из которых в свою очередь появился из корня $− 2,0,$ или $2$ у многочлена $P99(x),$ и так далее. В итоге получим, что каждому корню $0$ многочлена $P100(x)$ соответствует последовательность из $101$ числа $0,...,0,$ в которой каждые два соседних числа отличаются на $1.$ Причем каждой такой последовательности соответствует корень $0$ многочлена $P100(x).$ Тогда $k$ равно количеству таких последовательностей. Будем идти по последовательности слева направо. При переходе к следующему члену последовательности мы либо прибавляем к предыдущему члену $1,$ либо вычитаем, причем прибавлений и вычитаний поровну. В итоге получаем ответ $50 k =C100.$

Ответ:

$C50 100$

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

Задача 8#97053

Последовательность { $x n$ } определена рекурсивно: $x = a 1$ при некотором натуральном $a,$ а также $x = 2x + 1. n+1 n$ Пусть $y =2xn − 1. n$ Какое максимальное количество подряд идущих простых чисел может быть в последовательности { $yn$ }?

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

Подсказка 1

Для начала рекомендуется заметить что-нибудь про последовательность. Поймите ответ, написав несколько первых членов последовательности при маленьких a. Поймите, что x_i тоже должны быть простыми.

Подсказка 2

Будем доказывать, что ответ 2. Как доказать, что среди трех подряд идущих членов обязательно будет составной? На что он может делиться?

Подсказка 3

Попробуйте доказать, что x_3 | y_2. Воспользуйтесь тем, что x_3 сравнимо с 7 по модулю 8, то есть 2 - квадратичный вычет по модулю x_3.

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

Пусть $k$ — максимальное количество подряд идущих простых чисел может быть в последовательности { $y n$ }. Без ограничений общности, можем считать, что данная оценка достигается для подпоследовательности $y1,...,yk.$

Оценка. Докажем, что если при некотором $i$ число $yi$ — простое, то и число $xi$ — простое. Действительно, пусть $xi$ кратно некоторому натуральному $d$ , тогда

x d yi =2 i − 1 кратно 2 − 1

что влечет противоречие с простотой числа при $d> 1.$ В частности, если подпоследовательность ${y}k ii=1$ состоит только из простых чисел, то и подпоследовательность ${x}k i i=1$ состоит лишь из простых чисел.

Теперь докажем, что для каждого нечетного простого числа $a$ хотя бы одно из чисел $y ,y ,y 1 2 3$ является составным. Предположим противное, пусть $y1,y2$ и $y3$ — простые числа, тогда $x1,x2,x3$ тоже простые числа. Поскольку $x1 ≥3$ нечетно, имеем $x2 >3$ и $x2 ≡ 3 (mod 4);$ следовательно, $x3 ≡ 7 (mod 8).$ Таким образом, $2$ является квадратичным вычетом по модулю $p= x3,$ поэтому $2 2 ≡s (mod p)$ для некоторого целого числа $s$ и, следовательно,

x (p−1)∕2 p− 1 2 2 = 2 ≡ s ≡ 1 (mod p)

Это означает, что $p|y , 2$ т. е. $2x2 − 1= x = 2x + 1. 3 2$ Но легко показать, что $2t− 1> 2t+1$ для всех целых $t>3.$ Противоречие. Тем самым мы показали, что $k ≤2.$

Пример. Если $a =2,$ то числа $y = 3 1$ и $y = 31 2$ являются простыми числами.

Ответ:

$2$

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

Задача 9#121181

Определим последовательность $x ,x,... 1 2$ начальными условиями $x = 2 1$ , $x =4 2$ и рекуррентным соотношением

2n xn+2 = 3xn+1− 2xn +xn для n ≥1.

Докажем, что предел $nl→im∞ xn2n-$ существует и удовлетворяет неравенствам

√- 1+--3 ≤ lim xnn ≤ 3. 2 n→∞ 2 2

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

Индукцией докажем, что $xn+1 ≥2xn.$ Для $n =1$ это верно. Предположим, что неравенство выполняется для $n.$ Тогда:
$n xn+2 = 2xn+1+ (xn+1− 2xn)+ 2-> 2xn+1. xn$
Аналогично докажем $xn+1 ≤ 2xn +n.$ Для $n= 1$ это верно. Используя $xn ≥2n$ (это следует из предыдущего факта и начальных условий), получаем:
$xn+2 ≤3xn+1− 2xn +1 =2xn+1+ xn+1− 2xn +1= 2xn+1+ 2xn +n − 2xn+ 1≤ 2xn+1 +n +1.$
Последовательность $xn yn = 2n$ возрастает и ограничена:
$n−1 yn+1 ≤ yn+ n-≤ y1+ ∑ k-< ∞. 2n k=1 2k$
Следовательно, предел $c= lim yn n→∞$ существует(теорема Вейерштрасса).
Преобразуем рекуррентное соотношение для $yn :$
$4y − 2y =4y − 2y + --1-. n+2 n+1 n+1 n 2nyn$
Суммируя для $n= 1,...,m$ и подставляя начальные условия ( $y1 = y2 =1$ ) получаем:
$4ym+2− 2ym+1 = 2+∑m -1-. i=12iyi$
При $m → ∞$ и $yn → c :$
$∞∑ -1- 2c= 2+ i=12iyi.$
Оценим бесконечную сумму, ведь $1≤ yn ≤ c,$ ведь последовательность $yn$ - возрастает и имеет предел, тогда:
$1 ∑∞ 1 ∑∞ 1 c ≤ 2iyi ≤ 2i = 1 i=1 i=1$
Тогда имеем неравенство:
$2+ 1≤ 2c≤ 3, c$
что равносильно $c≤ 3 2$ и $2c2 ≥ 2c+ 1,$ что и дает оценку $2c≥1 +√3,$ ведь $c≥ 0.$

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

Задача 10#67675

Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность $(a ) n$ строится следующим образом: $a1 = a2 = 1$ и при $n> 2$ число $an$ — такое минимальное натуральное число, что среди чисел $a1,a2,...,an$ нет трёх, образующих триплет. Докажите, что $n2 +7 an ≤--8--$ для любого $n.$

Источники: ММО-2023, 11.6 (см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Если aₓ > aₓ₊₁, то при выборе x элемента последовательности мы бы взяли aₓ₊₁, а не aₓ. Отсюда следует, что наша последовательность не убывает. Причем, если какое-то натуральное число n встретилось в последовательности в первый раз, следующий элемент последовательности будет также равен n. Может тогда некоторые элементы можно выкинуть...

Подсказка 3

Мы уже поняли, что наша последовательность не убывает и при этом a₂ₓ = a₂ₓ₋₁. Тогда требуемое неравенство можно доказать только для нечетных номеров. Введем новую последовательность {bₓ}: bₓ=a₂ₓ₋₁. Тогда нам нужно доказать, что bₓ <= ((2x-1)²+7)/8 = x(x-1)/2+1. Теперь надо подумать о том, какими свойствами обладает последовательность {bₓ} и как мы собираемся доказывать наше неравенство...

Подсказка 4

Из свойств последовательности {aₓ} вытекает, что {bₓ}- строго возрастает. Попробуйте теперь воспользоваться методом от противного вместе с принципом крайнего предположив, что bₓ- первый элемент последовательности, для которого не выполняется неравенство.

Подсказка 5

Пускай bₓ- первый элемент последовательности, для которого не выполняется неравенство. Тогда: bₓ > x(x-1)/2+1. Заметим также, что bₓ₋₁ < x(x-1)/2+1, иначе бы bₓ₋₁ >= x(x-1)/2+1 > (x-1)(x-2)/2+1, что противоречит выбору bₓ. Это означает, что среди чисел от 1 до x(x-1)/2+1 существуют все x-1 элементов последовательности (b₁, b₂, ... bₓ₋₁). Попробуйте теперь найти противоречие в количестве чисел в интервале от 1 до x(x-1)/2+1, которые не являются членами последовательности

Подсказка 6

Пускай таких чисел s штук. Тогда: s = x(x-1)/2+1-(x-1) = (x-1)(x-2)/2+1 = С²ₓ₋₁+1. Подумайте, как могло случится так, что какое-то число n (1 < n < x(x-1)/2+1)) не стало членом последовательности...

Подсказка 7

Если n не стало членом последовательности, то n образует триплет с какими-то двумя членам последовательности, меньшими bₓ. Всего таких пар С²ₓ₋₁. Т.к. каждая пара могла "забраковать" не более одного числа в промежутке от 1 до x(x-1)/2+1, то s <= С²ₓ₋₁. Это и является противоречием.

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

Очевидно, что последовательность не убывает. Действительно, неравенство $a > a n n+1$ противоречило бы выбору $a . n$ Также понятно, что любое число повторяется не более, чем дважды, иначе в последовательности найдутся три одинаковых числа, а они образуют триплет. Теперь легко видеть, что если число $c$ впервые встречается в последовательности в качестве $an,$ то $an+1 = an = c.$

Таким образом, для любого натурального $k$ верно равенство $a2k−1 = a2k.$ Заметим, что тогда достаточно доказать требуемое неравенство только для нечетных индексов:

(2k− 1)2 +7 (2k)2+7 a2k = a2k− 1 ≤---8-----≤ ---8---

Положим $bk = a2k−1.$ Тогда нужно доказать, что

2 bk ≤ (2k− 1)-+-7= k(k− 1)+ 1 8 2

Отметим, что последовательность $(bn)$ обладает тем свойством, что при $k> 1$ очередной член последовательности $bk$ - минимальное натуральное число, которое не образует триплет с парами чисел из ${b1,...,bk−1},$ где пара может иметь вид $(bi,bi).$ При этом $bk > bk−1,$ то есть $(bn)$ строго возрастает, в отличие от $(an).$

Пусть $n$ - минимальное натуральное число, для которого требуемое неравенство неверно, то есть $bn > n(n−21)+1.$ Это означает, что среди чисел от $1$ до $n(n−21)+ 1$ содержится ровно $n− 1$ член последовательности, поскольку при $m < n$ по предположению имеем

bm ≤ m(m-− 1) +1< n(n−-1)+ 1 2 2

Обозначим через $s$ количество чисел в промежутке от 1 до $n(n−1)+ 1, 2$ не принадлежащих последовательности $(bn).$ Тогда

s= n(n-− 1)+ 1− (n − 1)= (n−-1)(n−-2)+ 1= C2n−1+1 2 2

Обозначим эти числа $di,1≤ i≤ s.$ В силу минимальности каждого из $bm$ для любого $1≤ k≤ s$ найдутся такие числа $bik,bjk,$ где $ik ≤ jk ≤ n− 1,$ что $(bik,bjk,dk)$ - триплет. При это можно считать, что $dk$ - наибольший элемент в триплете, иное бы противоречило выбору наименьшего элемента последовательности $(bn),$ большего $dk.$ Отсюда $ik < jk.$ Тогда число способов выбрать пару $(ik,jk)$ не превосходит $C2n−1,$ то есть не больше способов выбрать два различных индекса из ${1,2,...,n− 1}.$ В то же время парами $(ik,jk)$ нужно обеспечить $s>C2n−1$ чисел $di.$ Полученное противоречие завершает решение.

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

Задача 11#67942

Дана последовательность ${a}, n$ в которой $a = 19, 1$ а отношение каждого следующего элемента к предыдущему при всех целых $n≥ 2$ равно

an (n2+ 1)⋅n an−1 = (n−-1)2+-1

Найдите отношение 2023-го члена последовательности к сумме её первых 2022 членов.

Источники: Ломоносов-2023, 11.6 (см. olymp.msu.ru)

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

Подсказка 1

Напрямую искать это отношение не хочется. Давайте тогда начнем с aₙ, а там и придумаем. Вспомним, что у нас условие на отношение aₙ/aₙ₋₁. Как им хорошо можно воспользоваться?

Подсказка 2

А давайте перемножим эти условия для n, n-1, ..., 2, 1! Получится, что aₙ/a₁ = aₙ/aₙ₋₁ ⋅ aₙ₋₁}/aₙ₋₂} ⋅ ... ⋅ a₂/a₁ = (n²+1)n/((n-1)²+1) ⋅ ... ⋅ (2²+1)/(1+1) = (n²+1)⋅n!/2. У нас тут есть отношение aₙ к a₁, может тогда легче найти сумму/a₁, ведь отношение получившихся выражений как раз будет отношением aₙ/сумма? Давайте так и поступим)

Подсказка 3

Обозначим сумму первых n-1 члена за Sₙ₋₁. Даже зная aₙ/a₁ для любого n, не очень понятно, как хорошо свернуть сумму. А вдруг можно представить выражение (n²+1)⋅n!/2 как разность двух каких-то выражений, которые зависят от n и n-1? Например как какое-то bₙ - bₙ-₁. Тогда у нас выйдет, что Sₙ₋₁/a₁ будет bₙ₋-b₀, и зная эти b мы легко найдем то, что нам надо!

Подсказка 4

Пошаманим с aₙ/a₁: (n²+1)⋅n!/2 = 1/2 ⋅ (n(n+1) - (n-1)) ⋅ n! = n⋅(n+1)!/2 - (n-1)⋅n!/2. Вот как раз наши bшки! Обозначим тогда bₙ = n⋅(n+1)!/2. Остается найти сумму и посчитать отношение)

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

Найдем $an-, a1$ перемножив указанное в условии отношение для различных $n :$

an -an- an−-1 a2 (n2+-1)n-- ((n−-1)2-+1)(n-− 1) (22+-1)2- (n2+-1)n!- a1 =an−1 ⋅an− 2 ⋅⋅⋅a1 = (n − 1)2+1 ⋅ (n− 2)2+ 1 ⋅⋅⋅ 1+ 1 = 2

Представим его в виде разности:

2 an = (n-+-1)n!-= 1(n(n+ 1)− (n− 1))n!= n(n-+1)!− (n-− 1)n!=bn− bn−1, a1 2 2 2 2

где

bn = n(n+-1)! 2

Тогда отношение суммы первых $n$ членов к $a1$ равно

Sn a1+a2+-⋅⋅⋅+-an n(n+-1)! a1 = a1 = (b1 − b0)+(b2− b1)+⋅⋅⋅+(bn− bn−1)= bn− b0 = 2

Стало быть, ответ при $n= 2023$ равен

2 2 2 -an-= -an∕a1-= (n-+-1)n!= n-+-1= n-−-1+-2= n+ 1+ --2-= 2024-1-- Sn−1 Sn−1∕a1 (n − 1)n! n− 1 n− 1 n− 1 1011

Ответ:

$2024-1- 1011$

Интенсивы

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

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

Задача 12#68032

Арифметическая прогрессия $a ,a,... 1 2$ задана первыми двумя членами: $a = 381,a = 406. 1 2$ Определим последовательность $b k$ следующим образом: $b1 = a1 = 381,bk+1 =bk⋅ak+1$ для каждого $k ≥1.$ Тогда $b2 = 381⋅406= 154686.$ В записи этого числа используется 5 различных цифр: $1,4,5,6$ и 8. А какое наименьшее количество различных цифр может использоваться в записи числа $bk$ для натурального $k?$

Источники: Турнир Ломоносова-2023, 11.2 (см. turlom.olimpiada.ru)

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

Подсказка 1

Нам дали всего лишь два члена каждой последовательности… Кажется, это маловато, поэтому давайте посчитаем еще несколько членов каждой из последовательностей! Что интересное мы видим?

Подсказка 2

Да, третий член последовательности b имеет всего лишь 2 различные цифры в своей записи! Что осталось сделать, чтобы сказать, что 2 — это ответ на вопрос задачи?

Подсказка 3

Да, достаточно показать, что любой член последовательности b не может состоять из одной цифры! Перебирать дальше члены последовательностей не имеет смысла, ведь числа получаются огромные, что может нам помочь в таком случае?

Подсказка 4

Конечно, надо подумать про делимость всех членов b, после третьего! Поскольку a₄ кратно 4, то все члены последовательности b, начиная с 4-ого кратны четырём! А что еще можно сказать про каждый член последовательности b?

Подсказка 5

Верно, каждый из них оканчивается на 6! Что осталось показать, чтобы решить задачу?

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

Оценка. Докажем, что всего одна цифра в записи $b k$ не может быть. Найдем $b ,a : 3 4$

a3 = a2+(a2− a1)= 431;

a4 = a3+(a3− a2)= 456;

b = b ⋅a = 66 669 666. 3 2 3

Заметим, что $a4$ делится на $4,$ значит $b4$ и все $bk$ будут делится на $4.$ Кроме того, каждое из $ak$ оканчивается или на $1,$ или на $6.$ Поэтому все $bk$ при $k ≥4$ будут оканчиваться на $6(6⋅1= 6,6⋅6 =36).$ Получается, если в записи $bk,k≥ 4,$ будет всего одна цифра, то это цифра $6.$ Тогда последние две цифры $bk$ это $66,$ т.е. $bk$ не делится на $4,$ противоречие.

Пример. В записи $b3$ используются только две цифры.

Ответ: 2

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

Задача 13#68242

Имеется устройство, которое строит последовательность чисел $x,x ,x ,... 0 1 2$ следующим образом: первые два члена $x 0$ и $x 1$ мы задаем самостоятельно, а последующие члены устройство вычисляет так: $x2 =x0+ 13⋅(x1+ k1),x3 = x1+ 13 ⋅(x2+ k2),...$ Здесь $k1,k2,...$ — – некоторая фиксированная ключевая последовательность. При этом все числа $x0,x1,x2,...$ и $k1,k2,...$ являются целыми, лежащими в пределах от 0 до 32 включительно. (Если в процессе вычислений получится число, превосходящее 32, то результат будет заменен его остатком от деления на 33; например, $16+ 13 ⋅2 =9.)$ С помощью этого устройства построили две последовательности $a0,a1,a2,...$ и $b0,b1,b2,...,$ по первым членам $a0 =1,a1 = 3$ и $b0 =1,b1 =12.$ Верно ли, что найдётся ключевая последовательность $k1,k2,...$ и некоторое целое $t,$ большее 0, такие, что выполняются условия:

a) $bt = at,bt+1 =at+1?$

б) $bt = at+1?$

Решение обоснуйте.

Источники: Верченко-2023 (см. v-olymp.ru)

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

Пункт а), подсказка 1

У вас есть равенство двух членов одной последовательности двум другим. А как можно выразить, например предыдущий член последовательности через два соседних? Попробуйте так прийти к противоречию)

Пункт б), подсказка 1

Мы понимаем, что последовательности устроены одинаковым образом, так еще и ключевая последовательность у них одинаковая. Что можно сделать, чтобы вообще исключить эту последовательность?

Пункт б), подсказка 2

Вычесть одну последовательность из другой! По факту, в этой последовательности тогда нужно будет понять, есть там единица, или нет. В таком случае посмотрите на первые члены и на то, по какому модулю у нас все происходит и придите к противоречию)

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

а) Для всех $t≥1$

at+1 = at− 1+13(at+ kt),at−1 =at+1− 13(at+kt)

Поэтому, если $bt = at,bt+1 =at+1$ , то $bt−1 =at−1,...b1 = a1,b0 = a0$ , что противоречит условию.

б) Удобно перейти к разностям полублоков $zt = bt− at$ (везде далее действия с полублоками (умножение, сложение и вычитание) производятся по модулю $M$ ) и выяснить, может ли 1 появиться в ${z} t$ . Из уравнения шифрования

bt+1 = bt−1+ 13(bt+kt),t≥ 1

a =a + 13(a +k ),t≥ 1 t+1 t−1 t t

получаем после вычитания

zt+1 = zt−1+ 13zt,t≥1,

что последовательность разностей не зависит от ключа $kt$ . По условию $(z0,z1)= (0,9),(z0,z1,M )= 3$ , поэтому все члены последовательности будут делиться на $3$ , и единицы там не будет.

Ответ:

а) нет

б) нет

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

Задача 14#69822

Последовательность ${a },n∈ℕ, n$ задана такими равенствами: $a = 2, 1$ $a = 1 2$ и

-2 -1-- -1-- an = an−1 + an+1,n ≥2

Найдите такие $n,$ при которых

|an|≤ 10−3

Источники: САММАТ-2023, 11.3 (см. sammat.samgtu.ru)

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

Подсказка 1

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

Подсказка 2

Теперь мы понимаем, что член новой последовательности равен среднему арифметическому соседних членов. А у какой последовательности как раз есть такое свойство?

Подсказка 3

У арифметической прогрессии! Теперь решить задачу не составит труда,)

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

В условии задана последовательность, каждый член которой, начиная со второго, является средним гармоническим своих соседей. От такой “гармонической прогрессии” легко перейти к арифметической прогрессии, если рассмотреть последовательность обратных: $1- bn = an.$ Тогда условие переписывается в виде

bn−1+bn+1 bn =----2----

Так что по характеристическому свойству мы имеем арифметическую прогрессию. Из условия задачи находим её первый и второй члены:

b1 = 12,b2 = 1

Тогда разность равна $12$ и по формуле $n$ -го члена

bn = n 2

Теперь остаётся решить

|an|≤10−3 ⇐⇒ bn ≥ 103 ⇐⇒ n ≥2⋅103

Ответ:

$n ≥2⋅103$

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

Задача 15#73166

Последовательность положительных чисел $a,a ,... 1 2$ такова, что для всех натуральных $i$ выполнено $a2 + aa ≤ a +a i+1 ii+2 i i+2$ . Докажите, что $a2022 ≤ 1$ .

Источники: IMO shortlist - 2022, A1

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

Заметим, что $a2 − 1 ≤a + a − aa − 1 n+1 n n+2 n n+2$ , откуда

2 an+1− 1≤ (1 − an)(an+2− 1).

Предположим, что существует натуральное $n$ такое, что $a >1 n+1$ и $a > 1 n+2$ . Тогда из полученного ранее неравенства заключаем, что $0 <1 − a <1< 1+ a n n+2$ , откуда $a2 − 1< (a +1)(a − 1)=a2 − 1 n+1 n+2 n+2 n+2$ . С другой стороны $a2 − 1≤ (1 − a )(a − 1)< (1+ a )(a − 1)= a2 − 1 n+2 n+3 n+1 n+1 n+1 n+1$ — противоречие.

Предположим, что $a2022 > 1$ . Тогда из только что доказанного следует, что $a2021 ≤1$ и $a2023 ≤ 1$ . То есть $2 0 <a2022− 1≤ (1 − a2021)(a2023− 1)≤ 0$ — противоречие. Таким образом, $a2022 ≤ 1$ .

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

Задача 16#73696

Множество натуральных чисел разбито на бесконечные арифметические прогрессии с разностями $d ,d,.... 1 2$

(a) Докажите, что если число прогрессий конечно, то $d11 +d12 + ...= 1.$

(b) Верно ли утверждение пункта (а), если число прогрессий бесконечно?

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

Подсказка 1, пункт а

В первом пункте можно рассмотреть некоторое количество последовательных чисел и посчитать, сколько там членов каждой прогрессии. Но количество этих чисел стоит подобрать так, чтобы вычислять было проще.

Подсказка 2, пункт а

С одной стороны, количество чисел в отрезке равно сумме количеств членов каждой из прогрессий в этом отрезке. А с другой стороны?

Подсказка 1, пункт б

Тут нужно найти контрпример. Чтобы было проще искать, найдите сначала какое-нибудь бесконечное множество таких чисел, что сумма чисел, обратных им, меньше 1.

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

$a)$ Пусть число прогрессий равно $k.$ Докажем, что сумма $-1 +-1+ ...+ -1= 1. d1 d2 dk$ Пусть $M$ — наименьшее общее кратное чисел $d1,d2,...,dk.$ Рассмотрим любой отрезок из $M$ последовательных натуральных чисел; в нём будет $M- di$ членов $i$ -й прогрессии с разностью $di$ ( $i= 1,2,...,k$ ). Поэтому $M- M- M- d1 + d2 + ...+ dk = M.$ Если сократить на $M,$ получим требуемое.

$b)$ Приведём контрпример. Рассмотрим прогрессии $1,11,...(d1 = 10),2,22,...(d2 = 20),3,43,...(d3 = 40),...$ каждый раз $d$ увеличивается вдвое. Если какой-то член прогрессии встретился в предыдущих, то и все остальные её члены также встречались. Такие прогрессии вычеркнем. Оставшееся множество прогрессий содержит все натуральные числа ровно по одному разу, а $1 1 1 1 1 d1 +d2 + ...< 10 + 20 + 40 + ...< 0,2< 1.$

Ответ:

$b)$ Нет

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

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

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

Задача 17#74874

Обозначим через $d(n)$ количество натуральных делителей числа $n.$ Последовательность натуральных чисел $a ,a,...,a 1 2 400$ удовлетворяет условию

an+1 = d(an)+ d(n)

Докажите, что в этой последовательности не более $210$ простых чисел.

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

Отметим, что если $n$ не является квадратом натурального числа, то хотя бы одно из чисел $a ,a n n+1$ не является простым. Докажем это утверждение от противного – тогда $an$ простое. Число $. d(n).. 2,$ так как $n$ не квадрат, а $d(an)=2.$ Следовательно, $a = d(a )+d(n) ... 2 n+1 n$ , при этом $a > 2, n+1$ поэтому $a n+1$ не является простым – противоречие.

Вычеркнем из последовательности $an$ все элементы, индексы которых являются квадратами, а все остальные элементы разобьем на пары. Между любыми двумя квадратами находится четное количество чисел ( $. (a+ 1)2− a2− 1= 2a .. 2$ ), поэтому такой способ ставит в пару подряд идущие числа. По доказанному, в каждой паре находится не более одного простого элемента, значит среди $400− 20 =380$ невычеркнутых элементов есть не более, чем $190$ простых. Вычеркнутые элементы могут быть простыми. Их количество равно $20,$ поэтому общее число простых элементов можно оценить как $190+20= 210,$ что и требовалось доказать.

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

Задача 18#74876

Последовательность чисел $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).$

Ответ:

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

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

Задача 19#75281

Дана бесконечная последовательность натуральных чисел $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.$

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

Задача 20#90317

Последовательность $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$ таких что