XVIII математическая олимпиада «Шелковый путь», 2019 год

Последовательность $\{a_n\}$ определена следующим образом: $a_0=1$ и ${a_n} = \sum\limits_{k = 1}^{[\sqrt n ]} {{a_{n - {k^2}}}}$ для $n \ge 1.$ Докажите, что среди $a_1,a_2,\ldots,a_{10^6}$ есть хотя бы 500 четных чисел. (Здесь $[x]$ обозначает наибольшее целое, не превосходящее $x$.) ( Д. Елиусизов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Разобьем решения на три части.
Часть 1. Пусть $m = [\sqrt{n}]$. Заметим, что если $m$ четно, то количество слагаемых в сумме $$a_n + a_{n-1^2} + a_{n-2^2} + \cdots + a_{n - m^2} \equiv 0 \pmod{2},$$ нечетно. Тогда хотя бы одно из чисел $a_n, a_{n-1^2}, a_{n-2^2}, \ldots, a_{n - m^2}$ будет четным.
Часть 2. Число $n$ для которого $m = [\sqrt{n}]$ является четным назовем {\it хорошим}. Посчитаем количество хороших чисел $1 \le n \le 10^6$. Число хорошее если $(2k)^2 \le n < (2k+1)^2$ для полных промежутков длины $(4k+1)$ при $1 \le k \le 499$ и также $n = 10^6$. Тогда общее количество хороших чисел равно $$1 + \sum_{k = 1}^{499} (4k + 1) = 499500.$$
Часть 3. Итак, для каждого хорошего числа $n$, хотя бы одно из чисел $a_{n-k^2}$ является четным, где $0 \le k \le [\sqrt{n}]$. Для каждого хорошего числа $1 \le n \le 10^6$ отметим такое (одно) четное $a_{n-k^2}$, сделав при этом 499500 отметок. Тогда заметим, что для каждого фиксированного $m$, (четное) число $a_m$ в этом процессе могло быть отмечено не более 1001 раз, т.к. $m = n - k^2$ может иметь разные решения $(n,k)$ для $0\le k\le 10^3$ (при каждом $k$, число $n$ определяется однозначно). Это означает, что есть хотя бы $499500/1001 > 499$ четных чисел среди $a_n$ для $1 \le n \le 10^6$.
Замечание 1. Среди чисел ${{a}_{1}},{{a}_{2}},\ldots ,{{a}_{688}}$ есть ровно 500 четных чисел.
Замечание 2. Среди чисел ${{a}_{1}},{{a}_{2}},\ldots ,{{a}_{^{{{10}^{6}}}}}$ есть ровно 849445 четных чисел.

Определите $a_n=0$для всех $n<0$. Легко видеть, что $a_n$подсчитывает количество последовательностей натуральных чисел $(b_1,b_2,...,b_k)$таких, что $b_1^2+b_2^2+...+b_k^2=n$. Для каждого $n\geq0$обозначим множество $S_n$всех таких последовательностей.

Мы определяем инволюцию $f_n:S_n \to S_n$как $f_n(b_1,b_2,...,b_k)=(b_k,b_{k-1},...,b_1)$. Поскольку $f_n$является инволюцией, число неподвижных точек $f_n$имеет ту же четность, что и $|S_n|$. Рассмотрим фиксированную $(b_1,b_2,...,b_k)$точку $f_{2n}$. Если $к$четно, скажем $k=2l$, то $b_1^2+b_2^2+...+b_l^2=n$. Есть $a_n$такие последовательности. Если $к$, скажем, нечетно $k=2l+1$, то $2(b_1^2+b_2^2+...+b_l^2)+b_{l+1}^2=2n$. Примечание $b_{l+1}$должно быть четным, поэтому пусть $b_{l+1}=2c$. Затем $b_1^2+b_2^2+...+b_l^2=n-2c^2$. Для каждого $с>0$существуют такие $a_{n-2c^2}$последовательности. Следовательно, $$a_{2n}\equiv a_n+\sum_{c=1}^\infty a_{n-2c^2} \text{ }(\text{mod } 2)$$ Предположим $n$, что это не идеальный квадрат (поэтому каждая последовательность в $S_n$имеет как минимум два члена). Определить $g_n:S_n \to S_n$как $g_n(b_1,b_2,...,b_k)=(b_2,b_1,b_3,b_4,...,b_k)$. Аналогичным образом мы хотим подсчитать количество неподвижных точек $g_n$. Фиксированная точка возникает, когда $b_1=b_2=c$для некоторого $с>0$. Затем $b_3^2+b_4^2+...+b_k^2=n-2c^2$. Есть $a_{n-2c^2}$такие последовательности. Следовательно, $$a_n\equiv\sum_{c=1}^\infty a_{n-2c^2} \text{ }(\text{mod } 2)$$ если сложить два уравнения вместе, если $n$квадрат не является точным, $$a_{2n}\equiv 2\sum_{c=1}^\infty a_{n-2c^2} \equiv 0 \text{ }(\text{mod } 2)$$ это, очевидно, дает больше, чем $500$четные числа в $a_1,a_2,...,a_{10^6}$. $\Box$