Clearly $P$ cannot be constant, since then $P$ will be identically null, and the sequence $(a_i)$ will not be made of distinct numbers (will be constant equal to $0$). So $\deg P \geq 1$. Since $P$ takes more than its degree natural values at natural arguments, it will have rational coefficients (by being equal to the Lagrange interpolation polynomial for a set of $\deg P + 1$ natural arguments). By the result of the following Problem 6 (of mine) at the 2009 Master of Mathematics competition, see http://www.artofproblemsolving.com/Forum/posting.php?mode=quote&f=38&p=1857112& Given a polynomial $f(x)$ with rational coefficients, with degree $d \ge 2,$ we define a sequence of sets $f^0(\mathbb{Q}), f^1(\mathbb{Q}), \ldots$, as $f^0(\mathbb{Q})=\mathbb{Q}, f^{n+1}(\mathbb{Q})=f(f^{n}(\mathbb{Q}))$ for $n\ge 0$. (Given a set $S,$ we write $f(S)$ for the set $\{f(x), x\in S\})$ Let $f^{\omega}(\mathbb{Q})=\bigcap_{n=0}^{\infty} f^n(\mathbb{Q})$ be the set of numbers that are in all of the sets $f^n(\mathbb{Q}).$ Prove that $f^{\omega}(\mathbb{Q})$ is a finite set. the property cannot occur if $\deg P \geq 2$, because then $\{a_i \mid i=1,2,\ldots\} \subseteq P^{\omega}(\mathbb{Q})$. Therefore we need $\deg_P = 1$ (and indeed, a polynomial like $P(x) = x-1$ works, for the sequence $a_i=i$).

Hi mavropnevma, I'm sorry for waking up this topic but can you repost your link of your problem? ( as you said, problem 6 of mmr 2009). You link is dead I think, and I cant find it in contest forum. Thanks a lot.

@above http://artofproblemsolving.com/community/c6h1099628_dan_schwarz_has_died

Suppose that. $ Deg[P(x)]\geq 2$ Because $ P(a_i)>0$ for every natural number $i$ and the sequence $\{a_i\}_{i=1,2,\ldots}$ is unbounded. So, the leading coefficient of $ P(x)$ must be positive. Therefore, there is a natural number $c$ which the inequality $ P(x)>x $ holds for every $x>c$. Since the sequence $\{a_i\}_{i=1,2,\ldots}$ are all diferent values, there is a natural number $t$ which, for all $v\geq t$, $a_v>c$. Consider any $u\geq t$, $a_u>c\rightarrow P(a_u)>a_u\rightarrow a_{u-1}>a_u$ Therefore, $a_{t-1}>a_t>a_{t+1}>...$ which is contradicted by the fact that $a_i$ is positive integer for every positive integer $i$ Now, we can conclude that $ Deg[P(x)]\leq 1$ Trivially, $0$ doesn't work, but $1$ works by $P(x)=x-1$ So, the answer is only $1$.

Suppose the degree of this polynomial is $d > 1$. Let the leading coefficient of this polynomial be $b$. Then notice that asymptotically, $a_n \approx b \cdot a_{n+1}^d$. Now clearly $b$ cannot be negative, otherwise we will run into negative values of $a_i$ as the sequence grows (and it will, since it is a positive, unbounded sequence). Now, a quick glance back to the previous result tells that if $a_n$ is a large term, then the subsequent terms are all descending, which is obviously a contradiction since the sequence is always positive. So, the degree of such a polynomial cannot be greater than $2$. Now for $1$, just consider the polynomial $p(X) =X -1$.

Note that $P(x)-x|P(P(x))-P(x)$ thus the sequence $|a_{j+1}-a_j|$ is monotonically decreasing.Since $|\cdot|$ is always positive in this case, for $n\geq N$ there is an natural number $M$ so that $a_{j+1}=a_j\pm M$. But this implies if $\text{deg}(P)\geq 2$ then the set of roots of $P(x)-x\pm M$ (in total) is infinite, a contradiction. (Note that in the linear case the coefficient of $x$ becomes 0)