Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 IMO Shortlist Problems/A1"

 
(I believe the solution was (slightly) wrong, as otherwise the product doesn't verify the problem conditions)
 
Line 8: Line 8:
 
== Solution ==
 
== Solution ==
  
−
Since the constant term of <math> \displaystyle p(x)q(x) </math> is <math> \pm 1 </math>, and <math> \displaystyle p(x) </math> and <math> \displaystyle q(x) </math> both have integral constant terms, the constant term of <math> \displaystyle p(x) </math> must be <math> \pm 1 </math>.
+
Since the constant term of <math>p(x)q(x) </math> is <math> \pm 1 </math>, and <math>p(x) </math> and <math>q(x) </math> both have integral constant terms, the constant term of <math>p(x) </math> must be <math> \pm 1 </math>.
  
−
We note that for <math> \displaystyle |z| \ge 2 </math>, <math> \displaystyle n \ge 2 </math> (<math> n \in \mathbb{N} </math>), we have
+
We note that for <math>|z| \ge 2 </math>, <math>n \ge 2 </math> (<math> n \in \mathbb{N} </math>), we have
  
 
<center>
 
<center>
Line 18: Line 18:
 
</center>
 
</center>
  
−
Since we must have <math>\displaystyle |z^n| = | p(x)q(x) - z^n |</math> when <math> \displaystyle n </math> is the degree of <math> \displaystyle p(x)q(x) </math> and <math> \displaystyle z </math> is a root thereof, this means that <math> \displaystyle p(x)q(x) </math> cannot have any roots of magnitude greater than or equal to 2.
+
Since we must have <math>|z^n| = | p(x)q(x) - z^n |</math> when <math>n </math> is the degree of <math>p(x)q(x) </math> and <math>z </math> is a root thereof, this means that <math>p(x)q(x) </math> cannot have any roots of magnitude greater than or equal to 2.
  
−
Now, if <math> \displaystyle p(x) = x^2 + kx + 1 </math>, then we cannot have <math> \displaystyle |k| \ge 3 </math>, for then one of the roots would have magnitude <math> \frac{|k| + \sqrt{k^2 - 4}}{2} \ge \frac{3 + \sqrt{3^2 - 4}}{2} > 2</math>, and similarly, if <math> \displaystyle p(x) = x^2 +kx - 1 </math>, then we cannot have <math> \displaystyle |k| \ge 2 </math>, for then one of the roots would have magnitude <math> \frac{|n| + \sqrt{n^2+4}}{2} \ge \frac{2 + \sqrt{2^2 + 4}}{2} > 2 </math>.
+
Now, if <math>p(x) = x^2 + kx + 1 </math>, then we cannot have <math>|k| \ge 3 </math>, for then one of the roots would have magnitude <math> \frac{|k| + \sqrt{k^2 - 4}}{2} \ge \frac{3 + \sqrt{3^2 - 4}}{2} > 2</math>, and similarly, if <math>p(x) = x^2 +kx - 1 </math>, then we cannot have <math>|k| \ge 2 </math>, for then one of the roots would have magnitude <math> \frac{|n| + \sqrt{n^2+4}}{2} \ge \frac{2 + \sqrt{2^2 + 4}}{2} > 2 </math>.
  
−
This leaves us only the possibilities <math> \displaystyle p(x) = x^2 \pm 1,\; x^2 \pm x \pm 1,\; x^2 + 2x + 1,\; x^2 - 2x + 1</math>.  For these we have respective solutions <math> \displaystyle q(x) = x+1,\; 1,\; x^2 - 1,\; x^2 + 1 </math>.  These are therefore the only solutions, Q.E.D.
+
This leaves us only the possibilities <math>p(x) = x^2 \pm 1,\; x^2 \pm x \pm 1,\; x^2 + 2x + 1,\; x^2 - 2x + 1</math>.  For these we have respective solutions <math>q(x) = x+1,\; 1,\; x - 1,\; x + 1 </math>.  These are therefore the only solutions, Q.E.D.
  
  

Latest revision as of 08:56, 14 May 2024

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_IMO_Shortlist_Problems/A1&oldid=219320"