## [Soln] 2015 Spain MO Day 1 Problem 1

2015 Spain MO 1.1. 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.

First, let’s give names to the objects mentioned in the question. Let the polynomial in question be denoted by $f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$, where the $a_i$‘s are integers. Let the two chosen points be $(p, f(p))$ and $(q, f(q))$, where $p$ and $q$ are integers and $p \neq q$.

With this notation, we can calculate the distance between the 2 points:

$\text{Distance} = \sqrt{(p-q)^2 + [f(p)-f(q)]^2}.$

Note here that “distance is an integer” is equivalent to $(p-q)^2 + [f(p)-f(q)]^2$ being a perfect square.

Next, let’s test out some simple cases to get a feel for the problem. If $f$ is the constant function (i.e. degree $n = 0$), then the graph is a horizontal line. In this case, the statement in the problem is obvious: the segment connecting any two points on the graph is parallel to the horizontal axis.

The next simplest case is where $f$ is a linear function (degree $n = 1$), i.e.

$f(x) = a_1x + a_0$

where $a_1 \neq 0$. We can calculate the square of the distance between the 2 points:

\begin{aligned} \text{Square distance} &= (p-q)^2 + [f(p) - f(q)]^2 \\ &= (p-q)^2 + [a_1p + a_0 - a_1q - a_0]^2 \\ &= (p-q)^2 + [a_1(p-q)]^2 \\ &= (p-q)^2(1 + a_1^2). \end{aligned}

The term $(p-q)^2$ factors out nicely and the remaining term $(1+a_1^2)$ is $1 + (\text{a positive perfect square})$, which means that it can’t be a perfect square itself!

Hence, we can make the following argument:

\begin{aligned} &&&\text{Square of distance is perfect square} \\ &\Rightarrow &&(p-q)^2(1 + a_1^2) \text{ is perfect square} \\ &\Rightarrow &&(1+a_1^2) \text{ is perfect square.} \end{aligned}

Contradiction (since $a_1 \neq 0$)! Hence, there is no such thing as 2 points with integer coordinates on a (non-constant) linear graph that are an integer distance apart.

Hmmm. That was not particularly illuminating for the general case as the “prerequisite” of having integer distance between 2 points can never be true. The next step is to see what happens for quadratic functions ($n = 2$), i.e.

$f(x) = a_2x^2 + a_1x + a_0$

where $a_2 \neq 0$.

\begin{aligned} \text{Square distance} &= (p-q)^2 + [f(p) - f(q)]^2 \\ &= (p-q)^2 + [a_2p^2 + a_1p + a_0 - a_2q^2 - a_1q - a_0]^2 \\ &= (p-q)^2 + [a_2(p^2-q^2) + a_1(p-q)]^2 \\ &= (p-q)^2 + [a_2(p+q)(p-q) + a_1(p-q)]^2 \\ &= (p-q)^2 [1 + (a_2(p+q) + a_1)^2]. \end{aligned}

Again, the $(p-q)^2$ term factors out nicely and the remaining term is $1 + \text{a perfect square}$! Hence, we can use similar logic as in the case of $n = 1$:

\begin{aligned} &&&\text{Square of distance is perfect square} \\ &\Rightarrow &&(p-q)^2(1 + (a_2(p+q) + a_1)^2) \text{ is perfect square} \\ &\Rightarrow &&(1+(a_2(p+q) + a_1)^2) \text{ is perfect square.} \end{aligned}

But unlike the case of $n = 1$, we can go further:

\begin{aligned} &\Rightarrow && a_2(p+q) + a_1 &&= 0, \\ &\Rightarrow && (p-q)[a_2(p+q) + a_1] &&= 0, \\ &\Rightarrow &&a_2(p^2 - q^2) + a_1(p-q) &&= 0, \\ &\Rightarrow &&a_2p^2 + a_1p + a_0 &&= a_2q^2 + a_1q^2 + a_0, \\ &\Rightarrow &&f(p) &&= f(q). \end{aligned}

Hence the line connecting the points $(p, f(p))$ and $(q, f(q))$ is parallel to the horizontal axis. Done for the case of $n = 2$!

Can we generalise this procedure? Looking over the proof above, the key step was in factoring out $(p-q)$ from the $(p^2 -q^2)$ term when calculating the square of the distance. Since

$p^n - q^n = (p-q)(p^{n-1} + p^{n-2}q + \dots + pq^{n-2} + q^{n-1}),$

we should be able to follow the same steps to obtain the result for general $n$!

To help make the proof a bit cleaner, let’s introduce additional notation:

$G_{n-1} = p^{n-1} + p^{n-2}q + \dots + pq^{n-2} + q^{n-1}.$

Then we have the identity

$p^n - q^n = (p-q) G_{n-1}.$

Following the previous chain of logic as close as possible but for general $n$:

\begin{aligned} \text{Square distance} &= (p-q)^2 + [f(p) - f(q)]^2 \\ &= (p-q)^2 + \left[\sum_{i=0}^n a_ip^i - \sum_{i=0}^n a_iq^i \right]^2 \\ &= (p-q)^2 + \left[ \sum_{i = 1}^n a_i(p^i - q^i) \right]^2 \\ &= (p-q)^2 + \left[ \sum_{i=1}^n a_i(p-q)G_{i-1} \right]^2 \\ &= (p-q)^2 \left[1 + \left( \sum_{i=1}^n a_iG_{i-1} \right)^2 \right]. \end{aligned}

Hence,

\begin{aligned} &&&\text{Square of distance is perfect square} \\ &\Rightarrow &&(p-q)^2\left[1 + \left( \sum_{i=1}^n a_iG_{i-1} \right)^2 \right] \text{ is perfect square} \\ &\Rightarrow &&1 + \left( \sum_{i=1}^n a_iG_{i-1} \right)^2 \text{ is perfect square.} \end{aligned}

Since the only pair of perfect squares of difference 1 is $(0, 1)$, we must have

\begin{aligned} &\Rightarrow &\sum_{i=1}^n a_iG_{i-1} &= 0, \\ &\Rightarrow &(p-q) \cdot \sum_{i=1}^n a_iG_{i-1} &= 0, \\ &\Rightarrow &\sum_{i=1}^n a_i(p^i - q^i) &= 0, \\ &\Rightarrow &\sum_{i = 0}^n a_ip^i &= \sum_{i= 0}^n a_iq^i, \\ &\Rightarrow &f(p) &= f(q). \end{aligned}

Hence the line connecting the points $(p, f(p))$ and $(q, f(q))$ is parallel to the horizontal axis. Done!