prove that P is linear 
Suppose $P(x)$ is a polynomial so that for any integer $n, P(x)=n$ has a rational solution. Show all the coefficients of $P(x)$ are rational. Furthermore, show that $P(x)$ is linear.

To see why all the coefficients of $P$ are rational, choose a rational $x_k\in\mathbb{Q}$ so that $P(x_k)=k$ for $0\leq k\leq n,$ where $n=\deg P.$ Then by Lagrange interpolation, $P(x) = \sum_{k=0}^n k \prod_{j\neq k} \dfrac{x-x_j}{x_k-x_j}$. Then $P(x)$ is a sum of polynomials all of whose coefficients are rational, so $P(x)$ has the same property.

But how do I show $P$ is linear? I know this occurs iff $P$ has a bounded derivative.

 A: We don't really need $n$ to run all over $\mathbb{Z}$; restricting to $\mathbb{N}$ is enough to solve your problem.
As you have already proved, $P\in \mathbb{Q}[X]$. Then $\exists~M\in \mathbb{N}$ such that $Q=MP\in\mathbb{Z}[x]$. Thus $Q(x)=Mn$ has a rational root, say $\frac{p_n}{q_n}$, for all $n\in \mathbb{N}$. Now by Rational Root Theorem , theorem, we know that $q_n\mid D$, where $D$ is the leading coefficient of $Q$. Thus, we must have $|q_n|\le D, \forall n\in\mathbb{N}$. Hence we must have $|\frac{p_{n+1}}{q_{n+1}}-\frac{p_n}{q_n}|\ge  \frac{1}{D}$. But recall that $Q(\frac{p_n}{q_n})=Mn$. Thus by LMVT,
$$Q\left(\frac{p_{n+1}}{q_{n+1}}\right)-Q\left(\frac{p_n}{q_n}\right)=M$$
$$\implies |M|\ge \frac{|Q'(r_n)|}{|D|}  \qquad(*)$$
where $r_n$ is between $\frac{p_{n+1}}{q_{n+1}}$ and $\frac{p_n}{q_n}$. Also observe
$\{\frac{p_n}{q_n}\}_{n\ge 1}$ is unbounded(why?), hence $r_n$ is also unbounded. Now if $Q$ were not a linear polynomial, $Q'(r_n)$ would be unbounded, contradicting $(*)$.
A: COMMENT AND HINT FOR LARGER DEGREES.-We prove for quadratic $p(x)=ax^2+bx+c\in\mathbb Q[x]$. It is evident that the property is valid for linear polynomial in $\mathbb Q[x]$.
We have
$$\\p(r)-n=ar^2+br+c-n=0\\p(r_1)-1=ar_1^2+br_1+c-1=0\\p(r_2)-2=ar_2^2+br_2+c-2=0\\p(r_3)-3=ar_3^2+br_3+c-3=0\tag 1 $$ Taking $(1)$ as a linear system in $a,b,c$ and a new unknown $w$ one has the (very known) compatibility condition
$$\det\begin{vmatrix}r^2&r&1&n\\r_1^2&r_1&1&1\\r_2^2&r_2&1&2\\r_3^2&r_3&1&3\end{vmatrix}=0$$ from which we have $Ar^2+Br+C+nD=0$ where $A,B,C,D$ are constant. Solving the quadratic equation in $r$, the discriminant $B^2-4A(C+nD)$ should be a square so we have $$E+nF=z^2$$ whare $E$ and $F$ are constant and $n$ can be, say, integer arbitrary distinct of $1,2,3$. This is clearly absurd.
