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

Дан многочлен $f(x)$ с вещественными коэффициентами степени выше 1. Докажите, что существует бесконечно много натуральных чисел, не представимых в виде $$f(n+1)+\dots+f(n+k)$$ с натуральными $n$ и $k$. ( А. Голованов )

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

Начнем с того, что если $f$ имеет отрицательный старший коэффициент, то с какого то значения принимает только отрицательные значения и если $S$ - сумма всех положительных значений многочлена, то мы никак не сможем представить значения $>S$, поэтому непредставимых бесконечно

Пусть теперь старший коэффициент положителен, тогда очевидно, что с какого то значения многочлен будет возрастать и будет положителен. Пусть $C$ - такое натуральное число, с которого все натуральные числа представимы. Рассмотрим числа от $C$ до $f(Сx+1)-1$ для какого то большого числа $x$. Каждому числу сопоставим из этого промежутка сопоставим пару $(z,t)$, где $t\geq z$, которая будет означать, что это число равно сумме $f(z)+\dots+f(t)$, тогда второе число в паре никак не превосходит $Cx$, так как можно выбрать $x$ такой, что $f(Cx)>-S$, где $S$ - сумма всех возможных отрицательных значений $f$, тогда $f(Cx)$ и $f(Cx+1)$ не могут одновременно присутствовать в представлении, а наличие только чисел $\geq f(Cx+1)$ также приводит к противоречию. Поэтому во всех рассматриваемых представлениях $t \leq Cx$. Количество таких пар тогда равно $\frac{Cx(Cx+1)}{2}$, так как разным числам соответствуют разные пары, то мы можем сказать, что $f(Cx+1)-C \leq \frac{Cx(Cx+1)}{2}$, так как это верно при достаточно больших $x$, то $deg$ $f\leq 2$ Теперь рассмотрим многочлен $f(x)+f(x+1)+\dots+f(x+C^2)-f(Cx+1)$. Его старший коэффициент равен $(C^2+1)a-C^2a=a>0$, где $a$ - старший коэффициент $f$, поэтому рассмотрим большой $x$, при котором этот многочлен $>-S$, тогда если в паре $(z,t)$, $z\geq x$, то для $t$ будет $\leq C^2$ вариантов. Откуда получаем, что общее число пар, которые могут присутствовать в представлениях будет $\leq \frac{x(x-1)}{2} + (Cx-x+1)C^2$, что должно быть $\geq f(Cx+1)-C$, и так как это верно при достаточно больших $x$, то $aC^2\leq \frac{1}{2}$, но мы могли выбрать C любым и так как $a>0$, то противоречие