Математика
Русский язык

19. Задачи на теорию чисел

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

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

Задание 1
Уровень задания: Легче ЕГЭ

Илья выписал последовательность остатков от деления последовательно идущих натуральных чисел на 3 (начиная с некоторого числа). Верно ли, что начиная с некоторого номера \(N\), члены последовательности повторяются периодически c некоторым периодом \(T > 0\) (т.е. при любых \(k\in\mathbb{N}\) выполнено равенство \(a_{N + k} = a_{N + k + T}\))?

Добавить задание в избранное

Любое \(a\in\mathbb{N}\) имеет такой же остаток от деления на 3, что и \(a + 3t\), где \(t\in\mathbb{N}\) – произвольное.

Так как различных остатков от деления на 3 может быть не больше 3, то фрагмент последовательности, в котором нет одинаковых чисел, имеет длину не больше 3: \(b_1, b_2, b_3\), но тогда \(b_4 = b_1\), \(b_5 = b_2\), \(b_6 = b_3\) и т.д., то есть члены выписанной Ильёй последовательности, начиная с некоторого номера, повторяются периодически.

Ответ:

Да

Задание 2
Уровень задания: Равен ЕГЭ

Тимур придумал бесконечную последовательность действительных чисел, в которой первые 10 членов натуральные числа, а каждый член, начиная с третьего, равен остатку от деления предпредыдущего члена на предыдущий член, либо \(0\) (то есть, например, \(a_3\) равен остатку от деления \(a_1\) на \(a_2\), либо \(a_3 = 0\)).

а) Приведите пример такой последовательности.

б) Назовём периодом последовательности наименьшее натуральное число \(T\), такое что, начиная с некоторого номера \(N\), для любого \(k\in\mathbb{N}\cup\{0\}\) выполняется \(a_{N + k} = a_{N + k + T}\). Найдите период последовательности Тимура.

Добавить задание в избранное

а) Будем искать такую последовательность в виде \[A, A + B, A, B, A - B, 2B - A, 2A - 3B, 5B - 3A, 5A - 8B, 13B - 8A, ...\] (каждый последующий член равен разности двух предыдущих). Чтобы такая последовательность подходила под условие, необходимо и достаточно, чтобы

\[\begin{cases} A > B > A - B > 2B - A > 2A - 3B > 5B - 3A > 5A - 8B > 13B - 8A > 0\\ A, B\in\mathbb{N}. \end{cases}\]

Данная система эквивалентна системе

\[\begin{cases} \dfrac{21}{13}B < A < \dfrac{13}{8}B\\ A, B\in\mathbb{N}. \end{cases} \qquad\Leftrightarrow\qquad \begin{cases} \dfrac{336}{208}B < A < \dfrac{338}{208}B\\ A, B\in\mathbb{N}. \end{cases}\]

Таким образом, можно взять, например, \(A = 337\), \(B = 208\). При этом получим последовательность

\[337, 545, 337, 208, 129, 79, 50, 29, 21, 8, ...\]

б) Если какой-то из членов последовательности равен \(0\), то, начиная с него, все члены последовательности равны \(0\) (так как результат деления на \(0\) не может совпасть ни с каким действительным числом).

Пусть никакой из членов последовательности не равен \(0\).

 

1) Пусть \(a_1 > a_2\). Так как остаток от деления не может быть больше делителя, то \(a_2 > a_3 > a_4 > ...\), то есть последовательность убывает.

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

Тогда член последовательности с номером \(N = a_1\) должен быть натуральным числом, меньшим, чем \(a_1\) по крайней мере на \(N = a_1\), что невозможно.

 

2) Пусть \(a_2 > a_1\), тогда \(a_3 = a_1\) и этот пункт сводится к пункту 1) при помощи смены обозначений \(a_2 = b_1\), \(a_3 = b_2\), ..., \(a_{n + 1} = b_n\) и дословного повторения рассуждения для последовательности \(b_1, ..., b_n, ...\).

Таким образом, последовательностей, подходящих под условие, у которых никакой из членов не равен \(0\), не бывает. Тогда, начиная с некоторого номера, все члены последовательности Тимура равны \(0\) и, значит, \(T = 1\).

Ответ:

а) \(337, 545, 337, 208, 129, 79, 50, 29, 21, 8, ...\)

б) \(1\)

Задание 3
Уровень задания: Сложнее ЕГЭ

Верно ли, что при любом \(k > 0\) последовательность \(a_n = \sqrt{n + k}\) не убывает?

Добавить задание в избранное

Зафиксируем произвольное \(k > 0\).

Рассмотрим функцию \(f(x) = \sqrt{x + k}\) при \(x > 0\).

При \(x > 0\): \[f'(x) = \dfrac{1}{2\sqrt{x + k}} > 0.\] Таким образом, функция \(f\) возрастает на \((0; +\infty)\), тогда \(f(n + 1) > f(n)\) – при всяком \(n\in\mathbb{N}\), то есть последовательность \(a_n\) возрастает, а следовательно, она не убывает.

Ответ:

Да

Задание 4
Уровень задания: Сложнее ЕГЭ

Верно ли, что при любом \(k > 0\) последовательность \(a_n = \sqrt{n + k} - \sqrt{n}\) убывает?

Добавить задание в избранное

Зафиксируем произвольное \(k > 0\).

Рассмотрим функцию \(f(x) = \sqrt{x + k} - \sqrt{x}\) при \(x > 0\).

При \(x > 0\): \[f'(x) = \dfrac{1}{2\sqrt{x + k}} - \dfrac{1}{2\sqrt{x}} = \dfrac{\sqrt{x} - \sqrt{x + k}}{2\sqrt{x + k}\sqrt{x}}.\]

Так как \(0 < x < x + k\), то \(\sqrt{x} < \sqrt{x + k}\), следовательно, \(f'(x) < 0\) при \(x > 0\), то есть функция \(f\) убывает на \((0; +\infty)\), тогда \(f(n + 1) < f(n)\) – при всяком \(n\in\mathbb{N}\), то есть последовательность \(a_n\) убывает.

Ответ:

Да

Задание 5
Уровень задания: Сложнее ЕГЭ

Илья придумал бесконечную последовательность натуральных чисел, в которой каждый член, начиная с сотого, равен последней цифре квадрата предыдущего члена (в десятичной записи). Можно ли с уверенностью утверждать, что, начиная с некоторого номера \(N\), члены этой последовательности повторяются периодически c некоторым периодом \(T > 0\) (т.е. при любых \(k\in\mathbb{N}\) выполнено равенство \(a_{N + k} = a_{N + k + T}\))?

Добавить задание в избранное

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

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

Начиная с сотого члена, каждый член последовательности совпадает либо с 0, либо с 1, ..., либо с 9.

Так как последовательность бесконечная, то найдётся член этой последовательности, который повторяется бесконечное число раз. Таким образом, последовательность Ильи периодична.

Ответ:

Да

Задание 6
Уровень задания: Сложнее ЕГЭ

Максим придумал бесконечную последовательность натуральных чисел, в которой каждый член, начиная с третьего, равен последней цифре суммы двух предыдущих членов (в десятичной записи). Можно ли с уверенностью утверждать, что, начиная с некоторого номера \(N\), члены этой последовательности повторяются периодически c некоторым периодом \(T > 0\) (т.е. при любых \(k\in\mathbb{N}\) выполнено равенство \(a_{N + k} = a_{N + k + T}\))?

Добавить задание в избранное

Заметим, что каждый член последовательности, начиная с третьего, однозначно определяется ровно двумя предыдущими членами последовательности, следовательно, если в данной последовательности дважды встречается фрагмент \(a, b\), то есть она имеет вид \(a_1..., a, b, ..., a, b, ...\), то она периодическая.

Остаётся показать, что некоторый фрагмент такого вида действительно встретится в последовательности Максима не менее двух раз.

Начиная с третьего члена, каждый член последовательности совпадает либо с 0, либо с 1, ..., либо с 9.

Так как последовательность бесконечная, то найдётся член этой последовательности, который повторяется бесконечное число раз.

Пусть \(0\) повторяется бесконечное число раз. Тогда следующие после \(0\) члены не могут быть всё время разными (их разных – конечное количество, а \(0\) встречается бесконечно много раз).

В итоге следующие после \(0\) члены также хотя бы раз совпадут, и фрагмент вида \(0, b\) действительно встретится в последовательности хотя бы дважды.

Если другое число повторяется бесконечное число раз, то рассуждения в этом случае аналогичны предыдущим.

Таким образом, последовательность Максима периодична.

Ответ:

Да

Задание 7
Уровень задания: Сложнее ЕГЭ

Иван придумал функцию \(f(x)\), область определения которой \(\mathbb{R}\), а область значений – конечное подмножество \(\mathbb{R}\).

Настя придумала бесконечную последовательность, в которой каждый член, начиная с пятого, имеет вид \[a_n = f(f(f(a_{n - 4}) + a_{n - 3}) - a_{n - 1}).\] Можно ли с уверенностью утверждать, что начиная с некоторого номера \(N\) члены этой последовательности повторяются периодически c некоторым периодом \(T > 0\) (т.е. при любых \(k\in\mathbb{N}\) выполнено равенство \(a_{N + k} = a_{N + k + T}\))?

Добавить задание в избранное

Заметим, что каждый член последовательности, начиная с пятого, однозначно определяется предыдущими четырьмя членами, следовательно, если в данной последовательности дважды встречается фрагмент \(a, b, c, d\), то есть она имеет вид \(a_1..., a, b, c, d, ..., a, b, c, d, ...\), то она периодическая.

Остаётся показать, что некоторый фрагмент такого вида действительно встретится в последовательности Насти не менее двух раз.

Так как область значений \(f(x)\) – конечное множество, то в этом множестве найдётся элемент, который встречается в последовательности бесконечное число раз. Обозначим этот элемент через \(a\).

Так как \(a\) встречается бесконечное число раз, а претендентов на роль правого соседа \(a\) лишь конечное число, то найдётся число \(b\), такое, что фрагмент \(a, b\) встречается в последовательности бесконечное число раз.

Так как фрагмент \(a, b\) встречается бесконечное число раз, а претендентов на роль правого соседа фрагмента \(a, b\) лишь конечное число, то найдётся число \(c\), такое, что фрагмент \(a, b, c\) встречается в последовательности бесконечное число раз.

Аналогично, найдётся число \(d\) такое, что фрагмент \(a, b, c, d\) встречается в последовательности бесконечное число раз, следовательно, Настина последовательность периодична.

Ответ:

Да