Problem Solving Question With Polynomials 
For any polynomial $p$ with real coefficients, let
  $$
S(p):= \{x\in \mathbb{R} \mid p(x) \in \mathbb{Z}\}
$$
  Prove that if $p$, $q$ are two polynomials such that $S(p) = S(q)$, then either $p+q$ or $p-q$ is a constant.

My attempt:
Let $S:=S(p)=S(q)$, if $x\in S:$ $$p(x)+q(x) \in Z, p(x)-q(x)\in \mathbb{Z}$$
By adding these equations we can receive that $p(x)\in \mathbb{Z}$, which is pointless info.
I also tried:
$$
p^2\in \mathbb{Z}, q^2\in \mathbb{Z} \implies p^2-q^2\in \mathbb{Z}\implies (p+q)(p-q)\in \mathbb{Z}
$$
which leads to nowhere.
I'm not sure how to even look at this question, since even if I do manage to find that $p+q$ or $p-q$ are constants for every $x\in S$, I wouldn't know how to apply that knowledge to every $x\in \mathbb{R}$.
 A: Here's just an idea, without a rigourous proof. Without loss of generality, assume both leading coefficients are positive and $p(x) > q(x)$ asymptotically (as $x \to \infty$). Then, unless $p = q+c$, starting from some point both $p$ and $q$ start increasing to infinity but $p$ increases faster than $q$ (with greater derivative). So assume $p(x_1) =M_1 \in \mathbb Z, q(x_1)=N_1 \in \mathbb Z$, and the next point in $S(q)$ is $x_2: p(x_2) =M_2 \in \mathbb Z, q(x_2)=N_2=N_1+1$. Then we must have $M_2-M_1 > 1$ (because $p$ increases faster), so there must have been another point $x \in (x_1, x_2)$ where $p(x) = M_2-1 \in \mathbb Z$, a contradiction because this point is in $S(p) \setminus S(q)$.
A: Not sure it's worth writing this separately (doesn't fit into a comment), but here's a bit more legwork and detail filling before applying Sly's idea
For any non-constant polynomial $p$, $S(p)$ is infinite. (why?)
0). The case where either $p$ or $q$ is constant is easy (if $p$ is constant, then $S(p)$ is either empty or equal to $\mathbb{R}$, and thus so is $S(q)$; in the first case, with the above remark $q$ is constant; in the latter,then $q$ can take only integer values; but then as a polynomial is continuous this means it can only take one value, otherwise it would take all values in between as well).
1). Assuming now both $p$ and $q$ are non-constant. Note that wlog, we can assume the leading coefficient $a$ of $p$ is positive (as otherwise, we can just consider $-p$ and $-q$. Furthermore, we can $(\dagger)$ also assume the same about the leading coefficient $b$ of $q$, as the hypotheses hold for both $p,q$ and $p,-q$. Finally, again without loss of generality, we can assume $a > b$ (otherwise, just swap $p$ and $q$. We can now apply Sly's idea (note that the conclusion will be that $p-q$ is constant; the case $p+q$ constant would come from the discussion above, where there is a $(\dagger)$: by possibly swapping $q$ wth $-q$).
