Тема АЛГЕБРА

Последовательности и прогрессии → .05 Периодичность и зацикливание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На доске записаны в ряд сто чисел, отличных от нуля. Известно, что каждое из них, кроме первого и последнего, является произведением двух чисел, соседних с ним. Первое число равно $7.$ Какое число записано последним?

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

Подсказка 1

Удобно рассмотреть 4 подряд идущих числа (скажем, с первого по четвёртый члены), ведь для двух центральных выполнено свойство из условия. Посмотрите, что это может давать, как связь первого и четвёртого, ведь нам нужно по первому члену понять, чему равен последний член.

Подсказка 2

В силу свойства из условия можно сказать, что a_1 * a_4 = 1. Но это верно и для следующих индексов. Как нам тогда найти сотый член?

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

Обозначим данные числа через $a = 7,a ,...,a . 1 2 100$ По условию $a = a ⋅a 2 1 3$ и $a =a ⋅a . 3 2 4$ Так как в заданном ряду нет нулей, то перемножив эти равенства почленно, получим $a1⋅a4 = 1,$ то есть $-1 a4 =a1.$ Аналогично из равенств $a5 = a4 ⋅a6$ и $a6 = a5⋅a7$ получим, что $-1 a7 = a4.$ Таким образом, $a7 =a1,$ значит, последовательность периодична, а длина ее периода — $6.$ Следовательно, $a1 = a7 = ...= a97 =7,$ тогда $-1- 1 a100 = a97 = 7.$

Ответ: 1/7

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

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

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

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

Последовательность периодична с периодом 7. В ней оставлены только 1-й, 10-й, 100-й, 1000-й и т.д. члены. Докажите, что полученная последовательность периодична.

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

Подсказка 1

Если нам дано, что наша последовательность периодична, то значение i-ого члена определяется значением члена с номером i mod 7. Тогда и значение 10, 100, 1000, … членов определяется исключительно их номерами mod 7. Значит, что нам нужно доказать?

Подсказка 2

Нам нужно доказать, что степени 10 зацикливаются mod 10. Ну это верно, так как мы смотрели вебинары по теории чисел и знаем, что оно циклится (более того, проходит всю систему вычетов по модулю 7). Либо же можно самостоятельно выписать этот цикл и убедиться в верности данного факта.

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

Пусть $(a ,a ,...,a) 1 2 7$ — период данной последовательности ${a }. n$ Для того чтобы найти члены новой последовательности, надо найти остатки от деления на $7$ чисел $10,100,1000,...$ Тогда удобно рассмотреть деление числа 1000…на $7$ «в столбик», выписывая на каждом шаге получающиеся остатки: $3,2,6,4,5,1,...$ Заметим, что, получив остаток $1,$ мы опять делим $10$ на $7$ и получаем остаток $3.$ Следовательно, последовательность остатков периодична, поэтому периодична и новая последовательность. Ее период: $(a1,a3,a2,a6,a4,a5).$

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

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

$P$ — некий полином с целыми коэффициентами, $A$ и $M$ — целые числа. Построим последовательность $a n$ , где $a = A 1$ , и $a =P (a) n+1 n$ и пусть $rn$ — остаток от деления $an$ на $M$ .

1. Пусть $P(x)= x2+ x+ 1,A = 1,M = 32022$ . Докажите, что период последовательности $rn$ (то есть, такое наименьшее $t$ , что $rn+t = rn$ при достаточно больших $n$ ) равен 2.

2. Найдите длину предпериода той же последовательности (то есть такое наибольшее $n$ , что $an+t ⁄= an$ , где $t$ — период).

3. Назовем полином стабильным по модулю $M$ , если существует $B$ , такое что для любого $A$ найдется $k$ , для которого $rk = B$ . Докажите, что полином $3 2 f = x − x − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Докажите, что многочлен $P (x)= x2− 3x +12$ стабилен для бесконечного числа натуральных $M$ .

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

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

Если мы докажем, что с какого-то момента a_(n+2) - a_n = a_(n+1) - a_(n-1) (mod 3^2022), то и требуемое тоже будет доказано. Попробуйте выразить a_(n+2) - a_n через a_(n+1) и a_(n-1).

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

Мы получаем, что если a_(n+1) - a_(n-1) делится на 3^k, то и a_(n+2) - an делится на 3^k. Теперь, если мы докажем, что a_(n+1) - a_(n-1) делится на 3^(k+1), то сможем сказать, что с какого-то момента k станет >= 2022. Попробуйте для этого доказать, что a_(n+1) и a_(n-1) имеют одинаковые остатки при делении на 3.

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

Для этого посмотрите на значение a_n по mod 3.

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

Как подсказывает нам прошлый пункт задачи, нужно рассматривать остатки от деления a_n на степени 3. Попробуйте найти таким способом зацикливание.

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

Отлично! Теперь мы знаем, что остатки от деления a_n на 9 и на 27 зацикливаются. Тогда, зная, что степень вхождения 3 в выражение a_(n+1) - a_(n-1) каждый раз растёт, попробуйте вывести рекуррентную формулу для этой степени вхождения.

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

Если v_n - степень вхождения 3 в a_(n+1) - a_(n-1), то v_2 = 1, v_3 = 2, v_(2k+1) = v_2k + 2 и v_(2k+2) = v_(2k+1). Теперь осталось лишь решить неравенство v_k < 2022.

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

Нам нужно определить такое B, чтобы для него нашлось A, такой, что ни один r_k не равен B. Сразу сделать это довольно трудно. Попробуйте для начала подставлять небольшие A и посмотреть на значения полинома.

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

Отлично! Мы знаем, что f(2) = 2. Очень удобно будет доказывать, что есть такое A, что не будет остатка 2, ведь M - квадрат нечётного числа. Осталось лишь подобрать такое A и доказать, что r_k никогда не равен 2. Попробуйте найти A так, чтобы в нём как слагаемое присутствовало q (M = q^2).

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

Можно взять A = 2 + k*q (k и q взаимно просты). Теперь попробуйте рассмотреть f(A) по mod M.

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

Доказать, что это верно для произвольного множество бесконечных чисел, не представляется возможным. Поэтому нужно определить, для каких чисел мы это будем делать. Предыдущие пункты задачи явно подсказывают, что M должна быть степенью какого-то числа. Попробуйте перебирать небольшие числа и посмотреть, является ли стабильным полином по этому модулю.

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

Так, теперь мы знаем, что для 7 многочлен стабилен. Тогда попробуем доказать, что это верно и для 7^k. Легче всего сделать это по индукции. База уже есть, осталось доказать переход. И победа!

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

1. Легко видеть, что остатки $an$ от деления на 3 чередуются с периодом 2 (1, 0, 1, 0, . . .) поэтому период остатков по модулю $M = 32022$ тем более не равен 1.
Покажем что он равен 2.
Заметим, что $an+2 − an =a2n+1− a2n−1+an+1− an−1 = (an+1− an−1)(an+1+ an−1 +1)$
Отсюда следует, что если $an+1 − an−1$ делится на $3k$ , то тем же свойством обладает и $an+2− an$ , а если вдобавок $an+1$ , $an−1$ дают остаток от 1 деления на 3, то $an+2 − an$ делится на $3k+1$ .
Учитывая, что такая ситуация имеет место при каждом четном $n$ , получаем, что соответствующее $k$ может неограниченно увеличиваться, в частности, $an+2− an$ делится на $32022$ при некотором $n= n0$ (а значит и при всех $n >n0$ ). Поэтому период $rn$ равен двум.

2. Выпишем остатки от деления $an$ на 9 и на 27: легко убедиться, что это 2-периодические последовательности $1,3,4,3,4,...$ и $1,3,13,21,13,21,...$ соответственно.
Поэтому число $(an+1+ an−1+ 1)$ не делится на 3 при нечетных $n$ , делится на 3, но не на 9 при $n= 2$ и делится на 9, но не на 27 при четных $n >2$ .
То есть если $v n$ — степень вхождения 3 в число $a − a n+1 n−1$ , то $v = 1 2$ , $v =2 3$ а дальше $v =v + 2 2k+1 2k$ и $v = v 2k+2 2k+1$ .
Отсюда легко видеть, что наибольшее $s$ такое, что $v <2022 s$ равно 2022, то есть $a − a 2023 2021$ — последняя среди разностей вида $an+2− an$ не кратная $M$ .

3. Пусть $M =Q2$ , тогда $Q$ - нечетное число.
Заметим, что $f(2)= 23− 22− 2= 2$ ,значит, достаточно показать, что существует число, проделывая операцию из условия над которым мы не получим 2.
Рассмотрим числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$
$f(t)= (2+ kQ)3 − (2+ kQ )2 − 2= Q3k3+ 5Q2k2+8Qk +2$
Нетрудно заметить, что $f(t)≡ 8Qk + 2(mod M )$
То есть числа вида $t= 2+ kQ$ , где НОД $(k;Q)= 1$ переходят в себя, но число 2 не имеет такого вида, поэтому полином $f = x3− x2 − 2$ нестабилен по модулю $M$ , если $M$ является квадратом нечётного числа.

4. Индукцией по $k$ докажем, что для $M = 7k$ многочлен $x2− 3x+ 12$ стабилен.
Обозначим через $a → b$ , то что $P(a)≡b(modM )$
База $k =1$

0→ 5→ 1 → 31 → 3→ 5→ 12 → 3→ 5→ 13→ 5 → 1→ 34→ 2→ 3→ 5→ 15→ 1 → 36 → 5→ 1→ 3

Таким образом, имеем цикл длины 3 везде одинаковый.
Переход $k→ k+ 1$
Пусть по модулю $M = 7k$ многочлен стабилизируется так, что всегда встретится $r$
Тогда по модулю $M = 7k+1$ остаток $r$ будет $7km+ r= r1$
$P (r1)≡r2− 3r+ 12 +7kn(2r− 3)(Mod 7k+1)$ , что не зависит от $n$ , при $0≡ 2r− 3(Mod 7)$
$0 ≡2r− 3(Mod 7)⇔ 5 ≡r(Mod 7)$ , что бывает по базе индукции, поэтому многочлен стабилизируется и по модулю $7k+1$ .

Ответ:

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

2. 2021

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

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

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

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

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

an+1+1- a1 =1,a12 =2,an+2 = an

для всех натуральных $n= 1,2,...10.$ Найдите $a4.$

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

Подсказка 1

Что нам дано в условии: есть 12 чисел а₁, ...а₁₂, первое и последнее известны, а также есть 10 соотношений, их связывающие (для n от 1 до 10). По сути есть система из 10 уравнений с 10 неизвестными, и нам обещают, что она разрешима единственным образом. Что самое простое и естественное хочется сделать, когда перед нами куча несложных уравнений с кучей неизвестных?

Подсказка 2

Конечно, для упрощения системы хочется начать выражать неизвестные друг через друга! Зачем нам думать о всех 10 неизвестных, если можно уменьшить их количество?

Подсказка 3

Например, а₃ = (а₂+1)/а₁. То есть а₃ = a₂+1, и а₃ дальше в нашей системе уже фигурировать не будет. Попробуйте так же выразить несколько следующих членов последовательности, может, что-нибудь красивое получится!

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

Для краткости обозначим $a 2$ за $x$ и найдём несколько первых членов последовательности при $x ⁄=− 1$ , что, как мы увидим, будет выполнено:

x +2 2x+ 2 2 a1 =1,a2 = x,a3 = x+ 1,a4 =-x-,a5 = x(x+-1) = x,a6 =1,a7 = x

Следовательно, она периодична с периодом 5. В таком случае

a2 = a12 = 2,a3 = 2+-1 =3,a4 = 3+-1= 2 1 2

Ответ: 2

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

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

Дана бесконечная числовая последовательность $a,a ,..., 1 2$ о которой известно следующее: $a = 20,a = a a ,n ∈ℕ. 1 n+1 n n+2$ Найдите все значения, которые может принимать $a2014.$

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

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

Подсказка 1

Формула для n-го элемента содержит предыдущий и последующий, поэтому имеет смысл выразить друг через друга соседние элементы и составить уравнение.

Подсказка 2

Получим, что или произведение членов, стоящих через 2, равно 1, или же произведение рядом стоящих членов равно нулю.

Подсказка 3

Нам известно первое число, поэтому достаточно разобрать два вышеуказанных случая, начиная с первых элементов!

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

Запишем это условие для двух последовательных членов

a = a ⋅a ak+1= ak k⋅+a2 =⇒ 1= ak⋅ak+3 или ak+1 = ak+2 = 0 k+2 k+1 k+3

Подставим во втором случае $k =1,$ тогда $ak ⁄= 0,$ откуда $a2 = a3 = 0,$ далее можно подставить $k= 3 =⇒ a4 = 0$ и так далее по индукции. В итоге возможно $a2014 =0.$ В первом случае $a4 = 1-=-1. a1 20$ Перейдём от $a1$ к $a4,$ действуем аналогично, теперь либо $a5 = a6 = ...= 0,$ либо $a7 = 1-. a4$ Совершая такие переходы, приходим к другому возможному значению $a2014 = a1+3⋅671 =-1 = 1. a1 20$ Остальные значения невозможны.

Ответ:

$0, 1 20$

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

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