Izho 2022 , задача 5

[rightways]

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

$$f(n+1)+f(n+2)+…+f(n+k)$$

с натуральными $n,k$.

[worm2]

Идея-то понятна: на больших интервалах тупо слишком редко попадаются числа, представимые в таком виде.
На примере многочлена $f(x)=ax^2$ (понятно, что чем выше степень многочлена, тем хуже).

$$f(n+1)+f(n+2)+…+f(n+k)=\frac{a}{6}((n+k)(n+k+1)(2n+2k+1)-n(n+1)(2n+1))$$

В диапазон $[N^3..(N+1)^3]$ попадает, как показывают численные эксперименты, $O(N)$ чисел, что меньше количества чисел в этом интервале: $O(N^2)$.
Значит, идея работает. Но как бы всё это строго обосновать... Интегралы надо оценивать, а лень.

[nnosipov]

Еще одна идея: попробовать доказать, что в указанном виде непредставимы все достаточно большие простые числа. Дело в том, что сумма $f(n+1)+\ldots+f(n+k)$ как многочлен от $n$ и $k$ всегда делится на $k$.

[TOTAL]

Степень полинома равна $s$. Если предположить, что все натуральные числа больше $M$ представимы указанными суммами, то отношение $f(n)$ к количеству сумм с ростом $n$ стремится максимум к единице. Однако количество сумм из одного слагаемого, которые не превосходят $f(n)$, равно $n$. Из двух слагаемых - $\displaystyle n/\sqrt[s]{2}$. И так далее.

$$n\left(\frac{1}{\sqrt[s]{1}}+\frac{1}{\sqrt[s]{2}}+ \dots + \frac{1}{\sqrt[s]{n}}\right) = \alpha n^{2-1/s} < \beta n^{s} $$

Таким образом, сумм не хватит.