[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!

Advertisements
This entry was posted in Grade 12, Spain and tagged , , , . Bookmark the permalink.

One Response to [Soln] 2015 Spain MO Day 1 Problem 1

  1. Fergal Daly says:

    My solution was essentially the same but starts by noticing that if you have an f, p and q that work, you can shift everything so that (p, f(p)) -> (0, 0). This means f'(x) has no constant term and is actually f'(x) = x * g(x) and so the square distance is q^2 + (q * g(q))^2 = q^2 * (1 + g(q)^2).

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s