No such polynomial exist except $P(x)\equiv c$ where $c\in \mathbb{Z}$ which clearly works. Now, assume that $\deg P>0$ Since $x-y|P(x)-P(y)$ he condition can be written as $Q(m,n): m|P^{(m-n)}(n)-P^{(n)}(n),m>n$ For every pair $(m,n)$ with $m<n$ of positive integers denote by $T(m,n)$ the smallest positive integer such that there are positive integers $a,b$ such that $m|P^{(a)}(n)-P^{(b)}(n)$ and $|a-b|=T(m,n)$ Now it's easy to show that whenever there are positive integer $a,b$ such that $m|P^{(a)}(n)-P^{(b)}(n)$ and $|a-b|=c$ then $T(m,n)|c$ (write $c=kT(m,n)+b,0\leq b<T(m,n)$ and use the minimality of $T(m,n)$ to show that $b=0$) Claim: $T(m,n)|m$ Proof: $Q(m,n): m|P^{(m-n)}(n)-P^{(n)}(n)$ and $Q(2m,n): m|2m|P^{(2m-n)}(n)-P^{(n)}(n)$ so $m|P^{(2m-n)}(n)-P^{(m-n)}(n)$ and hence $T(m,n)|(2m-n)-(m-n)=m\blacksquare $ So in particular for every prime $q$ and $n<q$ we have $T(q,n)=1$ or $q$. We have the following claim: Claim: For large enough $n's$ at least one of the following equalities is true: $P^{(n)}(-n)=P^{P(n)}(-P(n))\,\,(*)$ $P^{(n)}(-n)=P^{-P(n)}(P(n))\,\,(**)$ $P^{(2n)}(-n)=n\,\,(***)$ Proof: Pick a positive integer $n>N$ (we are going to choose $N$ later) Case 1: There are infinitely many primes $q$ such that $T(q,n)=1$

Case 2: There are only finitely many primes $q$ such that $T(q,n)=1$

$\blacksquare$ Now, obesrve that $P(x)=x$ doesn't work since $m+n|n-m$ is not always true. Let's see now why each of $(*),(**),(***)$ can't have infinitely many solutions. If we do that, then we are done. Focus on $(*)$, suppose to the contrary that we can find arbitrary large $n$'s such that $(*)$ holds( note that this is the case where $P$ has positive leading coefficient) Lemma 1 There exist a positive integer $M$ such that for every integer $z$ with $|z|>M$ we have $|P(z)|>|z|$ Proof: This is simple, observe that the degree of $Q(x)= P(x)^2-x^2 $ is non-zero (otherwise $P(x)=x$ which is impossible) and it's an even positive integer, hence $Q(x)>0$ for $|x|$ large enough which leads to the desired result $\blacksquare$. Lemma 2 There exist a constant $K$ such that whenever $|x|>|y|>K$ we have that $|P(x)|>|P(y)|$ Proof: Use the approximation $P(x)=ax^n$ for $|x|$ large enough and the fact that $P'$ has finitely many roots so for large $|x$ the function $|P(x)|$ is inscreasing $\blacksquare$ Now, take $n$ to be large enough, then $|P(n)|>n>M$ and so $|P(P(n))|>|P(n)|>M$ and inductively we get that $|P^{(c)}(n)|>n>M$ for every $c\in \mathbb{N}$ Now since $|P^{(n-1}(n)|=A,|P^{(P(n)-1)}(-P(n))|=B$ are both large enough the condition $P(\pm A)=P(\pm B)$ gives $A|=|B|$ and doing the same thing again and again we finaly get that $n=|P^{(P(n)-n)}(-P(n))|>|P^{(P(n)-n-1)}(-P(n))|>..>|P(-P(n))|>n$ a contradiction! Same arguments gives us that $(**),(***)$ have only finitely many solutions as well, hence we are done.

P(n)=n+1 works

Prod55 wrote: Since $x-y|P(x)-P(y)$ he condition can be written as $Q(m,n): m|P^{(m-n)}(n)-P^{(n)}(n),m>n$ Can $x-y|P(x)-P(y)$ imply that $x-y|P^{(n)}(x)-P^{(n)}(y)$? If I'm missing something please let me know.... (Probably missing something)

dgkim wrote: Prod55 wrote: Since $x-y|P(x)-P(y)$ he condition can be written as $Q(m,n): m|P^{(m-n)}(n)-P^{(n)}(n),m>n$ Can $x-y|P(x)-P(y)$ imply that $x-y|P^{(n)}(x)-P^{(n)}(y)$? If I'm missing something please let me know.... (Probably missing something) $x-y \mid P(x) - P(y) \mid P(P(x)) - P(P(y)) \mid \cdots \mid P^{(n)}(x) - P^{(n)}(y)$

Prod55 wrote: No such polynomial exist except $P(x)\equiv c$ where $c\in \mathbb{Z}$ which clearly works. Now, assume that $\deg P>0$ Since $x-y|P(x)-P(y)$ he condition can be written as $Q(m,n): m|P^{(m-n)}(n)-P^{(n)}(n),m>n$ First, the $P(x)=x+1$ works too. Second, I can't get $Q(m,n)$. I have: $(m-n)+n \mid P^{(m-n)}(n) - P^{(n)}(m-n)$, and $(m-n)-(-n) \mid P^{(n)}(m-n)-P^{(n)}(-n)$. So: $m \mid P^{(m-n)}(n)-P^{(n)}(-n)$?

My solution from contest was the same as the official one.

Another nice problem from Navid! Every time I want to post a solution, the site says "New users are not allowed to post images in the Community.". I registered my account around a month ago, so what does it mean and what should I do to fix it?