SAUDI ARABIAN MATHEMATICAL COMPETITIONS

For convenience, denote $3d=2016$.

Lemma. There exist a polynomial $Q(x)\in \mathbb{Q}[x]$ such that $$\underset{x\to +\infty }{\lim }[\sqrt[3]{P(x)}-Q(x)]=0$$ Proof. Suppose that $S(x)\in \mathbb{Q}[x]$ is a polynomial such that $\mathrm{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: - $\mathrm{deg}(P(x)-S^3(x))<\mathrm{deg}P(x)=3d$. - $S(x)$ has leading coefficient $1$. - $\mathrm{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=\mathrm{deg}(P(x)-S^3(x))\ge 2d$. Consider polynomial $S^{\ast }(x)=S(x)+\frac{a_l}{3}{x}^{l-2d}$ then $$\begin{array}{rl}& P(x)-(S^{\ast }(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{array}$$ The result is a polynomial of degree less than $l$. This means $$\mathrm{deg}(P(x)-(S^{\ast }(x){)}^3)<l=\mathrm{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 $$\mathrm{deg}(\sqrt[3]{P(x)}-Q(x))<2d=\mathrm{deg}(\sqrt[3]{P^2(x)}+\sqrt[3]{P(x)}Q(x)+Q^2(x))$$ then ${\lim }_{x\to +\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}}^{\ast }$. 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\to +\infty }{a}_i=+\infty$, which implies that $$\underset{x\to +\infty }{\lim }P\left(a_i\right)=+\infty \text{ and }\underset{x\to +\infty }{\lim }{N}_i=+\infty$$ then $$\underset{x\to +\infty }{\lim }[\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 $$\underset{i\to +\infty }{\lim }M(Q(a_i)-N_i)=\underset{i\to +\infty }{\lim }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, $MQ(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\iff P(a_i)=Q^3(a_i)+3Q(a_i)+1$ for all $i>i_0$. This implies that $P(x)=Q^3(x)+3Q(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+Mk$ satisfies the given requirement. It is needed to clarify $Q(a_1+Mk)\in {\mathbb{Z}}^{+}$ for all $k\in {\mathbb{Z}}^{+}$. Indeed, let $R(x)=MQ(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.