The answer is $P(x) = \pm x^e + c$, which clearly work. By negating $P$ if necessary, we assume the leading coefficient $c$ of $P$ is positive, and by shifting we may assume $P(0) = 0$. Assume also that $P$ is nonconstant Henceforth, we will only take $s,t > 0$, and thus we may assume $P$ is not even, otherwise we replace $P(X) = Q(X^2)$ with $Q(X)$, with no loss of generality. Lemma: [USA MOP 2007, Mock IMO #3] There exist arbitrarily large integers $r > 0$ such that $P(X) - r$ is irreducible over $\mathbb Z[X]$. Proof. Select $r$ such that the constant term of $P(X)-r$ is a large prime. If $r$ is large enough, then $|P(z)| = r$ implies that $|z|>1$, and so all complex roots of $P(X)-r$ should have absolute value exceeding $1$. Yet if $P(X)-r = f_1 f_2$ factors, one of the two factors should have constant term $\pm1$, and leading term equal to some integer $a$. So the complex roots of that polynomials have product $|1/a|$ in absolute value, contradiction. $\blacksquare$ Now, let $r$ be large as in the claim, and let $P(\alpha) = r$ for $\alpha = \alpha(r) \in {\mathbb R}_{>0}$ (this is possible for $r$ large enough, since $\lim_{x \to \infty} P(x) = \infty$). Then $P(\alpha^2) \in {\mathbb Z}$, and so $P(x^2) - k$ has $\pm \alpha$ as roots for some $k = P(\alpha^2)$. But the two polynomials $P(X)-r$ and $P(-X)-r$ are distinct and irreducible, and consequently we get the divisibility relation \[ \left( P(X)-r \right) \left( P(-X)-r \right) \mid P(X^2) - k. \]For degree reasons, and by comparing the leading coefficient, we get \[ \left( P(X)-r \right) \left( P(-X)-r \right) \equiv (-1)^{\deg P} c \left( P(X^2) - k \right). \]as an identity of polynomials. By setting $X = 0$ we conclude $k = -(-1)^{\deg P}\frac{r^2}{c}$. In other words, \[ P(\alpha^2) = (-1)^{\deg P+1} \frac{P(\alpha)^2}{c}. \]By varying the choice of $r > 0$ we find this holds for infinitely many large $\alpha > 0$, and so we conclude \[ c P(X^2) \equiv (-1)^{\deg P+1} P(X)^2. \]holds identically as polynomials. It's well-known this implies $P(X) \equiv cX^n$ for some odd integer $n$ (as we assumed $P$ was nonconstant). From here it is routine to obtain that we must have $c = \pm 1$. As we assumed $P$ was not even and had constant term $0$, reversing the assumptions in the first paragraph yields the solutions.

Answer. $P(x)=c$ and $P(x)=\pm x^d+c$, where $c$ is an integer and $d$ is a positive integer. If $P$ is constant, then the statement is trivially true, so assume $P$ is nonconstant and let $d=\deg P$. $P(2)$ is clearly an integer. Therefore whenever $P(s)$ is an integer, so is $P(2s)$. Let $R(x)=P(2x)-2^dP(x)$. Then $\deg R < \deg P$ and whenever $P(s)$ is an integer, so is $R(s)$. Suppose for the sake of contradiction that $R$ is nonconstant. Let $N$ be a real number such that $P$ and $R$ are both injective on $[N, \infty)$. Assume without loss of generality that $P$ is increasing (as we may negate $P$). Select integers $m_1, m_2$ such that $m_2 > m_1 > P(N)$, and let $k_1, k_2$ be the unique real numbers greater than $N$ such that $P(k_1)=m_1, P(k_2)=m_2$. In the interval $x\in [k_1, k_2]$, $P(x)$ is an integer for exactly $m_2-m_1+1$ values of $x$, so $R(x)$ is also an integer for at least $m_2-m_1+1$ values of $x$. As $R$ is also injective (and therefore strictly monotonic) over this interval, we must have $\lvert R(k_2)-R(k_1)\rvert \geq m_2-m_1$. Let $d'=\deg R$, and recall that $d' < d$. Then as $x\to\infty$, \[R(x)=O(x^{d'})=O(P(x)^{d'/d}).\]In particular, if we fix $m_1$ and let $m_2$ increase, we obtain $R(k_2)=O(m_2^{d'/d})=o(m_2)$. Hence for sufficiently large $m_2$ we will violate the inequality $\lvert R(k_2)-R(k_1)\rvert \geq m_2-m_1$. This contradiction proves that $R$ is constant. Since $R$ is constant, we have $P(2x)=2^dP(x)+c$ for a constant $c$. By comparing the coefficient of $x^i$ on both sides for $0 < i < n$, we conclude that $P$ is of the form $kx^d+c$ for integers $k, c$. $P(\sqrt[d]{\tfrac{1}{\lvert k\rvert}})$ is an integer, so $P(\sqrt[d]{\tfrac{1}{\lvert k\rvert}}\times\sqrt[d]{\tfrac{1}{\lvert k\rvert}})=\frac{\mathrm{sgn}(k)}{\lvert k\rvert}+c$ is an integer, and therefore $k=\pm 1$. Now we need to verify all polynomials of the form $\pm x^d+c$ work, which is simple. $\pm x^d+c$ is an integer if and only if $x^d$ is an integer, and if $s^d$ and $t^d$ are both integers, then so is $(st)^d$.

My solution at the contest The answer is $P(x)=Ax^k+C$ for integers $k \ge 0, C, A$ such that $|A|=1$. It is easy to check that these polynomials work. If $P$ is constant, then all $P(x) \in \mathbb{Z}[x]$ works. Assume that $k=\deg P \ge 1$. If $P$ satisfies the problem's conditions, then one can check that $-P$ satisfies the orignial condition too. So WLOG assume that the leading coefficient is postitive. Fix some positive integer $n$, and define $Q_n(x)=P(nx)-n^kP(x)$ We will show that $Q_n$ is a constant polynomial. Assume that $\deg Q \ge 1$, and note that $\deg Q < \deg P$. Since $P \in \mathbb{Z}[x]$, then $P(n)$ is an integer, so for real $w$, $P(w) \in \mathbb{Z} \implies P(nw) \in \mathbb{Z} \implies Q_n(w) \in \mathbb{Z}$. Case 1 : If the leading coefficient of $Q$ is positive, then the leading coefficient of three polynomials $P$,$Q$,$P-Q$ are all positive. So there exists some real $R$ such that $P,Q,P-Q$ are all strictly increasing at the interval $(R, +\infty)$. Let $P(R+1)=s$, and take some integer $N>s$. Then there exists some real $u>v>R+1$ such that $P(u)=N+1, P(v)=N$. Since $P(u)$ and $P(v)$ are all integers, $Q_n(u)$ and $Q_n(v)$ are integers. Also $u>v>R \implies 0<(P(u)-Q_n(u))-(P(v)-Q_n(v))=1-(Q_n(u)-Q_n(v)) \implies 0<Q_n(u)-Q_n(v)<1$, a contradiction. Case 2 : If the leading coefficient of $Q$ is negative, then there exists some real $R$ such that $P,-Q,P+Q$ are all strictly increasing at the interval $(R,+\infty)$. Let $P(R+1)=s$, and take some integer $N>s$. Then there exists some real $u>v>R+1$ such that $P(u)=N+1, P(v)=N$. Since $P(u)$ and $P(v)$ are all integers, $Q_n(u)$ and $Q_n(v)$ are integers. Also $u>v>R \implies 0<(P(u)+Q_n(u))-(P(v)+Q_n(v))=1+(Q_n(u)-Q_n(v)) \implies -1<Q_n(u)-Q_n(v)<0$, a contradiction. So $Q_n$ is a constant polynomial. Let $P(x)=\sum_{j=0}^{k}a_jx^j$, then $Q_n(x)=\sum_{j=0}^{k} a_j(n^j-n^n)x^j=C_n$ for all positive integer $n$ and real $x$ where $C_n$ is a constant depending on $n$. So $a_1=a_2= \cdots =a_{k-1}=0$, and $P(x)=Ax^k+C$ for some integers $A$ and $C$. (We assumed that $A$ is a integer because we assumed that the leading coefficient of $P$ is postitive at first, so we have to flip signs to cover that case.) If $|A|>1$, then take reals $s,t$ such that $s^k=t^k=\frac{1}{|A|}$, then $P(s)$ and $P(t)$ are all integers but $P(st)$ is not. Hence $|A|=1$, as desired.

This was my solution during the contest. (almost the same with official solution 2) The answer is $P(x) = \pm x^d + a$, which is indeed a solution. For the solution, we will assume that $P(0)=0$ (If $P(x)$ works, so does $P(x)-a$, where $a\in\mathbb{Z}$), and we will exclude constant functions. Lemma $f(x) \in \mathbb{Z}[x]$ satisfies $\forall x \in \mathbb{R}$ such that $$f(x)\in\mathbb{Z} \Longrightarrow x\in\mathbb{Q}$$then, $f(x)=cx$ Proof Let $c$ the leading coefficient of $f$. If $deg f>1$ we can find an interval $(x,x+\frac{1}{c+1})$ such that $f(x+\frac{1}{c+1})-f(x)>2$ and for every $y\in(x,x+\frac{1}{c+1})$, $f(y)=f(y')\Longrightarrow y=y'$. Notice that by the given conditions, there exist $q_1,q_2\in\mathbb{Q}$ such that $f(q_1),f(q_2)\in\mathbb{Z}$ and $f(x)<f(q_1)<f(q_2)<f(x+\frac{1}{c+1})$, but this leads to contradiction since $\frac{1}{c+1}>|q_2-q_1|>\frac{1}{c}$ Now, let $P(x)=a_nx^n+\dots+a_1x (a_n\neq0)$, and let $x \in \mathbb{R}$ such that $P(x) \in \mathbb{Z}$. Since $f(x),f(2x), \dots,f(nx) \in \mathbb{Z}$. $$\sum_{k=1}^n (a_kt^k)x^k \in \mathbb{Z}\text{ for } t=1,2,...n \Longrightarrow a_i \neq 0\text{ then }x^i \in \mathbb{Q}$$(The vectors $(1,1,\dots,1),(2,2^2,\dots,2^n),\dots,(n,n^2,\dots,n^n)$ are independent in $\mathbb{R}^n$, just Vandermonde Determinant ) Let $d$ be the smallest natural number such that $x^d\in\mathbb{Q}$ and let $P(x^d)=Q(x)$ ($Q(x)\in\mathbb{Z}[x]$) and by our lemma, $$Q(x)=cx\Longrightarrow P(x)=cx^d\Longrightarrow P(x)=\pm x^d$$,so we are done.

Assume that $P$ is a non-constant solution. Let $P(x) = a_d x^d + a_{d-1} x^{d-1} + \ldots + a_0$ (so $a_d \neq 0$). Notice that if $P$ is a solution, then so does $Q\equiv -P$, so WLOG assume $a_d>0$. We will use the following lemma. Lemma 1: For any polynomial $Q\in\mathbb{R}[X]$ with degree $d$ and leading coefficient $a$, and for any $n>d$, $$\sum_{i=0}^d (-1)^{d-i} {d\choose i} Q(x+i) = d!a, \quad \sum_{i=0}^n (-1)^{n-i} {n\choose i} Q(x+i) = 0$$ Proof. Notice that $\forall n\in\mathbb{N}$, any polynomial of degree at most $n$ is a solution of a recursive equation $\sum_{i=0}^n (-1)^{n-i} {n\choose i} b_{k+i} = c$ for some real $c$ and those of degree at most $n-1$ is a solution at $c=0$. This means we have proved the second equality and for the first equality, we can pick $Q(x)=d!a{x\choose d}$. Also it becomes sufficient to only prove that $\sum_{i=0}^d (-1)^{d-i} {d\choose i} {i\choose d} = 1$. But this is trivial. Lemma 2: $\boxed{\sum_{i=0}^d (-1)^{d-i} {d\choose i} P(xi) = d! a_d x^d}$ Proof. By lemma 1, for each $0\leq n<d$, $\sum_{i=0}^d (-1)^{d-i} {d\choose i} a_n (xi)^n=0$ and $\sum_{i=0}^d (-1)^{d-i} {d\choose i} a_d (xi)^d = d! a_d x^d$. Combining this completes our proof. Lemma 3: If $t$ is a real number such that $P(t)$ is an integer, then $d! a_d t^d$ is an integer. Proof. Since $P(n)$ is an integer for every $n \in \mathbb{Z}$, $P(nt)$ is also an integer for every $n \in \mathbb{Z}$ and thus using lemma 2, we get that $d! a_d t^d$ is an integer. Lemma 4: If $t$ is a real number such that $P(t)$ is an integer, then $t^d$ is an integer. Proof. By induction, $P(t^n)\in\mathbb{Z}$ for each $n\geq 1$ and thus by lemma 3, $d! a_d t^{nd}$ is an integer. By computing their p-adic valuation, we obtain that $t^d$ is an integer. Now, consider the continuous function $f(x)=P(\sqrt[d]{x})=a_d x+\sum_{i=0}^{d-1} a_i x^{\frac{i}{d}}$ for $x>0$. By lemma 4, $f(t)\in\mathbb{Z}$ implies $t\in\mathbb{N}$. Since $f(x)\rightarrow \infty$ when $x\rightarrow \infty$, we can pick $M$ big enough such that $f(M)$ is an integer, $f(x)$ is strictly increasing at $x>M$ and $f(x+2)-f(x)>1$ for every $x>M$ ($a_d\geq 1$). Let $f(M)=M+c$. By IVT, for each $n\geq M$, there exist $x$ real such that $n<x<n+2$ and $f(x)$ is an integer, which means $x=n+1$ and thus $f(n)\in \mathbb{Z}$ for each $n\geq M$. But by IVT again, $f(n+1)-f(n)=1$ and thus by induction $f(n)=n+c \forall n\geq M$. Hence, $P(x)=f(x^d)=x^d+c$ for infinitely many values of $x$, and thus $P(x)=x^d+c$. We're done. Note: the solution $P(x)=c$ works even if $c$ is not an integer, but for $P(x)=\pm x^d+c$, $c$ is necessarily an integer. Hope the latex doesn't fail...

Here is another solution using v_Enhance's Lemma: That there exist arbitrarily large $t > 0$ with $P-t$ irreducible over $\mathbb Z[x]$. (The proof is to take $P-t$'s constant term to be a large prime.) Write $P(x) = a_0+a_1x+\cdots + a_nx^n$; and assume $a_n > 0, n > 0$. Now take some $t$ with $P-t$ irreducible, and $t$ sufficiently large so that $t\in P(\mathbb R)$, and let $P(s) = t$. The key is that $P-t$ is irreducible over $\mathbb Q[x]$ (by Gauss's Lemma), and hence $P-t$ is the minimal polynomial of $s$ in $\mathbb Q[x]$. Now, take $Q(x) = P(2x)-2^nP(x)$; by examining leading term we conclude $\deg Q < \deg P$. On the other hand, $Q(s) = P(2s)-2^nP(s)\in \mathbb Z$, since $P(2s)\in \mathbb Z$ from $P(2) \in \mathbb Z$ and $P(s)\in \mathbb Z$. Hence, $Q-k$ also has root $s$, and since $P-t$ is the minimal polynomial of $s$ we conclude $P-t\mid Q-k$. But $\deg(Q-k) < \deg (P-t)$, so $Q-k = 0$. This implies that the nonconstant coefficients of $Q$ vanish, which implies in turn that all of the coefficients of $P$ vanish, except the leading and constant ones. Hence $P(x) = ax^n+c$ for some $a,c$, and now it is easy, for example by taking $s = t = \frac{1}{a^{\frac 1n}}$, to show that $a = 1$ (recall $a>0$) and that the answer must be $\boxed{\pm x^n+c}$.

The below is probably an abuse of notation, but it got me a 7 in-contest so yay We claim the answer is all $P(x) = \pm x^n+a$ for integers $a$ and $n\ge 0$; clearly these all work. Let $S$ be the set of real numbers $r$ such that $P(r) \in \mathbb Z$. Lemma: If $r\in \mathbb Q \cap S$ then $r\in \mathbb Z$. Proof: Write $P(x) = a_nx^n + a_{n-1}x^{n-1}+ \dots + a_0$. Suppose $r$ is not an integer, so there is some $p$ dividing the denominator of $r$ when written in reduced form. Then $r\in S \implies r^k\in S$ for all $k\ge 0$, so $P(r^k) = a_n r^{nk} + a_{n-1} r^{(n-1)k} + \dots + a_0$, and for sufficiently large $k$ we have $v_p (a_n r^{nk}) < \min (0, v_p (a_{n-1}r^{(n-1)k}), \dots, v_p (a_0))$, so we have $v_p (P(r^k))<0$, implying $r^k\not \in S$, contradiction. Therefore $r\in \mathbb Z$. Now let $\deg P=d$. If $d=0,1$ the problem is trivial and matches the answer given above. Otherwise assume $d\ge 2$. Consider any element $r\in S$, so by the condition we have $2r, 3r, \dots, (d+1)r\in S$. Then by the Lagrange Interpolation Formula, we have $$P(x) = \displaystyle\sum_{i=1}^{d+1} P(ir) \dfrac{\prod_{j\neq i} (x-jr)}{\prod_{j\neq i} (ir-jr)},$$so since $P\in \mathbb Z[x]$, the leading coefficient $\dfrac{1}{r^d}\displaystyle\sum_{i=1}^{d+1} P(ir) \dfrac{1}{\prod_{j\neq i} (i-j)}$ is an integer, and thus $r^d\in \mathbb Q$ for every $r\in S$. Since $r\in S\implies r^d\in S$, the lemma tells us that actually $r^d\in \mathbb Z$. WLOG shift $P$ so that $P(0)=0$ and flip signs so that $\lim_{x\to \infty}P(x)=\infty$. Now consider a large positive integer $N$. Then for each integer $0\le m\le P(N)$, by IVT there exists some $r$ with $P(r) =m$, so there are at least $P(N) = O(N^d)$ elements of $S$ in the interval $[0,N]$, and all such numbers are of the form $\sqrt[d]{n}$ for $0\le n \le N^d$ by our earlier observations. Now note that for each $2\le k\le d$, there are $O(N^{d/k})$ perfect $k$th powers between $0$ and $N^d$, so in total we have $O(N^{d/2} )+O(N^{d/3})+\dots + O(N^{d/d}) = O(d\cdot N^{d/2})$ numbers between $0$ and $N^d$ which are some sort of $k$th power for $2\le k\le d$. In particular, this is less than $O(N^d)$, so for large $N$ there must be some element $r$ of $S$ such that $r^d$ is not a perfect $k$th power for any $2\le k\le d$. Then it follows that $x^d-r^d$ is the minimal polynomial of $r$ in $\mathbb Z$, so since $P(r)$ is an integer we deduce that $P(x)$ is of the form $ax^d+b$ for integers $a,b$. Since $x=a^{-1/d}\in S$, we deduce that $x=a^{-1}\in S$, so from $P(a^{-1})\in \mathbb Z$ we get $a=\pm 1$. Therefore $P(x) =\pm x^d+b$ as claimed.

Here is an other solution: Let $P(x)=a_nx^n + \dots +a_1 x +a_0$.WLOG assume that $a_n>0$ and $a_0=0$,as we can replace $P$ with $-P$ or $P-r ,r \in \mathbb{Z}$. By here (post #10) we get that there are $m,k \in \mathbb{Z}$ such that $P(2x)=mP(x)+k$.Comparing the coefficients of both sides implies that $a_{n-1}=a_{n-2}= \dots =a_1=0 ,m=2^n $ so $P(x)=a_n x^n$,but it's easy to see that $a_n=1$ (just let $r=\frac{t}{\sqrt[n]{a_n}},s=\frac{u}{\sqrt[n]{a_n}}$,where $t,u$ are relatively prime to $a_n$).Working backward with our previous assumptions,we get the general solution $\boxed{P(x)=\pm x^n +c, n \geq 0}$

The answer is $P(x)=\pm x^n+b$ for any constant $b$. It is easy to see that this works, since $P(st)-b=(P(s)-b)(P(t)-b)+b$. We'll now show that no other $P$ work. WLOG, we can take $P(0)=0$, and we can flip signs to make $\lim_{x\to\infty}P(x)=-\infty$. The crux of the solution is the following very intuitive lemma. Lemma: There exists arbitrarily large $n\in\mathbb{Z}$ so that $P(x)+n$ is irreducible over $\mathbb{Z}[x]$. Proof of Lemma: The idea is to take $n$ to be a very large prime (much larger than $(\deg P)\times\text{coefficients of }P$ works I think). Firstly, $n$ is very large, so if $r$ is a root of $P(x)+n$, then by the triangle inequality applied to $P(r)=-n$ gives $|r|>1$. If we had \[P(x)+n=Q(x)R(x)\]for $Q(x),R(x)\in\mathbb{Z}[x]$, then by letting $x=0$ we get WLOG $R(0)=\pm 1$. If $a$ is the leading coefficient of $R$ which is an integer, we see that the product of the roots of $R$ is $1/|a|\le 1$, but all the roots have $|r|>1$, which is a contradiction. Therefore, $P(x)+n$ is irreducible. $\blacksquare$ Note that as $x\to\infty$, $P(x)\to -\infty$, so we can select sufficiently large $n$ so that $P(x)+n$ has a real root. Let this root be $t$. We see that $P(t)=-n\in\mathbb{Z}$. But $P(2)\in\mathbb{Z}$, so therefore $P(2t)\in\mathbb{Z}$, so $P(2t)+m=0$ for some $m$. Since $P(x)+n$ is irreducible, it is a minimal polynomial for $t$ (minimal polynomial is unique up to scaling). Therefore, a minimal polynomial for $2t$ is $Q(x)\equiv P(x/2)+n$. But $P(2t)+m=0$, and the degree of $P(x)+m$ is the same as $Q(x)$, so we must have \[Q(x)=k(P(x)+m)\]for some $k$. Since $P(0)=0$, we see then that \[P(x/2)=kP(x)\]for some $k$, and for all $x$. If $P(x)$ has at least two terms, then it is easy to see that this can never happen, so $P(x)=a x^n$ for some $a,n$. Then, $P(st)=P(s)P(t)/a$, so by taking $P(s),P(t)$ to be integers relatively prime to $a$, we see that $|a|=1$, as desired. $\blacksquare$

If $P(x)$ works, then $-P(x)$ does as well, so WLOG the leading coefficient of $P$ is negative. Then, for $N\gg 1$, $P(x)-N$ has a real root. Furthermore, if we choose $N$ such that the constant term of $P(x)-N$ is a very large prime, then it is irreducible by Ostrowski's Criterion. Hence, if $P(s)=N$, it's minimum polynomial is just $P(x)-N$. Now, as $P(2),P(s)\in\mathbb{Z}$, $P(2s)=k\in\mathbb{Z}$. As $2s$ is a root of $P(x)-k$, we must have that it's minimum polynomial, $P(2x)-N$, divides $P(x)-k$. As they have the same degree, they must be multiples of each other. However, suppose $P(x)=a_nx^n+\ldots+a_1x+a_0$, and $\exists a_i\neq 0$, $0<i<n$. Then, the ratio of the coefficients of $x^n$ and $x^i$ in $P(x)-k$ is $\frac{a_n}{a_i}$ while it is $\frac{a_n}{a_i}\cdot 2^{n-i}\neq \frac{a_n}{a_i}$ in $P(2x)-N$. Therefore, such $i$ does not exist, and $P(x)$ must be either constant or of the form $ax^n+b$ Of course, all constant functions work, and $ax^n+b$ works iff $ax^n$ works. If $P(x)=ax^n$, then $x=a^{-1/n}$ yields an integer, so $x^2=a^{-2/n}$ should as well. Hence, $1/a\in\mathbb{Z}\implies a=\pm 1$. So, our complete set of solutions is $P(x)=c$, $P(x)=\pm x^n+c$, both of which are easily verified.

The answer is $\pm x^e+c$, which clearly work. Without loss of generality $P$ has positive leading coefficient. Lemma: [MOP 2007] There are arbitrarily large $u>0$ such that $P(x)-u$ is irreducible. Proof. Let $Q(x)=P(x)-u=a_nx^n+\cdots+a_0$. We let $a_0=-p$ with $p$ a very large prime. Then if $Q$ is reducible, one of the factors $R$ has a constant term of $\pm1$. Its roots have product with magnitude at most $1$, so $Q$ has a root on or inside the unit circle. But if $p>|a_1|+|a_2|+\cdots+|a_n|$ then $Q$ does not have roots on our inside the unit circle by triangle inequality. $\blacksquare$ Take some $u$ as in the above lemma, and suppose $P(\alpha)=u$. Then $P(2\alpha)=v$ is an integer. We have \[P(x)-u\mid P(2x)-v\]since $P(x)-u$ is irreducible and $\alpha$ is a root of both. This immediately implies $P$ has at most one nonconstant term, so if $P$ is nonconstant, we have $P(x)=ax^e+c$ for some integers $a>0$ and $c$. Now take $s=t=a^{-1/e}$. This gives $P(st)=1/a+c$ is an integer, so $a=1$, and we are done.

Since there are bunch of solution, so I would write only the sketch of proof. (You can mix some solutions above to make this, so.. maybe redundant.) Let $S$ be the set of $x$ that $P(x)$ is integer. Since $P(x)$ has integer-coefficient, $S$ contains $\mathbb{Z}$. Step1) When $S=\mathbb{Z}$, $P(x)=\pm x + c$ for some integer $c$. (every difference of $P(n+1)-P(n)$ is $\pm 1$ or $0$.) Step2) If $S$ contains rational number $q$, $q$ is integer. (Substitute $s^k$ for sufficiently large $k$) Step3) If $S$ contains irrational number $\alpha$, $\alpha^d \in \mathbb{Z}$ where $d$ is the degree of the polynomial. Therefore, every $\alpha$ can be written as $\pm \sqrt[e]{a}$ for some $e$ dividing $d$ and $a \in N$. (Use well-known identity for $\sum_{i=1}^{d} (-1)^{d-i} {d \choose i} i^k$ and with Step2) Step4) There exists, $\alpha$ with $d=e$, $P$ should in forms of $P(x)=b(x^d - a)$ and actually $b=\pm 1$. Step5) If every $e<d$, the number of positive element in $S$ smaller than $n$ is at most $n^{d-1}+...+n$. However, by continuity of $P$, there are at lesat $|P(n)-P(0)|-1$ distinct elements in $S$. This cannot holds for large $n$. Therefore, the answer is $\pm x^d + c$ for some integer $c$.

This is actually quite easy for a #5. Should have solved this two years ago The answer is $P(x) = \pm x^n+c$ for some integers $c,n$ where $n\geq 0$. All of these clearly work. First, we make a bunch of trivial optimizations. By negating $P$ if necessary, we can assume that the leading coefficient of $P$ is $a>0$. By shifting $P$, we can assume that $P(0)=0$. Assume furthermore that $P$ is non-constant. Let $n=\deg f$. For each real number $r$, define $\mathrm{ord}(r)$ as the minimum positive integer $k$ such that $r^k\in\mathbb{Q}$ and $\infty$ if none exists. First we prove the following claim. Claim: If $r\in\mathbb{R}$ such that $P(r)\in\mathbb{Z}$. Then we have the following facts. $Cr^n\in\mathbb{Z}$ for some constant $C$. If $\mathrm{ord}(r)\nmid k$, then the coefficient of $x^k$ of $P$ is zero. Proof: By the condition, $P(2r), P(3r),\hdots, P(nr)\in\mathbb{Z}$. Hence using Lagrange Interpolation formula at points $0,r,2r,\hdots,nr$, we get $$P(xr) = \sum_{i=0}^n P(ir)\prod_{\substack{j\in\{0,1,\hdots,n\} \\ j\ne i}} \frac{x-j}{i-j} \in \frac{\mathbb{Z}[x]}{(n!)^2}.$$Thus comparing the leading coefficients gives i. For ii., assume that the coefficient of $x^k$ is $b\ne 0$, then by comparing $x^k$-coefficient in above, $r^kb\in\mathbb{Q}$. Since $b\in\mathbb{Z}$, this gives contradiction to the definition of $\mathrm{ord}$. $\blacksquare$ Next, we use density argument to show that $P$ must be in form $ax^n$. Claim There exists $r$ such that $\mathrm{ord}(r) = n$ and $P(r)\in\mathbb{Z}$. Proof: Assume not. Let $M$ be real number such that $P$ is bijective on $[M,\infty]$. Consider all $r$ such that $P(r)\in\{1,2,3,\hdots,N\}$. Clearly, there are at least $N-M$ such number. However, if $\mathrm{ord}(r) = d$, then we have $C\cdot r^d\in\mathbb{Z}$ by Claim 1. Since $r = O(N^{\frac 1n})$, there exists at most $O(N^{\frac dn})$ such $r$. Hence double counting gives $$N-M \leq \sum_{\substack{d\mid n \\ d\ne n}} O(N^{\frac dn})$$which is a clear contradiction. $\blacksquare$ The two claims above force $P(x)=ax^n$. To show that $a=1$, just pick $s=t=a^{-\frac 1n}$ to get the contradiction.

We claim $P=\pm x^n+c$, which clearly works. WLOG $P$ has positive leading coefficient $b>0$. Let $n=d=\text{deg}(P)$. First, I prove the lemma everybody else proved (except I assumed leading term positive): Lemma: [USA MOP 2007, Mock IMO #3] There exist arbitrarily large integers $r > 0$ such that $P(x)+r$ is irreducible over $\mathbb Z[x]$. Proof: Shift it such that $P(n)$ is positive for all positive $n$. For a large $m$, consider the numbers $P(1)+a$, $P(2)+a$, ... $P(m)+a$ for $a=1,2, \ldots m^{d+2}$. Then, by the prime number theorem, the average number of primes among these over all $a$ is eventually at least $$\frac{1}{m^{d+2}}\left(0.5 \cdot \frac{m^{d+3}}{\log(m^{d+2})}-(P(1)+P(2) \ldots P(m))\right)$$where the $0.5$ is added so it eventually holds. This grows arbitrarily large, but since if $P=fg$ is prime, then either $f= \pm 1$ or $g = \pm 1$, a reducible $P$ is prime at most $2\text{deg}(f)+2\text{deg}(g)=2d$ times. We can fulfill the arbitrarily large condition by applying this method to $P(x)+r_0$, where $r_0$ is an arbitrarily large positive integer. Now, we apply this to the original problem. If $P(x)-k$ has roots $\alpha_1,\alpha_2, \ldots \alpha_n$, define $Q_k(x) = \sum P(\alpha_i x)$. Note that by the problem condition, if $P(t)$ is an integer then $Q_k(t)$ is an integer. Also, $Q_k$ has degree $\leq n$, and if $Q_k = \sum c_i x^i$, by Newtons Sums, $c_0, c_1, \ldots c_{n-1}$ are independent of $k$ and $c_n$ is nonconstant linear in $k$. Now, take a root $r$ of $P(x)+m$ for some $m$ such that $P(x)+m$ is irreducible (and hence the minimal polynomial of $r$), and note that if $b$ is the leading coefficient of $P$, we have that $c_n P - b Q_k$ is a constant polynomial (or minimality would be contradicted). Hence, the ratio $c_n:c_{n-1}:c_{n-2}: \ldots :c_1$ is the same as the ratio of the corresponding coefficients of $P$, and hence the same for all $k$. Since $c_n$ is a linear function of $k$, we have $c_{n-1}=c_{n-2} \ldots = c_1=0$, so $P=ax^n+b$, and we can easily force and check $a=\pm 1$.

Answer: $P(x)$ is constant or $P(x)=ex^n+d$ where $|e|=1$ is an integer. The given condition seems a bit excessive. Throughout the proof we only use the condition when one of $s,t$ is an integer. We use the full force of the condition only to pin down the leading coefficient. Constant solutions clearly work, so we will be looking only at non-constant polynomials. Assume $P(x)=a_nx^{n}+a_{n-1}x^{{n-1}}+\cdots +a_1x+a_0$. We may assume WLOG that $a_n>0$ (because if $P$ is a solution then so is $-P$). Claim 1: If $P(r) \in \mathbb{Z}$ for some real number $r$ then $r^n \in \mathbb{Q}$. Proof: Consider the integers $P(r),P(2r),\dots P((n+1)r)$. We are searching for rational numbers $b_1,b_2, \dots b_{n+1}$, such that $$b_1P(x)+b_2P(2x)+\cdots +b_{n+1}P((n+1)x)=ax^n$$for some non-zero rational number $a$. This is equivalent to solving the following $n+1$ equations in $\mathbb{Q}$: $$\sum_{i=1}^{n+1}b_ii^k=0 \ \ for \ \ k=0,1,\dots, n-1$$$$\sum_{i=1}^{n+1}b_ii^n= \frac{a}{a_n}$$But we can see that the coefficient determinant of the above system is just the Vandermonde determinant on $1,2,\dots,n+1$, which is clearly non-zero. Hence there exists a solution in $\mathbb{Q}$. Now we put $x=r$ in the above equation to get $r^n \in \mathbb{Q}$. $\blacksquare$ Now assume FTSOC that $a_i \neq 0$ for some $i \in \{1,2,\dots ,n-1 \}$. Claim 2: $P(x)-k$ is reducible in $\mathbb{Z}[x]$ for all sufficiently large $k \in \mathbb{Z}$ (in particular $k>P(0)$). Proof: Let $k>P(0)$ be any integer. Clearly the equation $P(x)-k=0$ has a real root; let that root be $r$. Let $a_nr^n=l \in \mathbb{Q}$. Hence $r$ is also the root of the following polynomial: $$a_{n-1}x^{n-1}+\cdots+a_1x+a_0+l-k=0$$which is non-constant, has rational coefficients, and degree at most $n-1$. So $P(x)-k$ is reducible in $\mathbb{Q}[x]$, and by Gauss's lemma, also in $\mathbb{Z}[x]$. $\blacksquare$ We are ready to obtain a contradiction. Choose a positive integer $k > \max_{|z| < 2020}|P(z)|$ such that $|P(0)-k|$ is a prime. By Claim 2 we can write $P(x)-k=f(x)g(x)$ where $f,g$ are non-constant. So $P(0)-k=f(0)g(0)$ $\implies$ one of $|f(0)|,|g(0)|$ is $1$. But by the choice of $k$, all roots of $P(x)-k$ have modulus greater than $1$, so product of any subset of roots cannot have modulus $1$, contradiction. Hence we can write $P(x)=ex^n+d$ for some integers $e,d$. Now $P(|e|^{-\frac{1}{n}})=d \pm 1 \in \mathbb{Z}$ so by the condition $P(|e|^{-\frac{2}{n}})=d \pm \frac{1}{e} \in \mathbb{Z}$, which implies that $e= \pm 1$, and we are done. $\blacksquare$

The answer is $P(x) = \pm x^{n} + c$ and $P(x) = c$ for integers $n$ and $c$. We will prove the following two lemmas: Lemma 1: If $f$ was a polynomial with $|f(0)|$ a prime number, and all the roots of $f$ have absolute value greater than $1$, then $f$ is irreducible over $\mathbb{Z}$. Proof: Assume $f$ was reducible; let $f = g\cdot h$. Since $|f(0)|$ is prime, this means the product of the constant terms of $g$ and $h$ is prime, so the constant terms of one of $g$ or $h$ is $1$; wlog assume $|g(0)| = 1$. Then, by vietas formula, the product of the roots of $g$ has absolute value at most $1$, so some root of $g$ has absolute value less than $1$. This is a contradiction since roots of $g$ are roots of $f$, and all rots of $f$ have absolute value greater than $1$, which implies $f$ is irreducible. Lemma 2: For any polynomial $P(x)$, there exists an integer $k$ such that $P(x) - k$ is irreducible. Let \[P(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + \ldots a_{1}x + a_{0}\]Consider some $k$ such that $|P(0) - k|$ is a prime number. For large enough $k$, if $z$ is a root of $P(x) - k$, so $P(z) = k$, then I claim $|z| > 1$. This is because, if $|z|\leq 1$, then for large enough $k > |a_{0}| + \ldots + |a_{n}|$, we have \[|P(z)| = |a_{n}z^{n} + \ldots + a_{0}| \leq |a_{n}z^{n}| + |a_{n-1}z^{n-1}| + \ldots + |a_{0}| \leq |a_{n}| + |a_{n-1}| + \ldots + |a_{0}| < k\]which is a contradiction since $P(z) = k$. Thus, for large enough $k$, we have all the roots of $P(x) -k$ have absolute value greater than $1$. Letting $|P(0) - k|$ be prime results in $P(x) - k$ be irreducible by lemma 1. Now we solve the problem. Since $P$ is an integer polynomial, we have $P(x) \in \mathbb{Z}$ for $x\in \mathbb{Z}$. Again, we let \[P(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + \ldots a_{1}x + a_{0}\]If $P(s)\in \mathbb{Z}$, then by our condition, we also have $P(2s), P(3s), \ldots P(ns) \in \mathbb{Z}$ by our condition. Now, we will choose $x_{0}, x_{1}, \ldots x_{n-1}$ that satisfy the following condition \[\sum_{j=1}^{n}x_{j}j^{i} = 0 \text{ for } 0\leq i < n\]and we also have $\sum_{j=1}^{n}x_{j}j^{n} \neq 0$. This is possible, which means we can sum a linear combination of $P(s), P(2s), \ldots P(ns)$ to get $kx^{n}\in \mathbb{Z}$ for some integer $k$. This implies $x^{n}$ is rational. We can do the same thing for every $i$ where $a_{i}\neq 0$ to get $x^{i}$ is rational. Now, let $S$ be the set of integers such that for $t\in S$, we have $a_{t}\neq 0$. Let $d$ be the $\gcd$ of all the elements in the set, and $y = x^{d}$. Furthermore, let $Q$ be a polynomial such that $Q(y) = P(x)$. Since for all elements $t\in S$, we have $x^{t}\in\mathbb{Q}$ if $P(x)\in \mathbb{Z}$, we must have $x^{d}\in \mathbb{Q}$, so if $Q(r)$ is an integer, this means $r$ is rational. However, by lemma 2, we can choose some number $k$ such that $Q(r) - k$ is irreducible. If $Q(y)$ is not a linear function, then this gives a contradiction, since the root $z$ of $Q(r) - k$ can not be rational, but then $Q(z)$ is an integer. We conclude that $Q$ is a linear function. Now, since $Q$ is linear, let $Q(y) = ay + b$. Replacing $y = x^{d}$ gives $P(x) = ax^{d} + b$. If $a\neq 0, 1, -1$, then consider a number $s$ such that $s^{d} = \frac{1}{a}$. Then, this means $P(s^{2})\in \mathbb{Z}$, but \[P(s^{2}) = a(s^{2})^{d} + b = a\cdot \frac{1}{a^{2}} + b = b + \frac{1}{a} \not\in\mathbb{Z} \]Therefore, the only possible polynomials are $P(x) = \pm x^{n} + c$ or $P(x) = c$.

The answer is all $P(x)=\pm x^n+c$, which obviously satisfy the condition. We now show that they are the only ones. Suppose $P(x)=\sum_{i=0}^ma_ix^i$ and there is $k$ coefficients among $a_1,...,a_m$ which are nonzero. Now define the sequence as follows: $$P_0=P, P_i=P_{i-1}(2x)-2^{\deg P_{i-1}}P(x)$$Then $P_k=ax^p$ where $p<m$ and $a\in\mathbb Z$. Notice that by induction it is easy to see that $P_0(x)\in\mathbb Z$ implies $P_k(x)=0$. Therefore, if $P(x)$ is an integer then $x=\left(\frac{n}{a}\right)^{\frac{1}{p}}$. We now show that there exists some integer $d$ such that $P(x)-d=0$ has a real root and but no roots of the form $$x=\left(\frac{n}{a}\right)^\frac{1}{p}$$which will be a contradiction. Let $\displaystyle y_n=\left(\frac{n}{a}\right)^\frac{1}{p}$. Indeed WLOG assume $P$ has negative leading coefficient then we can take a constant $k$ such that $P(x)-d$ has a real root for all $d>k$. Then it suffices to find sufficiently large $c$ such that $P(y_{n-1})<c<P(y_n)$. But we have $$P(y_n)-P(y_{n-1})=O((y+1)^\frac{m}{p}-y^{\frac{m}{p}})$$which tends to infinity as $y$ tends to infinity. Hence we can always find such an integer, this implies $P$ must be a monomial and the proof can easily be completed.

Let $\deg P = n$, and let $z\in\mathbb{R}$ such that $P(z)\in\mathbb{Z}$. Suppose $P(x) = a_nx^n + \dots + a_1x + a_0$ where $a_0,\dots,a_n$ are integers. WLOG $a_n>0$, changing $P$ to $-P$ when needed. Let $d$ be the largest positive integer that divides all $m$ for which $a_m\neq 0$. Furthermore, define a unique $Q(x)\in\mathbb{Z}[x]$ such that $Q(x^d)\equiv P(x)$. Claim. $z^d$ must be rational. Proof. Since $P(z)$ is an integer, and $P(k)$ is an integer for any integer $k$, we see that $P(z), P(2z), P(3z), \dots, P((n+1)z)$ are all integers. This means that: \begin{align*} &a_nz^n + a_{n-1}z^{n-1} + \dots + a_1z + a_0 \in \mathbb{Z} \\ &2^na_nz^n + 2^{n-1}a_{n-1}z^{n-1} + \dots + 2a_1z + a_0 \in \mathbb{Z} \\ & \dots \\ &(n+1)^na_nz^n + (n+1)^{n-1}a_{n-1}z^{n-1} + \dots + (n+1)a_1z + a_0 \in \mathbb{Z}. \end{align*}Because the Vandermonde determinant \[\left|\begin{matrix} 1^n & 1^{n-1} & \dots & 1^1 & 1^0 \\ 2^n & 2^{n-1} & \dots & 2^1 & 2^0 \\ \dots & \dots & \dots & \dots & \dots \\ (n+1)^n & (n+1)^{n-1} & \dots & (n+1)^1 & (n+1)^0 \\ \end{matrix}\right| = \prod_{1\le i < j \le n+1} (j-i) \neq 0,\]the vectors $(k^n, k^{n-1}, \dots, k, 1)$ where $1\le k\le n+1$ are linearly independent in $\mathbb{Q}^{n+1}$, so there exists a $\mathbb{Q}$-linear combination of these vectors that produce the standard basis. This means that $a_kz^{k} \in\mathbb{Q}$ for any $0\le k\le n$, which implies the claim by definition of $d$. $\square$ Thus, we see that $Q(z^d) = P(z)$ is an integer. Let $z^d = \frac{a}{b}$ where $\gcd(a,b) = 1$, by rational root theorem on the integer polynomial $Q(x) - P(z)$, we know that $b\mid a_n$. This implies that any $z\in Q^{\text{pre}}(\mathbb{Z})$ (here assume $z>0$) must be in the form $\frac{a}{a_n}$ for some integer $a>0$. This implies $\deg Q = 1$ for density reasons, so $P(x) = a_nx^n + a_0$. Simple testing shows that $a_n = \pm 1$, so we are done.

We claim that $P(x) = \pm x^n + c$. To show that these are the only solutions, assume $P$ is non-constant and note that by considering $-P$ instead of $P$ if necessary, we may assume the leading coefficient of $P$ is positive. Since $P(2)$ is an integer, we have that for any $s$ such that $P(s)$ is an integer, so is $P(2s)$. Hence, if we write $P(x) = a_nx^n + \ldots + a_1x + a_0$ and \begin{align*} Q(s) := P(2s) - 2^nP(s) = a_{n-1}(2^{n-1} - 2^n)x^{n-1} + \ldots + a_1(2^1 - 2^n)x + a_0(1 - 2^n), \end{align*}then for any $s$ such that $P(s)$ is an integer, so is $Q(s)$. For large values of $X$, the number of reals $s \in [0, X]$ such that $P(s)$ is an integer is asymptotically a constant times $X^n$. (Think of the graph of $P$.) Meanwhile the corresponding value of $Q$ is, assuming $Q$ is non-constant, at most a constant times $X^{\deg(Q)} \le X^{n-1}$. This leads to a contradiction for large $X$. Hence $Q$ is constant, so $P$ is a binomial $a_nx^n + a_0$. From here it is easy to finish.

Thanks for seeing this. Please upvote, if you found the solution nice.

a somewhat different solution using two nice lemmas. Lemma 1: if $P(x) \in R[x]$ has the property that $\forall n\in \mathbb{Z}, P(n)\in \mathbb{Z}$ then there exist integers $a_0,\dots, a_d$ such that. $$P(x)= a_d \binom{x}{d} + a_{d-1} \binom{x}{d-1}\dots +a_0 \binom{x}{0}$$proof is by induction and using $P(n+1)-P(n)$ Lemma 2: if $P(x) \in Q[x]$ has the property of lemma 1 and that if $r>0$ and $P(r) \in \mathbb{Z} $ then $ r\in \mathbb{Q}$. then $P$ must be linear. proof: WLOG let the leading coefficient of $P$ be positive. similar to the proofs above we know that there are arbitrarily large $k$ such that $P(x)-k$ is irreducible. if we choose $k$ large enough, it must have a positive real root $z$. now, $P(z) \in \mathbb{Z}$ but $z$ must be irrational unless $P$ has degree $1$. we are done. now, let $t$ be a real number such that $P(t)\in \mathbb{Z}$. look at $P(tx)$, we know that it has the property of lemma 1 hence it must be in $Q[x]$. Set $P(x)=a_n x^n+\dots+a_0$, let $m>0$ be the smallest number larger than $0$ such that $a_m\neq0$. because $P(tx)\in Q[x]$ then $t^m\in \mathbb{Q}$. now $m'$ be the smallest number that if $P(r)\in \mathbb{Z}$ then $r^{m'}\in{Q}$, such a thing exists because we know that it is at most $m$, call this property *. now because $P(rx) \in \mathbb{Q}[x]$ we know that if $a_i \neq 0$ then $m' \mid i$ so there is a $Q(x) \in \mathbb{Q}[x]$ such that $P(x)=Q(x^{m'})$. now according to *, we know that $Q$ has the properties of lemma 2, so it must be linear! so now we have $P(x)=ax^n+b$. from here on out it is quite simple to prove that $a=1$ or $a=-1$ by setting $\frac{1}{a^{\frac kn}}$. seeing that these polynomials work isn't that complicated. we are done

very stupid/funny The answer is $P(x)=\pm x^n+c$ where $n \geq 0$ (in particular, every constant integer polynomial is a solution), which clearly work. Let $P(x)=a_nx^n+a_{n-1}x^{n-1}\cdots+a_1x+a_0$. We begin with the following lemma. Lemma: If $n>0$, then there are $O(N^n)$ real numbers $r \in [0,N]$ such that $P(r)$ is an integer. Proof: WLOG let $a_n>0$. Then there exists some constant $M$ such that $P$ is increasing on $[M,\infty)$. Thus for $N>M$, there are $O(P(N)-P(M))$ integers $k$ in the interval $[P(n), P(m)]$, and since each of these integers will have precisely one corresponding solution in $x$ to $P(x)=k$ (by increasing-ness and continuity), we have $O(P(N))=O(N^n)$ total solutions in $[M,N]$ and thus that many in $[0,N]$ as well, since $M$ is fixed. $\blacksquare$ Since $P(x) \in \mathbb{Z}[X]$, $P(2)$ is an integer, so for any real $r$ if $P(r)$ is an integer then $P(2r)$ is as well. Then $Q(r):=P(2r)-2^nP(r)$ is an integer whenever $P(r)$ is, so we should expect $O(N^n)$ real numbers $r \in [0,N]$ such that $Q(r)$ is an integer. On the other hand, clearly $\deg Q<n$, hence we must have $\deg Q=0$. It is easy to see that the coefficient of $x^k$ in $Q(x)$ will be $2^ka_k-2^na_k$, which is nonzero for $k<n$ unless $a_k=0$. Thus any solution will be of the form $P(x)=ax^n+c$, where $a \neq 0$. Now consider $P(\tfrac{1}{\sqrt[n]{|a|}})$, which equals $c \pm 1$ and is therefore an integer. Then $P(\tfrac{1}{\sqrt[n]{a^2}})$ should also be an integer, but this equals $\pm \tfrac{1}{a}+c$, hence $|a|=1$ and we extract the given solutions. $\blacksquare$

Answer is $\pm x^n + c$ and $c$. First, notice you cannot have a root with nonzero magnitude strictly between $-1$ and $1$ by makeshift Kronecker's theorem of $s \to s^2$. WLOG $P(0) = 0$. Then if there is a irrational root $s$, then $P(xs)$ takes on integer values for all integer $x$, so its coefficients must all be rational. Thus $s^d$ where $d$ is the gcd of the nonzero degree set of $P$ must be rational. Thus we may perform a reduction so assume $s$ is rational. ($s' = s^d$). Now by RRT, for large $p$, $P(x) = \pm p$ has roots on the order of $p$ or equal to $1$, which is impossible unless the degree is at most $1$. If degree is $0$, obviously $c$ works. If degree is $1$, solution must be $ax+b$ but then $\frac{1}{a} \to \frac{1}{a^2}$ gives contradiction unless $a = \pm 1$. Checking is trivial, thus solution is $\pm x^n + c$.

Let $S=\{s\text{ }|\text{ }P(s)\in\mathbb{Z}\}$. See that $\mathbb{Z}\in S$ and if $s\in S$ then $ks\in S$ for any integer $k$. Suppose WLOG that $P$ is not constant, which is a solution for the problem, and that the leading coefficient of $P$ is positive (if $P$ works then $-P$ also does work). We prove the following claim: $\textbf{Claim 1:}$ If $s\in S$, then $s^n$ is an integer, where $n=\delta P$. $\textbf{Proof:}$ Let $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$. We see that we can write $a_nx^n$ as a rational linear combination of $P(0),P(x),P(2x),\dots,P(nx)$. This follows from the fact that $$\begin{pmatrix} 1 & 0 & 0 & \dots & 0\\ 1 & 1 & 1^2 & \dots & 1^n\\ 1 & 2 & 2^2 & \dots & 2^n\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & n & n^2 & \dots & n^n\end{pmatrix}\cdot \begin{pmatrix} a_0\\ a_1x\\ a_2x^2\\ \vdots\\ a_nx^n\end{pmatrix}= \begin{pmatrix} P(0)\\ P(x)\\ P(2x)\\ \vdots\\ P(nx) \end{pmatrix},$$and since the determinant of the leftmost matrix in the equation above is nonzero (Vandermonde's Matrix), we get $$\begin{pmatrix} 1 & 0 & 0 & \dots & 0\\ 1 & 1 & 1^2 & \dots & 1^n\\ 1 & 2 & 2^2 & \dots & 2^n\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & n & n^2 & \dots & n^n\end{pmatrix}^{-1}\cdot\begin{pmatrix} P(0)\\ P(x)\\ P(2x)\\ \vdots\\ P(nx) \end{pmatrix}=\begin{pmatrix} a_0\\ a_1x\\ a_2x^2\\ \vdots\\ a_nx^n\end{pmatrix}.$$Furthermore, since the leftmost matrix has only integer entries, its inverse has only rational entries, and thus we get $$a_nx^n=\sum_{0\leq i\leq n}c_iP(ix),$$for some rational numbers $c_0,c_1,\dots,c_n$. By taking $x\in S$ and multiplying both sides of the equation by some integer, we get that there exists a fixed integer $A$ such that for each $s\in S$ we must have $As^n$ an integer. We get that $s^n$ is rational, and writing $s^n=\frac{p}{q}$, with $(p,q)=1$, since $s^2,s^3,\dots\in S$, we have $$A\cdot\frac{p^k}{q^k}\in\mathbb{Z},$$for every positive integer $k$. This implies that $q=1$ and therefore $s^n$ is an integer. $\square$ We have that if $s\in S$, then $s=\sqrt[n]{\ell}$, for some integer $\ell$. We now prove the following claim: $\textbf{Claim 2:}$ There exist a constant $L$ such that if $\ell>L$ is an integer, then $\sqrt[n]{\ell}\in S$. $\textbf{Proof:}$ See that $$P(\sqrt[n]{\ell+1})-P(\sqrt[n]{\ell-1})=2a_n+a_{n-1}((\ell+1)^{\frac{n-1}{n}}-(\ell-1)^{\frac{n-1}{n}})+\dots+a_1((\ell+1)^{\frac{1}{n}}-(\ell-1)^{\frac{1}{n}}),$$which is greater than $1$ for sufficiently large $\ell$, since $a_n\geq1$ and $(\ell+1)^{\frac{k}{n}}-(\ell-1)^{\frac{k}{n}}\to0$, for $k<n$, when $\ell$ goes to infinity. Then the interval $(P(\sqrt[n]{\ell-1}),P(\sqrt[n]{\ell+1}))$ must contain an integer for large $\ell$. Since $P(x)$ is strictly increasing for large $x$, then there must be some $s\in(\sqrt[n]{\ell-1},\sqrt[n]{\ell+1})$ such that $s\in S$, from which $s=\sqrt[n]{\ell}$ and the claim follows. $\square$ Furthermore, repeating the last argument, for $\ell>L$ we must have $$P(\sqrt[n]{\ell+1})=P(\sqrt[n]{\ell})+1,$$from which we get that there exists some integer $C$ such that $P(\sqrt[n]{\ell})=\ell+C$, for large $\ell$. By taking $Q(x)=P(x)-x^n-C$, we can easily conclude that $Q\equiv0$ and therefore $P(x)=x^n+C$, easily deriving the answer; $P$ is constant or $P(x)=\pm x^n+C$. $\blacksquare$

Assume WLOG that $P(0) = 0$, since we can subtract any integer from $P$ while preserving the condition. It is well known that $P(x) - c$ is irreducible for infinitely many positive integers $c$, so, for large enough $c$, we are guaranteed to have a real root $\alpha$ for $P(x) - c$ whose degree is $\deg P$. Then, from the condition, $P(2\alpha) - d = 0$ for some integer $d$. Observe that $\deg 2\alpha = \deg \alpha$, so the minimal polynomial of $2\alpha$ is a scalar multiple of \[2^{\deg P}\left(P\left(\frac{x}{2}\right) - c\right).\]This tells us that $d = c\cdot2^{\deg P}$ and all the coefficients besides the leading coefficient are 0. To finish, we have that $P(x) = ax^n + c$ for some integers $a$, $c$. Observe that \[P\left(\sqrt[n]{\frac{1}{a}}\right)\in{\mathbb Z}\implies P\left(\sqrt[n]{\frac{1}{a^2}}\right) = \frac{1}{a} + c \in{\mathbb Z},\]so $a = \pm 1$, giving the full solution set of \[\boxed{P(x) = \pm x^n + c}.\]

Not bad for the hardest problem on APMO. The answer is $P(x) = \pm x^n + c$, which obviously work. First we need the following lemma: Lemma. For any $f(X) \in \mathbb Z[X]$, there exists infinitely many integers $r$ such that $f(X) - r$ is irreducible in $\mathbb Z[X]$. This is a pretty well-known argument: take $f(0) = p$ for some very large $p$ and note that if $f$ is reducible, it has a root of magnitude $|z| < 1$. But this is impossible by triangle inequality. $\blacksquare$ Now fix $s=2$ and consider some arbitrary $f$. For some $r$ such that $r$ is a root of the irreducible $g(X) = f(X) - c$, this implies that $g(2r)$ is an integer too. Then there exists a $c_1 \in \mathbb Z$ such that $$f(2r) - c_1 = 0.$$Now setting $g_1(X) = f(2X) - c_1$, note that $r$ is a root of $g_1$, and hence by irreducibility of $f$ we have $$g(X) \mid f(2X) - c_1.$$But $g(X)$ and $f(2X)$ have the same degree, so $$f(2X) -c = g(2X) = c_2f(X) + c_1$$for some $c_1, c_2 \in \mathbb Z$. Let $r_1 = r, r_2, \dots, r_d$ be the $\mathbb Z$-Galois conjugates of $r$; by comparing leading coefficients, $c_2 = 2^d$, and by comparing symmetric sums, we have $P_i[r_1, r_2, \cdots, r_d] = 0$ for all $1 \leq i \leq d-1$. Thus $r_2, r_2, \dots, r_d$ are the roots of some $g(X) = \pm x^n + c_1$, as needed.

Let $P(x)=a_dx^d + \dots + a_0$. Note that $P(k)$ is an integer for every integer $k$. In particular, for any real number $s$ such that $P(s)$ is an integer, we have $$\mathbb{Z}\ni \sum_{k=0}^{d} (-1)^k\binom{d}{k}P(ks) = \sum_{k=0}^{d} (-1)^k\binom{d}{k}\sum_{i=0}^d a_is^ik^i = \sum_{i=0}^d a_is^i\sum_{k=0}^{d-1} (-1)^k\binom{d}{k}k^i.$$ By finite differences, the inner sum becomes $0$ for $0\le i\le d-1$, and simplifies to some nonzero multiple of $s^d$. Hence, $s^d$ is rational. In particular if we choose some large $n$ such that $P(x)-n$ is irreducible over $\mathbb{Q}$ and let $s$ be a root of $P(x)-n$, then $s^d=q$ for some rational number $q$. Since $P(x)-n$ is irreducible, $P(x)-n$ is the minimal polynomial of $s$, so we actually require $P(x)-n = a(x^d-q)$ for some integer $a$. In particular, $P(x)$ is of the form $ax^d-b$ for integers $a$ and $b$. If $|a|>1$, then for $s=\sqrt[d]{\frac{1}{a}}$ we have $P(s)=1-b\in\mathbb{Z}$ but $P(s^2)=\frac{1}{a}-b\not\in\mathbb{Z}$. Hence, $P(x)=\pm x^d-b$ or $P(x)=b$ for $b\in\mathbb{Z}$, all of which clearly work.

Answer $P(x)=mx^d+n$ for $m=\pm1$. These work since $P(st)-n=\pm(P(s)-n)(P(t)-n)$. We can shift $P$ by any integer, so make the constant term a large enough prime or its negative, so that $P$ has a real root, and is irreducible by Ostrowski's criterion. Let $r$ be a root of $P$, then $P(2)$ is an integer, so $P(2r)=k$ for integer $k$. Now $P(2x)-k$ has root $r$, but $r$ has minimal polynomial $P(x)$. These have the same degree (unless $P$ is constant, and all constants work), so comparing leading coefficients gives $P(2x)-k=2^dP(x)$, where $d$ is the degree of $P$. Setting $P(x)=a_0+a_1x+\dots+a_dx^d$ gives $a_1=\dots=a_{d-1}=0$ so $P(x)=mx^d+n$ for integers $m,n$. Now $s=t=|m|^{-\frac1d}$ gives $\frac1m$ is an integer, so $m=\pm1$ as desired.