Problem 2

For a polynomial

P

and a positive integer

n

, define

P_n

as the number of positive integer pairs

(a,b)

such that

a<b\le n

and

|P(a)|-|P(b)|

is divisible by

n

. Determine all polynomials

P

with integer coefficients such that

P_n\le2021

for all positive integers

n

Step 3 of 6: P must be linear

Previous step Next step

\deg P=1

Detailed analysis

A constant $P$ fails immediately since then $P_n=\binom n2\to\infty$ . If $\deg P\ge2$ , then $P(k)-P(1)\ge k$ for some large $k$ ; taking $n=P(k)-P(1)\ge k$ , the values $P(1)$ and $P(k)$ (both among $P(1),\ldots,P(n)$ since $k\le n$ ) satisfy $P(k)-P(1)=n\equiv0\pmod n$ , contradicting the lemma. Hence $\deg P=1$ .