Saudi Arabian Mathematical Competitions

For convenience, denote $3d = 2016$.

Lemma. There exist a polynomial $Q(x) \in \mathbb{Q}[x]$ such that
$$\lim_{x \rightarrow +\infty} [\sqrt[3]{P(x)} - Q(x)] = 0$$
Proof. Suppose that $S(x) \in \mathbb{Q}[x]$ is a polynomial such that $\operatorname{deg}(P(x) - S^{3}(x))$ is minimized (if there are many $S(x)$ that satisfy, we choose one of them).
It is easy to check that:
- $\operatorname{deg}(P(x) - S^{3}(x)) < \operatorname{deg} P(x) = 3d$.
- $S(x)$ has leading coefficient $1$.
- $\operatorname{deg}(P(x) - S^{3}(x)) < 2d$.
For iii), denote $P(x) - S^{3}(x) = a_{l} x^{l} + a_{l-1} x^{l-1} + \cdots + a_{0}$ and suppose by contradiction that $l = \operatorname{deg}(P(x) - S^{3}(x)) \geq 2d$. Consider polynomial $S^*(x) = S(x) + \frac{a_{l}}{3} x^{l-2d}$ then
$$\begin{aligned} & P(x) - (S^*(x))^{3} = \\ & \left(P(x) - S^{3}(x) - a_{l} x^{l-2d} S^{2}(x)\right) - \left(\frac{1}{3} a_{l}^{2} x^{2l-4d} S(x) + \frac{1}{27} a_{l}^{3} x^{3l-6d}\right). \end{aligned}$$
The result is a polynomial of degree less than $l$. This means
$$\operatorname{deg}(P(x) - (S^*(x))^{3}) < l = \operatorname{deg}(P(x) - S^{3}(x))$$
which is a contradiction. Then, take $Q(x) = S(x)$ to get
$$\sqrt[3]{P(x)} - Q(x) = \frac{P(x) - Q^{3}(x)}{\sqrt[3]{P^{2}(x)} + \sqrt[3]{P(x)} Q(x) + Q^{2}(x)}$$
From iii), we can see that
$$\operatorname{deg}(\sqrt[3]{P(x)} - Q(x)) < 2d = \operatorname{deg}(\sqrt[3]{P^{2}(x)} + \sqrt[3]{P(x)} Q(x) + Q^{2}(x))$$
then $\lim_{x \rightarrow +\infty} [\sqrt[3]{P(x)} - Q(x)] = 0$. The lemma is proved.

Since there exist infinitely many numbers $a$ such that $P(a)$ is nice, we can choose some strictly increasing sequence of positive integers $\left(a_{n}\right)$ such that $P\left(a_{i}\right)$ are nice for all $i \in \mathbb{N}^{*}$.
Clearly, for each $a_{i}$, there exists $N_{i} \in \mathbb{Z}^{+}$ such that $P\left(a_{i}\right) = N_{i}^{3} + 3N_{i} + 1$.
Since $\lim_{x \rightarrow +\infty} a_{i} = +\infty$, which implies that
$$\lim_{x \rightarrow +\infty} P\left(a_{i}\right) = +\infty \text{ and } \lim_{x \rightarrow +\infty} N_{i} = +\infty$$
then
$$\lim_{x \rightarrow +\infty} [\sqrt[3]{N_{i}^{3} + 3N_{i} + 1} - N_{i}] = 0$$
Now, let $Q(x)$ be the polynomial described in the lemma.
Because $Q(x) \in \mathbb{Q}[x]$, there exists a number $M \in \mathbb{Z}^{+}$ such that $M \cdot Q(x) \in \mathbb{Z}[x]$. We have
$$\lim_{i \rightarrow +\infty} M(Q(a_{i}) - N_{i}) = \lim_{i \rightarrow +\infty} M(Q(a_{i}) - \sqrt[3]{P(a_{i})} + \sqrt[3]{P(a_{i})} - N_{i}) = 0$$
Hence, there is a number $i_{0} \in \mathbb{Z}^{+}$ such that
$$-1 < M(Q(a_{i}) - N_{i}) < 1, \forall i > i_{0}.$$
On the other hand, $M Q(a_{i}) \in \mathbb{Z}$, $N_{i} \in \mathbb{Z}$ so $M(Q(a_{i}) - N_{i}) = 0$ for all $i > i_{0}$, then $Q(a_{i}) - N_{i} = 0 \Leftrightarrow P(a_{i}) = Q^{3}(a_{i}) + 3 Q(a_{i}) + 1$ for all $i > i_{0}$. This implies that $P(x) = Q^{3}(x) + 3 Q(x) + 1$ for all $x \in \mathbb{R}$.

Choose a number $N$ such that $Q(x) > 0, \forall x > a_{N}$ then we will prove that the arithmetic sequence given by the formula $n_{k} = a_{N} + M k$ satisfies the given requirement.
It is needed to clarify $Q(a_{1} + M k) \in \mathbb{Z}^{+}$ for all $k \in \mathbb{Z}^{+}$.
Indeed, let $R(x) = M Q(x)$ then $R(x) \in \mathbb{Z}[x]$, then $R(n_{1}) = M a_{1}$ is divisible by $M$. So
$$(n_{k} - n_{1}) \mid R(n_{k}) - R(n_{1})$$
leads to $M \mid R(n_{k})$ for all $k \in \mathbb{Z}^{+}$. This finishes the proof.