Selection tests for the International Mathematical Olympiad 2013

Suppose there is some value of $n$ such that $p(n)\ne \pm 1$. Let $q$ be a prime divisor of $p(n)$. Because $q=(n+q)-n$ divides $p(n+q)-p(n)$, we deduce that $q$ divides $p(n+q)$. Therefore, $q$ divides both $2^n-1$ and $2^{n+q}-1$, which implies in particular that $q$ is an odd prime. We have $$1\equiv 2^{n+q}\equiv 2^n\cdot 2^q\equiv 2^q\equiv 2\mathrm{mod}q$$ by Fermat's little theorem. This is a contradiction.

Hence, for all values of $n$, $p(n)=\pm 1$. Since $p$ is a polynomial and takes infinitely many times the same value, either $1$ or $-1$, it is constant. This proves that the only polynomials with integer coefficients which have the required property are $p(X)=1$ and $p(X)=-1$.