19-я Международная Жаутыковская олимпиада по математике, 2023 год

Даны натуральные числа $a_1$, $a_2$, $\dots$, $a_k$. Обозначим через $S(n)$ количество решений уравнения $a_1x_1+\dots+a_kx_k=n$ в целых неотрицательных числах $x_1$, $x_2$, $\ldots$, $x_k$. Известно, что $S(n)\ne 0$ для всех достаточно больших $n$. Докажите, что $S(n+1)<2S(n)$ для всех достаточно больших $n$. ( А. Голованов )

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

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

Будем обозначать, что функция $f(x)$ является $O(g(x))$, если $\exists c > 0$, что $|f(n)|<cg(x)$ для всех достаточно больших $x$. Из того, что сумма модулей хотя бы модуль суммы можно получить, что сумма $t$ $O(g(x))$ функций будет являться $O(tg(x))$ ($t$ может зависеть от $x$, но если $t$ - константа, то можно сказать, что сумма будет также просто $O(g(x))$). Также нам понадобится тот факт, что любой многочлен степени $d$ будет являться $O(x^d)$.

Обобщение задачи. Если $(a_1, a_2, \ldots, a_k) = d$, то $S(n) = \frac{d}{(k-1)!a_1a_2\ldots a_k}n^{k-1} + f(n)$ для всех $d|n$, где $f(n)$ это $O(n^{k-2})$

Достаточно доказать требуемое утверждение для взаимнопростых $a_i$, иначе заменим $a_i=da_i'$ и $n=dn'$, тогда задача сведется к случаю взаимнопростых. Будем доказывать требуемое утверждение индукцией по $k$.

Для $k=2$: Так как $(a_1, a_2) = 1$, то остаток $x_1$ $(mod\text{ }a_2)$ фиксирован и равен $r$, причем для любого числа с таким остаток будет существовать $a_2$, если $a_1x_1\leq n$ , тогда количество решений будет $t+1$, где $t$ - максимальное натуральное число удовлетворяющее неравенству $a_1(r+a_2t) \leq n$. Несложно проверить, что требуемое количество будет равно либо $\lfloor \frac{n}{a_1a_2} \rfloor$ или $\lfloor \frac{n}{a_1a_2} \rfloor +1$, что как раз таки равно $\frac{n}{a_1a_2} + c$, где $c$ зависит только от остатка $n$ $(mod\text{ }a_1a_2)$, то есть является $O(1)$.

Теперь рассмотрим $a_1x_1+\dots+a_kx_k=n$. Пусть $(a_2, a_3, \ldots, a_k) = d$, тогда $(a_1, d) = 1$. Пусть $S_1(n)$ - количество решений уравнения $a_2x_2+\dots+a_kx_k=n$, тогда $S_1(n) = \frac{d}{(k-2)!a_2\ldots a_k}n^{k-2} + f_1(n)$ для всех $d|n$, где $f_1(n)$ это $O(n^{k-3})$. Пусть $a_2x_2+\dots+a_kx_k=ds$, где остаток $s$ $(mod\text{ }a_1)$ опять фиксирован и равен $r$. Каждому решению $(x_2, \ldots, x_k)$ этого уравнения, где $ds\leq n$ соответствует решение $(x_1, x_2, \ldots, x_k)$ изначального уравнения, тогда $S(n) = S_1(dr)+S_1(d(r+a_1))+\ldots+S_1(d(r+a_1t))$, где $t = \lfloor \frac{n}{a_1d} \rfloor -1$ или $\lfloor \frac{n}{a_1d} \rfloor$, но в любом случае $t = \frac{n}{a_1d} + c$, где $|c|$ ограничен константой, откуда мы также можем получить, что $t$, как функция от $n$, будет $O(n)$.

Теперь мы можем раскрыть $S(n)$ из предположения индукции: $S(n) = \frac{d^{k-1}}{(k-2)!a_2\ldots a_k}(r^{k-2} + (r+a_1)^{k-2} + \ldots + (r+a_1t)^{k-2}) + f_1(dr)+f_1(d(r+a_1))+\ldots+f_1(d(r+a_1t))$. Так как каждое из $f_1$ это $O(n^{k-3})$, то сумма $t+1$ таких слагаемых будет $O((t+1)n^{k-3})$, откуда оно также является $O(n^{k-2})$. Теперь осталось разобраться с суммой $k-2$-ых степеней. Для этого воспользуемся следующим фактом - cумма $T_n(x) = 1^n+2^n+\ldots+x^n$ является многочленом степени $n+1$ со старшим коэффициентом $\frac{1}{n+1}$. Тогда, если раскрыть каждую из скобок по биному Ньютона, то выйдут суммы $b_iT_i(t)$ для $0 \leq i \leq k-2$, где $b_i$ - фиксированные числа, которые зависят только от остатка $r$, тогда сумма $\sum_{i=0}^{i=k-3}b_iT_i(t)$ будет равна многочлену степени $k-2$, коэффициенты которого зависят только от $r$, а всего вариантов выбора $r$ будет $a_1$, поэтому, так как каждый из этих многочленов $O(n^{k-2})$, то и в общем для всех $n$, мы можем сказать, что эта сумма будет $O(n^{k-2})$. Теперь посмотрим на $\frac{d^{k-1}}{(k-2)!a_2\ldots a_k}a_1^{k-2}(1^{k-2} + \ldots + t^{k-2})$. Это многочлен от $t$, часть степени меньше $k-1$ которого будет являться $O(t^{k-2})$, но так как $t$ это $O(n)$, то это будет $O(n^{k-2})$. Теперь к оставшемуся члену степени $k-1$, он равен $\frac{d^{k-1}}{(k-1)!a_2\ldots a_k}a_1^{k-2}t^{k-1}$. Теперь вспомним, что $t = \frac{n}{a_1d} + c$ для конечного числа возможных $c$, но для каждого из них $t^{k-1}$ равно $\frac{n^{k-1}}{a_1^{k-1}d^{k-1}} + O(n^{k-2})$, но тогда мы можем сказать это для всех $n$ вне зависимости от их $c$. Теперь $\frac{d^{k-1}}{(k-1)!a_2\ldots a_k}a_1^{k-2}t^{k-1} = \frac{d}{(k-1)!a_1a_2\ldots a_k}n^{k-1} + O(n^{k-2})$, тогда в общем $S(n) = \frac{d}{(k-1)!a_1a_2\ldots a_k}n^{k-1} + O(n^{k-2}) + O(n^{k-2}) + O(n^{k-2}) + O(n^{k-2})$, но мы можем сложить все $O(n^{k-2})$ в один, так как их всего $4$, откуда получим требуемое.

Теперь задача следует напрямую. Из условия $S(n) > 0$ для всех достаточно больших $n$ следует, что $(a_1, a_2, \ldots, a_k) = 1$. Теперь $S(n+1) - S(n) - f(n) = \frac{1}{(k-1)!a_1a_2\ldots a_k}((n+1)^{k-1}-n^{k-1}) + f(n+1) - 2f(n)$. Все $3$ членa последней суммы являются $O(n^{k-2})$, откуда она в общем $O(n^{k-2})$. Но тогда $S(n+1) - S(n) - f(n)$ меньше, чем $\frac{1}{(k-1)!a_1a_2\ldots a_k}n^{k-1}$ для всех достаточно больших $n$, откуда и следует, что $S(n+1) < 2S(n)$ для всех достаточно больших $n$.

Рассмотрим $f(x)=\sum_{m=0}^\infty S(m)x^m$ - степенной ряд для $S(n)$. Заметим, что из условия мы получаем

$$f(x)=\prod_{m=1}^k \frac{1}{1-x^{a_m}}$$

Пусть, $x_1,x_2,\dots$ - все различные комплексные корни у знаменателей этих дробей, $x_1=1$,а $\alpha_1,\alpha_2,\dots$ - соответствующие суммарные кратности этих корней. Заметим, что $\alpha_1=k$, а все остальные строго меньше $k$, ведь иначе все $a_i$ делятся на одно и то же натуральное число, значит взяв $n$ не делящееся на это число, $S(n)=0$. Но таких $n$ бесконечно много, что противоречит условию. Значит, для каких-то многочленов $P_1,P_2,\dots$с комплексными коэффициентами:

$$f(x)= \sum_{m} \frac{P_m(x)}{(1-x_m)^{\alpha_m}}$$

Но тогда расписав степенные ряды отдельно для каждого слагаемого, получаем, что для каких-то многочленов $Q_1,Q_2,\dots$ с комплексными коэффициентами и степенями $\alpha_1,\alpha_2,\dots$ соответственно:

$$S(n)=\sum_{m} Q_m(n) x_m^n$$

Поскольку все $x_m$ по модулю равны $1$, то модуль правой части ограничивается сверху и снизу модулями двух многочленов $R_1,R_2$ с степенью и старшим коэффициентом как и у $Q_1$. Но тогда многочлен $2R_2(n)-R_1(n+1)<2S(n)-S(n+1)$ имеет положительный старший коэффициент, значит с какого-то момента он всегда положительный, значит с какого-то момента $S(n+1)<2S(n)$.

Сообразить не могу, какая область сходимости у ряда?