Does this work ? Answer. $P(x)=x+c$ for constant $c$. Claim. If $P$ is linear with a leading coefficient other than $1$, $P_n$ can get arbitrarily large. Proof. Let $P(x)=dx+c$ with $d\neq 1$ then $P(a)-P(b)=d(a-b)$ and choosing a large multiple $n$ of $d$ $$n\mid d(a-b)\leftrightarrow (n/d)\mid a-b$$and $1\le a-b\le n-1$, in particular we can find ordered pairs $(a, b)$ such that $a-b=n/d\leftrightarrow a=b+(n/d)\le n\leftrightarrow 1\le b\le n(d-1)/d$ and for each such $b$ there's a unique $a$ , a total of $n\left (\frac{d-1}{d}\right)$ ordered pairs which clearly tends to infinity as $d$ is fixed and $n\to \infty$ . $\square$. Claim. If $\deg P\ge 2$, $P_n$ can get arbitrarily large. Proof. Let $g(x)=P(x+1)-P(x)$, by Schur's Thm we can find an infinite chain of distinct primes dividing it. Take a sufficiently long chain $p_1, \dots, p_k$ of such primes and observe that for each $p_i$ there exist $x_i, a_i$ with $$P(x_i)\equiv P(x_{i}+1)\equiv a_{i}\pmod{p_{i}}$$Since the congruence $P(x)\equiv a_{i}\pmod{p_{i}}$ has at least two distinct solutions for $i=1, \dots, k$ by CRT if we let $n=p_{1}p_{2}\cdots p_{k}$ the congruence $P(x)\equiv a_{i}\pmod{n}$ has at least $2^k$ distinct solutions and by PHP there's always a residue that occurs at least $\frac{2^k}{k}$ times , again $P_{n}\to \infty$.

The answers are \(P(x)\equiv x+c\) and \(P(x)\equiv-x-c\) for \(c\ge-2021\), which obviously work. Now we will show these are the only solutions. Without loss of generality \(P\) has positive leading coefficient. For all \(i\), \(n\), let \(r_{i,n}\) denote the number of \(1\le k\le n\) such that \(P(k)\equiv i\pmod n\), and let \(s_{i,n}\) denote the number of \(1\le k\le n\) such that \(|P(k)|\equiv i\pmod n\). We are given that \[\sum_{i=1}^n\binom{s_{i,n}}2\le2021\]for all \(n\). Claim: [Eliminating the absolute value signs] There exists a constant \(M\) (dependent on \(P\)) such that for all \(n\), \[\sum_{i=1}^n\binom{r_{i,n}}2\le M.\] Proof. Select \(m\) such that \(P(k)\ge0\) for all \(k>m\); then, only for \(k\le m\) can \(|P(k)|\ne P(k)\). It follows that \[\sum_{i=1}^n|r_{i,n}-s_{i,n}|\le2m.\]We are given that \(\sum_{i=1}^n\binom{s_{i,n}}2\le2021\), so \(s_{i,n}\le64\) always. It follows that \begin{align*} \sum_{i=1}^n\binom{r_{i,n}}2 &\le2021+\binom{64+2m}2-\binom{64}2, \end{align*}which is constant. \(\blacksquare\) Claim: [Bounded \(P_n\) implies zero] We have \(P_n=0\) for all \(n\). Proof. The key idea is to choose an enormous prime \(q\gg n\) and consider the statement ``\(P_{nq}\le M\).'' Observe by Chinese Remainder theorem that \begin{align*} P_{nq}&=\sum_{i=1}^{nq}\binom{r_{i,nq}}2=\sum_{i=1}^n\sum_{j=1}^q\binom{r_{i,p}r_{j,q}}2 =\sum_{i=1}^n\sum_{j=1}^q\frac{r_{i,n}^2r_{j,q}^2-r_{i,n}r_{j,q}}2\\ &=\frac{\left(\sum_{i=1}^nr_{i,p}^2\right)\left(\sum_{j=1}^qr_{j,q}^2\right)-\left(\sum_{i=1}^nr_{i,n}\right)\left(\sum_{j=1}^qr_{j,q}\right)}2\\ &=\frac{\left(2\sum_{i=1}^n\binom{r_{i,n}}2+n\right)\left(2\sum_{j=1}^q\binom{r_{j,q}}2+q\right)-nq}2\\ &=\frac{(2P_n+n)(2P_q+q)-nq}2=2P_nP_q+P_nq+P_qn\ge P_nq. \end{align*}We know \(P_{nq}\) is bounded above by \(M\), but if \(P_n\ne0\), we may select \(q\) such that \(P_nq>M\), contradiction. \(\blacksquare\) Finally, the rest is routine (e.g.\ see ISL 2005 N2). From \(P_n=0\), we know that \(P(1)\), \ldots, \(P(n)\) are all distinct modulo \(n\). Claim: For all \(n\), \[\max\{P(1),\ldots,P(n)\}-\min\{P(1),\ldots,P(n)\}=n-1.\] Proof. Let \(d:=\max\{P(1),\ldots,P(n)\}-\min\{P(1),\ldots,P(n)\}\). Then: If \(d\le n-2\), by Pigeonhole Principle \(P(i)=P(j)\) for some \(1\le i,j\le n\), violating \(P_n=0\). If \(d\ge n\), then \(\max\{P(1),\ldots,P(n)\}=\min\{P(1),\ldots,P(n)\}\pmod d\), violating \(P_d=0\). \(\blacksquare\) For large enough \(n\), this implies \(P(n+1)=P(n)+1\), so \(P\) is linear with slope 1. It is then easy to verify that the only solutions are \(P(x)\equiv x+c\) for \(c\ge-2021\). Dropping the assumption that \(P\) has positive leading coefficient gives the desired solution set.

Kamran011 wrote: by CRT if we let $n=p_{1}p_{2}\cdots p_{k}$ the congruence $P(x)\equiv a_{i}\pmod{n}$ has at least $2^k$ distinct solutions Why we have the congruence $P(x)\equiv a_{i}\pmod{n}$ has at least $2^k$ distinct solutions?

Ok, if we construct these solutions one by one, for each $i$ take either $P(x)\equiv x_i$ or $x_{i}+1$ modulo $p_i$ so in the end any two of the $2^k$ obtained numbers differ by at least one $p_i$

sarjinius wrote: Let $q \equiv 1 \pmod{p}$ be a very big prime number. By Dirichlet's Theorem, $q$ can be as large as possible. Then for all $(a, b) = (s, s + q), (s + p, s + q + p), (s + 2p, s + q + 2p), \ldots, (s + 2021p, s + q + 2021p)$, we have $pq \mid P(a) - P(b)$. Since $q$ is very large, $p - 1 > 0$, and $s$ is not dependent on $q$, $(p - 1)(q - 2021) > s + 2021 \iff pq > s + q + 2021p$. So if we let $n = pq$, the aforementioned $2022$ pairs work, which violate the condition. Is it necessary that we have to choose $q$ as a prime number? Can we just simply choose $q$ as a positive integer large enough satisfies $q \equiv 1 \pmod{p}$ since we still have $pq \mid P(a) - P(b)$ and the remains can just be done in the same way?

Firstly, notice that $P$ cannot be constant, since then all $(a,b)$ with $1 \leq a<b \leq n$ would satisfy, which is absurd for large $n$. Now, we make a Claim: Claim 1: $\deg P=1$. Proof: Suppose not, and let $\deg P \geq 2$. Then, take $n=p^k$ where $p$ is a prime and $k$ a pretty large positive integer. Then, we prove a Subclaim: Subclaim: If $p \mid P'(a)$ for some $a$, then $p^k \mid P(a+p^{k-1})-P(a)$ . Proof: Let $P(x)=\sum_{i=0} ^ {n} a_ix^i$ be the polynomial, then note that $$P(a+p^{k-1})-P(a)=\sum_{i=0}^{n} a_i((a+p^{k-1})^i-a^i)$$ In order to show that $p^k \mid P(a+p^{k-1})-P(a)$ we only need to show that $P(a+p^{k-1})-P(a) \equiv p^{k-1}P'(a) \pmod p^k$, since this would imply the desired. Note that $$p^{k-1}P'(a)=\sum_{i=1}^{n} p^{k-1}ia_ia^{i-1}$$hence it would suffice to show that $(a+p^{k-1})^i-a^i \equiv p^{k-1}ia^{i-1} \pmod {p^k}$ for all $i \geq 1$ (the $i=0$ case is trivial, as then $(a+p^{k-1})^i-a^i =p^{k-1} \equiv 0 \pmod {p^2}$). To prove the desired, we just employ the binomial formula. All terms in $(a+p^{k-1})^i$ are $\equiv 0 \pmod {p^2}$, except for two - $\binom{i}{1}a^{i-1}p^{k-1}$ which equals $ia^{i-1}p^{k-1}$, and $a^i$. Hence the Subclaim is proved $\blacksquare$ To the Claim, we notice that if $\deg P \geq 2$, then $\deg P' \geq 1$, hence by Schur, there are pretty large $p$ such that there exists a $\ell \leq p$ such that $p \mid P'(k)$. Taking such a prime $p$ and such a $\ell$, we notice that all pairs of the form $(r,r+p^{k-1})$ satisfy, where $r \equiv \ell \pmod p$. The number of these pairs has to be $\leq 2021$ by the problem's condition. Nevertheless, note that the following numbers all satisfy the condition $r+p^{k-1} \leq n =p^k$: $$\ell,\ell+p,\ell+2p, \ldots, \ell+(p^{k-1}-p^{k-2}-1)p$$ Indeed, note that $$\ell+(p^{k-1}-p^{k-2}-1)p \leq p+p^k-p^{k-1} -p =p^k-p^{k-1}=n-p^{k-1},$$as desired. The number of these is $p^{k-1}-p^{k-2}-1$, which can be pretty large as $p$ can be infinitely large. Hence, we get a contradiction. Therefore, $\deg P=1$ $\blacksquare$ To the problem, we have established that $P$ is linear. We do more: Claim 2: The coefficient of $x$ is $\pm 1$. Proof: Suppose not, then there exists a prime $p$ dividing $a_1$ (we use the notation $P(x)=\sum_{i=0} ^ {n} a_ix^i$). Then, take $n=p^{2s}$ and note that $P(p^s) =p^sa_1+a_0$ and $P(p^s+p^{2s-1}) =p^sa_1+p^{2s-1}a_1+a_0 \equiv p^sa_1+a_0$, therefore $P(p^s) \equiv P(p^s+p^{2s-1})$, and in general, $P(mp^s) \equiv P(mp^s+p^{2s-1})$ for all $m \geq 1$. Taking $s$ to be pretty large, we can obtain $P(mp^s) >0$ and $P(mp^s+p^{2s-1}) >0$. In addition, note that there are exactly $p^s-p^{s-1}$ pairs $(mp^s,mp^s+p^{2s-1})$ such that both numbers are smaller than $n=p^{2s}$. The above is a clear contradiction for large $s$ $\blacksquare$. To the problem, we have that $P(x)=x+c$ or $P(x)=-x+c$ for some $c$. If $P$ satisfies, then $-P$ also does, so WLOG we may assume that $P(x)=x+c$. Then, we have two cases to consider. Case 1: $c \geq 0$. Then, $$|P(a)|-|P(b)|=|a+c|-|b+c|=(a+c)-(b+c)=a-b,$$which is never divisible by $n$, as it is less than $n-1$. Case 2: $c \leq 0$. Let $c'=-c$, then $|P(x)|=|x-c'|$, which is equal to $x-c'$ when $x \geq c'$, and to $c'-x$ otherwise. It is clear that no pairs $(a,b)$ could satisfy the condition when both $a,b$ are greater or less than $c'$. Hence, assume that $b>c'>a$ and take a pretty large $n$, such that $n \geq 2c'+1$. Then, $|P(a)|-|P(b)|=2c'-(a+b) \equiv 0 \pmod n$. Then, let $a=c'-e, b=c'+f$ and note that $2c'-(a+b)=e-f \equiv 0 \pmod n$. If $|e-f| \geq n$, then either $e$ or $f$ is $\geq n$. But, $f<b \leq n$ and $e <c'<b \leq n$, hence this is a contradiction. Therefore, $e=f$, implying that the only acceptable pairs are the ones of the form $(c'-e,c'+e)$, which are exactly $c'-1$ (since $e \in \{1,2, \ldots, c'-1 \}$. Note that $n \geq 2c'-1 \geq c'+e$.), hence $c' \leq 2022$ i.e., $c \geq -2022$. Therefore, solutions are all polynomials of the form $P(x)=\pm (x+c)$ with $c \geq -2022$, which work, as seen above.

nbdaaa wrote: sarjinius wrote: Let $q \equiv 1 \pmod{p}$ be a very big prime number. By Dirichlet's Theorem, $q$ can be as large as possible. Then for all $(a, b) = (s, s + q), (s + p, s + q + p), (s + 2p, s + q + 2p), \ldots, (s + 2021p, s + q + 2021p)$, we have $pq \mid P(a) - P(b)$. Since $q$ is very large, $p - 1 > 0$, and $s$ is not dependent on $q$, $(p - 1)(q - 2021) > s + 2021 \iff pq > s + q + 2021p$. So if we let $n = pq$, the aforementioned $2022$ pairs work, which violate the condition. Is it necessary that we have to choose $q$ as a prime number? Can we just simply choose $q$ as a positive integer large enough satisfies $q \equiv 1 \pmod{p}$ since we still have $pq \mid P(a) - P(b)$ and the remains can just be done in the same way? $q$ does not have to be necessarily prime. I forgot that $q \equiv 1 \pmod{p}$ already implies that $gcd(p, q) = 1$, so I let $q$ be prime during the actual contest.

Very nice problem. Note that if $P$ is a solution, then so is $-P$, and $P$ is clearly non-constant. Hence we can assume a positive leading coefficient and the existence of some positive integer $k$ such that $P(x)>0$ for all $x>k$. For any $n \in \mathbb{N}$, let $Q_n$ be the number of integer pairs $(a,b)$ such that $k<a<b\leq n$ and $n \mid P(a)-P(b)$. Clearly $Q_n \leq P_n \leq 2021$ for all positive integers $n$. Claim 1: For every integer $m>1$, $P$ hits all residues modulo $m$. Proof: Assume FTSOC that $P$ doesn't hit some residue modulo $m$ for some $m>1$. Then for any $d>0$, if we let $n=dm$, $P$ doesn't hit at least $d$ residues modulo $n$. For $0 \leq i <n$, let $a_i$ denote the number of integers in the interval $(k,n]$ satisfying the congruence $P(x) \equiv i \pmod n$. Then, at most $n-d$ of the $a_i$ are non-zero. So, $$2021 \geq Q_n = \sum_{i=0}^{n-1} \binom{a_i}{2} \geq (n-d) \binom{\frac{a_0+a_1+\cdots+a_{n-1}}{n-d}}{2}=(n-d) \binom{\frac{n-k}{n-d}}{2}$$by AM-GM. Putting $n=dm$ and expanding, we get $$4042d(m-1) \geq (dm-k)(d-k)$$which clearly cannot hold for sufficiently large $d$ because LHS is linear while RHS is quadratic. $\blacksquare$ In particular, $P(0),P(1), \dots P(m-1)$ are distinct modulo $m$ for all $m>1$. If we let $P(0)=c$, and define $Q(x)=P(x)-c$, then $m \mid Q(x)$ $\implies$ $m \mid x$ for all $m>1$ and $x \in \mathbb{Z}$. Note that $Q(0)=0$, but $Q$ is not identically $0$ because $P$ is non-constant (in fact $Q$ has a positive leading coefficient because of our initial assumption). Let $Q(x)=x^lR(x)$ for some $l >0$ where $R(0) \neq 0$. If $R$ is non-constant, then by Schur's theorem there exists a large prime $p>|R(0)|$ such that $p \mid R(x)$ for some integer $x$. But this means $p \nmid R(0)$ $\implies$ $p \nmid x$, while $p \mid x^lR(x)$, contradiction! Therefore $R$ is constant, say $d > 0$. If $d>1$ or $l>1$, then we can choose $x=2$ and $m=d2^l>2$ to get $m \mid Q(2)$ but $m \nmid 2$, contradiction! Therefore $Q(x)=x$ and $P(x)=x+c$. Now we narrow down on the $c$ that work. Clearly $c \geq 0$ works, so assume $c<0$; let $-c=d>0$.Then $|P(x)|=d-x$ for $1 \leq x \leq d$, and $|P(x)|=x-d$ otherwise $\implies$ $|P(a)|-|P(b)|= \pm (a-b)$ or $\pm (a+b-2d)$. If $0<a<b \leq n$ and $n \mid |P(a)|-|P(b)|$, then we must have $|P(a)|-|P(b)|=\pm (a+b-2d)$, so $a,b$ lies on different sides of $d$: $b >d \geq a$. So if $n \leq d$, $P_n=0$. Else we have $$-n <-d < a+b-2d \leq n-d <n$$So if $n \mid \pm(a+b-2d)$, we must have $a+b=2d$. For $n<2d$, this has precisely $n-d \leq d-1$ solutions, and for $n \geq 2d$, it has precisely $d-1$ solutions. Therefore we must have $d-1 \leq 2021$ $\implies$ $d \leq 2022$. So the solutions are $$\boxed{P(x)= \pm(x+c)}$$where $c \geq -2022$ is any integer.

The absolute value is just really annoying. I was stuck by that stupid stuff during the contest . And be pointed out how stupid I am after the contest. However, it is not a very bad thing cuz giving up this question just makes me have enough amount of time to do the problem 5

My solution: First, it is clear from the condition that $\vert P\vert$ hits at least $n-4042$ different residue classes modulo $n$. Indeed, the number of $x$ such that $n \mid \vert P(x)\vert-\vert P(y)\vert$ for some $y$ with $n \nmid x-y$ is bounded by $4042$ by assumption, hence $\vert P\vert$ already hits at least $n-4042$ different residue classes exactly once. Second, getting rid of the absolute value, this implies that for some $C=C(P)$, the polynomial $P$ itself hits at least $n-C$ different residue classes modulo $n$ for each $n$ (since $P(x)$ has constant sign for large $x$). Third, $P$ is indeed bijective modulo all $n$. Indeed, suppose that $P$ does not hit some residue classe modulo $n$. Then if $m$ is coprime to $n$, there are $m$ residue classes modulo $mn$ not hit by $P$. Contradiction if $m>C$. Fourth, fixing $m$ large and $n=\vert P(m)-P(0)\vert \ne 0$, this implies that $P(m) \equiv P(0) \mod n$ and hence $n \mid m$ by bijectivity whence $P(m)-P(0) \mid m$ for all large $m$ and hence clearly $P(x)=\pm x+P(0)$ is the only possibility.

Miku3D wrote: 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 \leq n$ and $|P(a)|-|P(b)|$ is divisible by $n$. Determine all polynomial $P$ with integer coefficients such that $P_n \leq 2021$ for all positive integers $n$. Hehe headsolved We claim that the answer is $P(x) \equiv x+a$ and $P(x) \equiv -x-a$ for $a \geq -2022$. It is easy to see these work. Now we prove that these are the only solutions. Note that $P$ works iff $-P$ works. So assume WLOG that $P$ has a positive leading coefficient (it is easy to see that the zero polynomial doesn't work). Let $P(x) > 0$ for all $x > t$, where $t \in \mathbb{Z}^+$. Let $Q(x) \equiv P(x+1)-P(x)$. Suppose $|Q(x)|$ takes a value other than $1$ over the integers. Then their exists a prime $p$ and $a \in \{0, \dots, p-1\}$ such that $p | Q(x)$ if $x \equiv a \mod p$. Then $P(c) \equiv P(d) \mod p$ whenever $c \equiv a \mod p, d \equiv (a+1) \mod p$. Note that $a \not\equiv (a+1) \mod p$. Let $q$ be a prime other than $p$. Let $n = pq$. Now, suppose $e \equiv f \mod q$, and $e \equiv a \mod p, f \equiv (a+1) \mod p$. Then $p | (P(e)-P(f)), q | (P(e)-P(f))$ (as $q | (e-f) | (P(e)-P(f))$). So $n | (P(e)-P(f))$. If $e, f > t$, then we get $n | (|P(e)|-|P(f)|)$. Choose $q$ to be greater than $2025+t$. Then using CRT we get $q$ pairs s.t. $n | (P(e)-P(f))$, $0 < e, f \leq n, e \neq f$ (vary the value of $e \mod q$ from $0$ to $(q-1)$). Of these, at most $t$ can have one member $\leq t$, so we get at least $q-t > 2025$ pairs satisfying $n | (|P(e)|-|P(f)|)$, so we are done. Suppose $|Q(x)| = 1$ always for $x \in \mathbb{Z}$. Then $Q(x) \equiv 1$, so $P(x) \equiv x-s$ for some $s \in \mathbb{Z}$. For $s > 2022$, choose $n = 2s+100$, and note that $n | 0 = (|P(s+i)|-|P(s-i)|)$ for $i = 1, \dots, (s-1)$, so we have $(s-1) > 2021$ pairs, so we're done.

This is similar to #3. Solution. The answer is $P(x)=\pm (x+c)$ with $c \ge -2022$. The main idea is instead of using a specific $n$ and trying to find $a,b$, we try to use a specific $a,b$ and try find/adjust $n$. Note that $P$ satisfies if and only if $-P$. WLOG, the leading coefficient of $P$ be positive. Define $Q(a,b) = |P(a)|-|P(b)|$. Note that for $a,b$ sufficiently large, $Q(a,b) = P(a)-P(b)$. There are two cases: a. If $Q(a,a+1)$ is eventually $1$ or $-1$, then $P$ is linear with the leading coefficient of $1$ or $-1$. It's not hard to prove that $P(x) = \pm (x+c)$ with $c \ge -2022$. b. Choose a sufficiently large $a$ and integer (not neccesarly a prime) $p>1$ satisfying $p|Q(a,a+1)$. Let $q = pb+1$. Then observe that $pq|Q(a,a+1+pb)$. Observe that for $c=0,1,\dots , d$ we have $$pq | Q(a +(pc) ,a+1+pb+(pc)).$$And in order for these pairs of $(a,b)$ to be valid, we need to show that each are at most $pq$ by proving $$a+1+pb+pd \leq pq$$$$\iff a+pd+(pb+1) \leq p(pb+1)$$$$\iff a+pd \leq (pb+1)(p-1).$$Now given any $d$, we can choose a sufficiently large $b$, thus $P_n \rightarrow \infty$.

revenge feels so, so sweet Intuitively, $P$ with degree $\geq 2$ do not work. We will prove this: Proof: Note that past some number $r$ such that $P(r) > 0$, polynomial $P$ becomes strictly increasing, so we take $n >> r$ and consider only $r < a < b$ to purge the annoying absolute value signs. If we can prove that the number of these solutions, which is a subset of $P_n$, eventually surpasses $2021$ for large enough $n$, we will be done. We will prove that in fact, there will be enough solutions of the form $(c, c+1)$ for large enough $n$. Consider $Q(x) = P(x+1) - P(x)$. We know $Q$ is not constant by assumption $\text{deg}(P) \geq 2$. Claim (Schur): Infinitely many primes divide the sequence $\{Q(n)\}_{n = 0}^{\infty}$ given $Q$ is not linear. Proof: Write $Q(x) = xR(x) + q$ for some integer constant $q$ and integer polynomial $R$. Note that\[Q(rk!) = r(k!R(rk!) + 1)\]must have some prime divisor $> r, k$ since all primes $< k$ do not divide $k!R(rk!) + 1$. Taking $k$ large enough proves that for any large enough threshold, there is a greater prime that divides some $Q(n)$, proving the result. This result tells us that for $Q(x) = P(x+1) - P(x)$, that there are infinitely many primes $p_1, p_2, \ldots $ for which $Q(x) \equiv 0 \pmod {p_i}$ admits some solution $a_i \pmod {p_i}$ so that $P(a_i + 1) \equiv P(a_i) \pmod {p_i}$. This means for each $p_i$, there is a residue $r_i$ for which $P(x) \equiv r_i \pmod{p_i}$ has two solutions, $a_i$ and $a_i +1$, mod $p$. If we take $n = p_1p_2\ldots p_N$ for a super large $N$, then note that if $S$ is the solution to the system $S \equiv r_i \pmod{p_i}$ from all $i : 1 \to N$, then $P(x) \equiv S \pmod n$ has a least $2^N$ distinct solutions modulo $n$, generated by\[x \equiv \{a_i, a_i + 1\} \pmod{p_i} \text{ across } i: 1 \to N.\]So for this large enough $n$, we have a residue $S$ for which there are at least $2^N$ solutions to $P(x) \equiv S \pmod N$. At least $2^N - r$ of them satisfy $x > r$, and taking any of these two yields a valid pair $(a, b)$. Taking $N \to inf$ clearly yields $>> 2021$ solutions, our desired contradiction. $\square$ Now, we know $P$ is linear. If $P(x) = mx + b$ with integer $|m| \neq 1$, then we have $P(a) - P(b) = m(a - b)$ and taking large enough $n = Q|m|$ tells us that any pairs with $Q\mid a - b$ works, which yields $\approx n(1 - \tfrac{1}{|m|})$ solutions for large enough $n$. This exceeds $2021$. Then, it becomes easy to manually verify that the only solutions are $P(x) = \pm(x + c)$ for $c \geq -2022$. Victory!

Suppose the degree of $P$ is greater than $2$ for now, consider only sufficiently large numbers so we can ignore the absolute value signs. By Schur, we know that $P(x+k) - P(x)$ has infinitely many divisors for any value of $k$, take only $k = 1$ or something for now. Consider a series of such prime divisors $p_1, p_2, p_3, \cdots, p_z$. Clearly, $P_{p_i} \ge 2$ since we just picked it such that it divides two consecutive values of $P$. Now consider the number $M = p_1p_2 \cdots p_z$, by CRT, it has at least $2^z$ pairs with $M | P(a) - P(b)$, since we can make $z > 12$, this is a contradiction to the problem statement. Now let $P = a_1x + a_2$, we're looking at when $n | a_1(a-b)$ or letting $n = ka_1$, we want $k | a-b$ for $a,b \le ka_1$. If $a_1 > 1$, then we can find at least $\frac{n}{2}$ such pairs again, impossible. So the only possibility is $P = x+c$ or $-x+c$, which both clearly work, so we are done but $c \ge -2022$ must be true otherwise the absolute value signs mess things up. $\blacksquare$

Answer is $P(x)= \pm (x-c)$ for any integer $c \le 2022$. It's not hard to see that all these work. Notice that $P(x)$ works iff $-P(x)$ works: hence from now on we assume the leading coefficient of $P$ is positive. Clearly no constant polynomials work. If $P=x-c$ is linear and monic, then it fails whenever $c \ge 2023$: picking $n=2022+c$, we have $$P(1),P(2), \dots , P(n) = 1-c, \dots , 2022$$which has $P_n=2022$ since $P(1) \le -2022$. If $P=ax+b$ is linear with $a>1$, then it fails by picking $n=aN$ for some very large $N$: for every positive integer $m< (a-1)N$ we have that$$P(m) \equiv P(m+N) \pmod{aN}$$and both these numbers are positive as long as $m> -\tfrac{b}{a}$. Since $N$ is arbitrarily large, this means we can get $P_n$ arbitrarily large. If $\text{deg}(P)>1$, then let $N$ be some arbitrarily large integer (large enough so that $P(x)>0$ for any $x \ge N$). Since $x-N$ divides the polynomial $P(x)-P(N)$, we can define an integer polynomial$$Q(x):=\frac{P(x)-P(N)}{x-N}.$$Then we can pick $n=Q(N)^2$, and we have$$(x-N)Q(x) \equiv 0 \pmod{n} \iff P(x) \equiv P(N) \pmod{n}$$whenever $x=N+tQ(N)$ for some positive integer $t$. This is because both $x-N$ and $Q(x)$ are divisible by $Q(N)$. Since $\text{deg}(Q)>0$, we have$$N+2022Q(N)<Q(N)^2$$for large enough $N$, and this gives $P_n \ge 2022$.

We claim there exists a prime $p$ for which all of $(a,b)=\{(x, x+n/p): x\in X_p(n)\}$ satisfies $n\mid |P(a)| - |P(b)|$ for large enough $n$, and where $X_p(n)$ is a set that grows linearly in size in $n$. Let $P(x) = a_kx^k + a_{k-1}x^{k-1} + \cdots + a_1x+a_0$ be fixed. WLOG (among $P$ or $-P$) we have $P(x)\ge 0$ for all $x>N$ for some constant $N$. We will focus only on those $x$ greater than $N$. Consider a prime $p$, which is arbitrary for now. Then \begin{align*} P\left(\frac{n}{p} + x \right) - P(x) &= a_k\left( \left( \frac{n}{p}+x \right)^k - x^k \right) + \cdots + a_1\left( \left(\frac{n}{p}+x\right)-x \right) \\ &= n^2 \cdot \frac{1}{p^C} \cdot R(a,n) + n\cdot \frac1p \cdot Q(x) \end{align*}where $C$ is a constant, and $R(a,n)$ is a polynomial with integer coefficients in $a$ and $n$, and $Q(x)=ka_kx^{k-1}+\cdots+1a_1x^0$ is a fixed polynomial in terms of $x$. Former Term: By only taking those $n$ that are divisible by $p^C$, the former term above is $n \cdot (n/p^C)R(a,n)$, which is an integer times $n$ and hence a multiple of $n$. Latter Term: We want the latter term $n\cdot Q(x)/p$ to be a multiple of $n$. This is equivalent to $Q(x)$ being a multiple of $p$. By Schur's Theorem (applicable since $Q$ nonconstant for non-linear $P$), there exists some prime $p$ for which there exists some $x_0\in \{0,\ldots,p-1\}$ for which $p \mid Q(x_0)$. Then $p\mid Q(x_0), Q(x_0+p), Q(x_0+2p),\ldots$. So there are at least $n/p - 100$ values $x\in \{0,\ldots,n-1\}$ which satisfy $p\mid Q(x)$. To recap all the logic: The restrictions on $n$ we placed throughout the above are: (1) $p^C\mid n$, (2) $n/p-100>0$. Infinitely many large enough $n$ satisfy these. The restrictions on $x$ we placed throughout the above are: (1) $x>N$, (2) $x \in \{x_0, x_0+p, x_0+2p,\ldots,x+(n/p-100)p\}$. Call $X_p(n)$ the set of $x\in \{0,\ldots,n-1\}$ satisfying these. We have $|X_p(n)| \ge (n/p-100)-N$, which grows linearly in $n$. So infinitely many large enough $n$ satisfy there existing a set $X_p(n)$ which grows in size linearly in $n$, for which $(x,x+n/p)$ works for all $x\in X_p(n)$. This is a contradiction, since $P_n \ge |X_p(n)|$ grows beyond $2021$ for large enough $n$. The above logic only fails when $Q$ is constant, as we cannot apply Schur. $Q$ constant is equivalent to $P$ linear. If $P(x)=cx+d$, then taking large enough $x$ for which $P(x)>0$, we have $P(a)-P(b)=c(a-b)$. If $c>1$, then infinitely many $(a,b)$ work -- those which are spread out by $n/c$ (similar to main idea in $\deg P\ge 2$ case). So $c=1$, and now we can verify $P(x) = x + C$ works for any constant $C\ge -2021$. (We WLOG assumed $P$ or $-P$, so negatives too.)

laikhanhhoang_3011 wrote: Take a prime divisor $q$: $q|P(M+t)-P(M);t>0,(t,M)=1$ $\Rightarrow (t,q)=1$ Why it gives $(t,q)=1$.I've been trying for it but failed.

Very loose. Answer is $x + c$ for $c \geq -2022$ and $-x-c$ for $c \leq 2022$. First, notice for large $n$, $P$ has one sign, so WLOG $P(+\infty) = +\infty$. If $P(x)$ does not cover all residues modulo some $n$, then taking $kn$ for large $k$ gives contradiction. Now only consider large inputs for $P$ and drop the $2021$ condition, then we can say $P(0) = 0$ and remove absolute value signs. Now notice for large primes $p$ after $P$ is strictly increasing for nonconstant $P$ (constant fails obviousy), $P(p) = p^k+c$ for some $k$ as otherwise $P(p) \equiv P(0) \pmod r$ for a prime $r \neq p$ would miss a residue. Now by polynomial degree bounding and since this exponent $k$ is monotonic increasing eventually and bounded above by the degree of $P$, that eventually $P(x) = x^k+c$ at infinitely many values for some $k$, so it follows $P(x) = x^k+c$. However by Dirichlet there exists $p \equiv 1 \pmod k$ for $k > 1$, and the polynomial collapses mod $p$, giving contradiction. Thus $P(x) = \pm x + c$ for some $c$. Basic verification gives the desired set.

Theorem: If a - b ≡ x - y (mod m), then a ≡ x (mod m) and b ≡ y (mod m), where a, b, x, y, and m are integers.(modular arithmetic's substraction property) By applying the theorem, (|p(a)| - |p(b)|) ≡ (0 - 0) (mod n) implies that |p(a)| ≡ 0 (mod n) and |p(b)| ≡ 0 (mod n). Also, |p(a)| is greater than |p(b)|. So we conclude that the possible polynomials are p(x) = x + d, p(x) = -x - d, and p(x) = x - d.

The idea here is to notice that $P$ must be surjective modulo every prime $q$. To check this, assume that $P$ skips some residue $i$ modulo $q$. Then, taking $n = qk$ we get that the numbers $P(1), P(2), \dots, P(qk)$ skip all residues mod $qk$ of the form $ql+i$, that is, there are at least $k$ residues mod $qk$ missing, so there must be at least $k$ residues repeating. Taking $k >> 2021$ this leads to a contradiction. We now show that $P(x) = \pm x +c$ are the only polynomials surjective modulo every prime. To do this, let $Q(x):=P(x+1)-P(x)$. If this value is not $1$ or $-1$ for some $x \in \mathbb{Z}$, then take a prime dividing it, a contradiction as then $P$ would not be surjective modulo that prime (being surjective and injective in $\mathbb{Z}/n\mathbb{Z}$ is clearly the same thing). Thus $P(x+1)-P(x)$ is or $1$ or $-1$ infinitely many times, implying that $P(x) = \pm x +c$. Now one can easily check that the ones that work are $P(x)=x+c$ for $c\geq -2022$ and $P(x)=-x-c$ for $c\geq -2022$ Remark: I ignored that $P(a)$ and $P(b)$ are taken with their absolute values because we can assume WLOG that they have possitive leading coefficient, so from a point on they are positive, and taking $k$ big enough does the job.

Nice Problem: Assume $\deg(P) \ge 2$. We take sufficiently large values of $a, b, n$ such that $P(a), P(b)$ have same sign. Then: consider $Q(n) = P(n+1)-P(n)$. By Schur's theorem, as $Q$ is non-constant, there exists infinite primes $p_1, p_2, \cdots, $ which divide $Q$. Consider $t$ of them: $p_1, \cdots, p_t$. Each prime provides at-least one such pair. Taking $t$ large enough, we will have $P_n > 2021$ for sufficiently large values of $n$ (where we take $\deg(P) \ge 2$). Consider $P$ to be linear polynomial. Let $P(x) = Rx+S$ with $R > 1$. Then, taking $n=Rn'$ for some large value of $n'$ gives us: $P(m) \equiv P(m+n') \pmod n$ and these have same sign for $m > -\tfrac{S}{R}$. Taking $n'$ sufficiently large enough, we can get $P_n > 2021$. Similarly, we go for $R < -1$. Taking $R=\pm 1$, we get $P(x)= \pm x \pm c$. One can check that: $c = \{ 1, 2, \cdots, 2022\}$ only works for $P_n \le 2021$.