USAMO

The polynomial $f$ has the required properties if and only if
$$f(x) = c(4x - a_1^2)(4x - a_2^2)\cdots(4x - a_k^2), \quad (*)$$
where $a_1, a_2, \dots, a_k$ are odd positive integers and $c$ is a nonzero integer. It is straightforward to verify that polynomials given by $(*)$ have the required property. If $p$ is a prime divisor of $f(n^2)$ but not of $c$, then $p|(2n-a_j)$ or $p|(2n+a_j)$ for some $j \le k$. Hence $p-2n \le \max\{a_1, a_2, \dots, a_k\}$. The prime divisors of $c$ form a finite set and do affect whether or not the given sequence is bounded above. The rest of the proof is devoted to showing that any $f$ for which $\{p(f(n^2)) - 2n\}_{n \ge 0}$ is bounded above is given by $(*)$.

Let $\mathbb{Z}[x]$ denote the set of all polynomials with integral coefficients. Given $f \in \mathbb{Z}[x]$, let $\mathcal{P}(f)$ denote the set of those primes that divide at least one of the numbers in the sequence $\{f(n)\}_{n \ge 0}$. The solution is based on the following lemma.

Lemma If $f \in \mathbb{Z}[x]$ is a nonconstant polynomial then $\mathcal{P}(f)$ is infinite.

Proof: Repeated use will be made of the following basic fact: if $a$ and $b$ are distinct integers and $f \in \mathbb{Z}[x]$, then $a-b$ divides $f(a)-f(b)$. If $f(0)=0$, then $p$ divides $f(p)$ for every prime $p$, so $\mathcal{P}(f)$ is infinite. If $f(0)=1$, then every prime divisor $p$ of $f(n!)$ satisfies $p>n$. Otherwise $p$ divides $n!$, which in turn divides $f(n!)-f(0)=f(n!)-1$. This yields $p|1$, which is false. Hence $f(0)=1$ implies that $\mathcal{P}(f)$ is infinite. To complete the proof, set $g(x) = f(f(0)x)/f(0)$ and observe that $g \in \mathbb{Z}[x]$ and $g(0)=1$. The preceding argument shows that $\mathcal{P}(g)$ is infinite, and it follows that $\mathcal{P}(f)$ is infinite. $\blacksquare$

Suppose $f \in \mathbb{Z}[x]$ is nonconstant and there exists a number $M$ such that $p(f(n^2)) - 2n \le M$ for all $n \ge 0$. Application of the lemma to $f(x^2)$ shows that there is an infinite sequence of distinct primes $\{p_j\}$ and a corresponding infinite sequence of nonnegative integers $\{k_j\}$ such that $p_j|f(k_j^2)$ for all $j \ge 1$. Consider the sequence $\{r_j\}$ where $r_j = \min\{k_j \pmod{p_j}, p_j - k_j \pmod{p_j}\}$. Then $0 \le r_j \le (p_j-1)/2$ and $p_j|f(r_j^2)$. Hence $2r_j+1 \le p_j \le p(f(r_j^2)) \le M+2r_j$, so $1 \le p_j - 2r_j \le M$ for all $j \ge 1$. It follows that there is an integer $a_1$ such that $1 \le a_1 \le M$ and $a_1 = p_j - 2r_j$ for infinitely many $j$. Let $m = \deg f$. Then $p_j|4^m f((p_j-a_1)/2)^2)$ and $4^m f((x-a_1)/2)^2) \in \mathbb{Z}[x]$. Consequently, $p_j|f((a_1/2)^2)$ for infinitely many $j$, which shows that $(a_1/2)^2$ is a zero of $f$. Since $f(n^2) \ne 0$ for $n \ge 0$, $a_1$ must be odd. Then $f(x) = (4x-a_1^2)g(x)$ where $g \in \mathbb{Z}[x]$. (See the note below.) Observe that $\{p(g(n^2)) - 2n\}_{n \ge 0}$ must be bounded above. If $g$ is constant, we are done. If $g$ is nonconstant, the argument can be repeated to show that $f$ is given by $(*)$.