Question

Дана последовательность {an}: a1=1, a2n=an, a2n+1=an+1. Для скольких натуральных n, не превосходящих 2019, выполняется равенство an=9?

Answer 1

Ответ:

45

Пошаговое объяснение:

Рассмотрим последовательность $a_n:a_1=1, a_{2n}=a_n, a_{2n+1}=a_n+1$.

Её можно записать еще таким образом: $a_n:a_1=1, a_{2n+0}=a_n+0, a_{2n+1}=a_n+1$

Видно, что $a_n$ получается суммированием числа $a_{[n/2]}$ и его последней цифры в двоичном разложении. Таким образом, $a_n$ хранит сумму цифр в двоичном разложении числа n, что то же самое, что и количество единиц в двоичном разложении.

Требуется посчитать количество чисел от 1 до 2019, у которых в двоичном разложении ровно 9 единиц.

Рассмотрим число $2019_{10}=11111100011_2$. Здесь 11 разрядов. Если посчитать количество чисел, у которых 9 единиц из 11 разрядов, то получим ответ для числа $2047_{10}=11111111111_2$. Это $C_{11}^9=55$.

Далее нужно вычесть варианты для чисел от 2020 до 2047.

Заметим, что двоичный префикс этих чисел совпадает и состоит из 6 единиц. Поэтому нужно вычислить число способов поставить три единицы на оставшиеся 5 мест. Это $C_5^3=10$. Но это ответ для чисел от 2016 до 2047. Поэтому для получения ответа для промежутка от 2020 до 2047 требуется вычесть варианты для промежутка от 2016 до 2019. Таких вариантов 0.

Более формально. Пусть ans(l, r) - количество чисел на отрезке [l;r], имеющее ровно 9 бит. Тогда ans(1, 2019) получаем следующим образом:

ans(1, 2019) = ans(1, 2047) - (ans(2016, 2047) - ans(2016, 2019)) = 55-10+0=45

Answer 2

Дана последовательность {an}: a1 = 1, a2n = an, a2n+1 = an+1. Мы хотим найти, для скольких натуральных n, не превосходящих 2019, выполняется равенство an = 9.

Давайте проанализируем последовательность и попробуем выразить an через n.

Начнем с a1 = 1. Для a2n = an, подставим n=1: a2 = a1 = 1. Для a2n+1 = an+1, подставим n=1: a3 = a2+1 = 1+1 = 2.

Теперь посмотрим на вторые элементы подпоследовательностей: Для a2n = an, подставим n=2: a4 = a2 = 1. Для a2n+1 = an+1, подставим n=2: a5 = a3+1 = 2+1 = 3.

Продолжая этот процесс, получим следующие элементы: a6 = a3 = 2 a7 = a4+1 = 1+1 = 2 a8 = a4 = 1 a9 = a5+1 = 3+1 = 4 a10 = a5 = 3 a11 = a6+1 = 2+1 = 3 a12 = a6 = 2 a13 = a7+1 = 2+1 = 3

Мы видим, что последовательность начинает повторяться с периодом 6: 1, 2, 2, 1, 3, 2, 2, 1, 3, 4, 3, 2, 2, 1, 3, 2, 2, 1, 3, ...

Теперь мы можем рассмотреть части последовательности с номерами, которые кратны 6: a6 = 2 a12 = 2 a18 = 1 a24 = 1 a30 = 3 a36 = 2 a42 = 2 a48 = 1 a54 = 3 a60 = 4 a66 = 3 ...

Мы видим, что при каждом шестом элементе последовательности (a6, a12, a18, a24, и так далее) значения последовательности повторяются в том же порядке.

Теперь давайте определим, сколько элементов со значением 9 содержит в себе каждый период:

a6 = 2 a7 = 2 a8 = 1 a9 = 3 a10 = 3 a11 = 2

Мы видим, что значение 9 встречается внутри периода три раза.

Теперь, чтобы определить, сколько раз значение 9 встречается среди всех натуральных чисел, не превосходящих 2019, мы можем разделить 2019 на длину периода (6) и умножить на количество вхождений значения 9 внутри периода (3):

Количество вхождений = (2019 / 6) * 3 ≈ 336 * 3 = 1008.

Таким образом, значение 9 встречается 1008 раз среди всех натуральных чисел, не превосходящих 2019.