2005 IMO Shortlist Problems/A1

Problem

Find all monic polynomials $\displaystyle p(x)$ of degree two for which there exists an integer polynomial $\displaystyle q(x)$ such that $\displaystyle p(x)q(x)$ is a polynomial having all coefficients $\pm 1$.


This was also the last problem of the final round of the 2006 Polish Mathematics Olympiad.

Solution

Since the constant term of $p(x)q(x)$ is $\pm 1$, and $p(x)$ and $q(x)$ both have integral constant terms, the constant term of $p(x)$ must be $\pm 1$.

We note that for $|z| \ge 2$, $n \ge 2$ ($n \in \mathbb{N}$), we have

$|z|^n > \frac{|z|^n -1}{|z|-1} = \sum_{i=0}^{n-1}|\pm z|^i \ge \left| \sum_{i=0}^{n-1} \pm z^i \right|$

Since we must have $|z^n| = | p(x)q(x) - z^n |$ when $n$ is the degree of $p(x)q(x)$ and $z$ is a root thereof, this means that $p(x)q(x)$ cannot have any roots of magnitude greater than or equal to 2.

Now, if $p(x) = x^2 + kx + 1$, then we cannot have $|k| \ge 3$, for then one of the roots would have magnitude $\frac{|k| + \sqrt{k^2 - 4}}{2} \ge \frac{3 + \sqrt{3^2 - 4}}{2} > 2$, and similarly, if $p(x) = x^2 +kx - 1$, then we cannot have $|k| \ge 2$, for then one of the roots would have magnitude $\frac{|n| + \sqrt{n^2+4}}{2} \ge \frac{2 + \sqrt{2^2 + 4}}{2} > 2$.

This leaves us only the possibilities $p(x) = x^2 \pm 1,\; x^2 \pm x \pm 1,\; x^2 + 2x + 1,\; x^2 - 2x + 1$. For these we have respective solutions $q(x) = x+1,\; 1,\; x - 1,\; x + 1$. These are therefore the only solutions, Q.E.D.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources