|
|
 |
Условие
В бесконечной последовательности a1, a2, a3, ... число a1 равно 1,
а каждое следующее число an строится из предыдущего an–1 по правилу: если у числа n наибольший нечётный делитель имеет остаток 1 от деления на 4, то an = an–1 + 1, если же остаток равен 3, то an = an–1 – 1. Докажите, что в этой последовательности
а) число 1 встречается бесконечно много раз;
б) каждое натуральное число встречается бесконечно много раз.
(Вот первые члены этой последовательности: 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, ...)
Решение
а) Пусть an = an–1 + bn. Тогда an = 1 + b2 + ... + bn. Заметим, что b2n = bn. Отсюда
a4n = 1 + b2 + ... + b4n = b2 + b4 + ... + b4n + (1 + b3) + (b5 + b7) + ... + (b4n–3 + b4n–1) = 1 + b2 + b3 + ... + b2n = a2n (выражения в скобках равны нулю).
Поэтому a2n = a2 = 2, следовательно, a2n–1 = 1.
б) Согласно а) a16n+4 = a8n+2 = a8n+1 + 1 = a8n + 2 = a4n + 2. Это значит, что члены с индексами, кратными 4, могут быть сколь угодно большими.
Теперь утверждение задачи следует из п. а) и дискретной непрерывности.
Замечания
1. Нетрудно доказать по индукции (см. решения Задачника "Кванта" задача М2119), что an равно количеству групп нулей и единиц в двоичной записи числа n. Например, если n2 = 1110011001 – 3 группы единиц и 2 группы нулей, то an = 5.
2. В варианте 10-11 классов предлагался только п. б).
3. Баллы: 8-9 кл. – 5 + 5, 10 кл. – 8.
