Let $P$ be a polynomial with real coefficients. Prove that if for some integer $k$ $P(k)$ isn't integral, then there exist infinitely many integers $m$, for which $P(m)$ isn't integral.
Problem
Source: Polish MO Finals 2015
Tags: contests, polynomial, algebra, calculus, integration
28.07.2016 01:42
Suppose there were only finitely many $m$, and let $M$ be the largest such integer. It's a well-known fact of polynomials that if $d=\deg P$, then $\Delta_{d+1} P(x) = 0$. Therefore, we know that $\displaystyle\sum_{i=0}^{d+1} \binom{d+1}{i} P(x+i)(-1)^i = 0$. In particular, we know $P(M) = -\displaystyle\sum_{i=1}^{d+1} \binom{d+1}{i} P(M+i)(-1)^i$ and by assumption, each $P(M+i)$ is an integer, so $P(M)$ is an integer, a contradiction.
26.02.2017 16:01
Assume the opposite for the sake of contradiction. We first prove that $P\in \mathbb{Q}[x]$: Let $d$ be the degree of $P$. By our assumption, there exists $d+1$ different integers $a_1,a_2,\dotsc,a_{d+1}$ such that $P(a_i)$ is an integer. Using Lagrange interpolation, we define the polynomial \[ R(x)\stackrel{\rm{def}}{=}\sum_{i=1}^{d+1}\left(\frac{\prod_{j!=i}(x-a_j)}{\prod_{j!=i}(a_j-a_i)}\cdot P(a_i)\right), \]which has degree at most $d$, and satisfies $R(a_i)=P(a_i)$ for $1\leq i\leq d+1$. It follows that the polynomial $R-P$ has at least $d+1$ different roots, and since it has degree at most $d$, it must be the zero polynomial. We conclude that $P=R$, and the claim is proved. Now, since $P\in\mathbb{Q}[x]$, there is an integer $n$ such that $nP$ has integer coefficients; Let $Q(x) = n\cdot P(x)$. Since $P(k)$ is not an integer (given), $nP(k)=Q(k)$ is not divisible by $n$. But then $Q(k+xn)\equiv_n Q(k)$ is not divisible by $n$ for any integer $x$, which means that $P(k+xn)$ is not an integer for any $x$, and we have our contradiction.
26.02.2017 16:32
Suppose not and let $A$ be the largest such number.Let $R(x)=P(x+A)$ and note that this implies that $R(\mathbb{N}_0)\subset Z$.Now : $$\Delta ^k R(x)=\sum_{j=0}^k R(x+j)(-1)^{j-k}\binom{k}{j}$$Setting $x:=0$ we obtain $\Delta^k R(0)=[x^k]R\in \mathbb{Z}$ $\forall k$ $\implies$ $R\in \mathbb{Z}[X]$ and by shifting everything by $A$ $\implies$ $P\in \mathbb{Z}[x]$ a contradiction.
30.10.2022 23:58
Suppose $P(m)$ is integral for all sufficiently large $m$, and let $\deg P = d$. Then by finite differences, if $1000d+1000$ values of $P$ are integers, then each of the iterated finite differences are also integers and thus $P(m)$ is integral for all $m$: contradiction.
24.12.2023 00:36
If $P(m)$ is integral for all $k \geq M$ then by finite differences formula $$\Delta ^t P(x)=\sum_{i=0}^t P(x+i)(-1)^{i-j}\binom{t}{i}$$Putting $x = M$, we get a contradiction (as it forces $P(m)$ to be integer)