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 2 of 5: Linear P works: find a block summing to d mod c

Previous step Next step

s_i\equiv s_j \pmod c,\ i<j \implies a_{i+1}+\cdots+a_j\equiv 0\pmod c

Detailed analysis

Let $P(x)=cx+d$ , $c\ne0$ , and set $s_0=0$ , $s_i=a_1+\cdots+a_i$ . A block sum $a_i+\cdots+a_j=s_j-s_{i-1}$ equals $P(k)=ck+d$ for some integer $k$ exactly when $s_j-s_{i-1}\equiv d\pmod c$ . Since every integer occurs exactly once, infinitely many positions $e$ have $a_e\equiv d\pmod{|c|}$ ; pick $|c|+1$ of them, $e_1<\cdots<e_{|c|+1}$ . As $a_{e_l}\equiv d\pmod c$ , the value $s_{e_l}\bmod c$ is determined by $s_{e_l-1}\bmod c$ , which takes only $|c|$ possible values; by pigeonhole two indices $p<q$ have $s_{e_p-1}\equiv s_{e_q-1}\pmod c$ .