Problem 4

Let

\mathbb{Z}

denote the set of all integers. Find all polynomials

P(x)

with integer coefficients that satisfy the following property: for any infinite sequence

a_1,a_2,\ldots

of integers in which each integer in

\mathbb{Z}

appears exactly once, there exist indices

i<j

and an integer

k

such that

a_i+a_{i+1}+\cdots+a_j=P(k)

Step 4 of 5: Bounded polynomials fail

Previous step Next step

a_{3u+1}=2u,\quad a_{3u+2}=2u+1,\quad a_{3u+3}=-(u+1)\ (u\ge0);\qquad \sum_{\ell=i}^{j}a_\ell\ge0\ \text{for }i<j

Detailed analysis

The displayed sequence is a permutation of all integers, and a direct check of the three possible endpoint positions shows that every sum of at least two consecutive terms is nonnegative. If the range of P is bounded above, choose a positive integer C above that bound and add C to every term. Every block then has at least two terms, so its sum is greater than C and avoids the range of P. If the range is bounded below, subtract C from every term instead; every block sum is below the lower bound. Translation preserves the bijection with the integers, so constant and even-degree polynomials fail.