tchebytchev wrote: On the graph of a polynomial with integer coefficients, two points are chosen with integer coordinates. Prove that if the distance between them is an integer, then the segment that connects them is parallel to the horizontal axis. Just write $(P(a)-P(b))^2+(a-b)^2=c^2$ and notice that $a-b|P(a)-P(b)$ So $\left(\frac{P(a)-P(b)}{a-b}\right)^2+1=d^2$ And it's easy to conclude from $n^2+1=m^2$ that $n=0$ Q.E.D.

This problem was on Moscow's Math Olympiad many years ago.

The distance between two points with $x$ coordinates $p$ and $q$ respectively, is given by $D=\sqrt{(q-p)^2+(f(q)-f(p))^2}$ As $f$ is a polynomial with integer coefficients, we have $q-p|f(q)-f(p)$. We rewrite this divisibility as $f(q)-f(p)=k(f(q)-f(p))$, where $k$ is an integer. This forces $(q-p)\sqrt(k^2+1) \in \mathbb{Z^+}$, which means $k=0$. Thus we have $f(p)=f(q)$.

Let $|a-b| = x, |P(a) - P(b)| = kx$, where $x, k \in \mathbb{N}_0$. From the Pythagorean Theorem, we require $k^2 + 1 = m^2$ for some $m \in \mathbb{Z}$, but from here we can easily conclude $k = 0$. $\square$