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