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 $\displaystyle p(x)q(x)$ is $\pm 1$, and $\displaystyle p(x)$ and $\displaystyle q(x)$ both have integral constant terms, the constant term of $\displaystyle p(x)$ must be $\pm 1$.

We note that for $\displaystyle |z| \ge 2$, $\displaystyle 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 $\displaystyle |z^n| = | p(x)q(x) - z^n |$ when $\displaystyle n$ is the degree of $\displaystyle p(x)q(x)$ and $\displaystyle z$ is a root thereof, this means that $\displaystyle p(x)q(x)$ cannot have any roots of magnitude greater than or equal to 2.

Now, if $\displaystyle p(x) = x^2 + kx + 1$, then we cannot have $\displaystyle |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 $\displaystyle p(x) = x^2 +kx - 1$, then we cannot have $\displaystyle |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 $\displaystyle 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 $\displaystyle q(x) = x+1,\; 1,\; x^2 - 1,\; x^2 + 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.

Invalid username
Login to AoPS