Difference between revisions of "2002 IMO Shortlist Problems/A3"

 
m
 
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
Let <math> \displaystyle P </math> be a cubic [[polynomial]] given by <math> \displaystyle P(x) = ax^3 + bx^2 + cx + d </math>, where <math> \displaystyle a, b, c, d </math> are integers and <math> \displaystyle a \neq 0 </math>.  Suppose that <math> \displaystyle xP(x) = yP(y) </math> for infinitely many pairs <math> \displaystyle x </math>, <math> \displaystyle y </math> of integers with <math> \displaystyle x \neq y </math>.  Prove that the equation <math> \displaystyle P(x) = 0 </math> has an integer root.
+
Let <math>P </math> be a [[cubic polynomial | cubic]] [[polynomial]] given by <math> P(x) = ax^3 + bx^2 + cx + d </math>, where <math> a, b, c, d </math> are [[integer]]s and <math> a \neq 0 </math>.  Suppose that <math> xP(x) = yP(y) </math> for infinitely many pairs <math>x </math>, <math>y </math> of integers with <math> x \neq y </math>.  Prove that the equation <math> P(x) = 0 </math> has an integer root.
  
 
== Solutions ==
 
== Solutions ==
  
We note that the condition <math> \displaystyle xP(x) = yP(y) </math> is equivalent to
+
We note that the condition <math>xP(x) = yP(y) </math> is equivalent to
  
 
<center>
 
<center>
 
<math>
 
<math>
\displaystyle a(x^4 - y^4) + b(x^3 - y^3) + c(x^2 - y^2) + d(x - y) = 0
+
a(x^4 - y^4) + b(x^3 - y^3) + c(x^2 - y^2) + d(x - y) = 0
 
</math>.
 
</math>.
 
</center>
 
</center>
  
Since <math> \displaystyle x \neq y </math>, we may remove the factor <math> \displaystyle (x-y) </math> to obtain
+
Since <math>x \neq y </math>, we may remove the factor <math>(x-y) </math> to obtain
  
 
<center>
 
<center>
 
<math>
 
<math>
\displaystyle a(x^3 + x^{2}y + xy^2 + y^3) + b(x^2 + xy + y^2) + c(x + y) + d = 0
+
a(x^3 + x^{2}y + xy^2 + y^3) + b(x^2 + xy + y^2) + c(x + y) + d = 0
 
</math>,
 
</math>,
 
</center>
 
</center>
Line 25: Line 25:
 
<center>
 
<center>
 
<math>
 
<math>
\displaystyle P(x+y) = xy\left[ 2a(x+y) + b \right]
+
P(x+y) = xy\left[ 2a(x+y) + b \right]
 
</math>.
 
</math>.
 
</center>
 
</center>
Line 31: Line 31:
  
  
We can denote <math> \displaystyle x + y </math> and <math> \displaystyle xy </math> as <math> \displaystyle s </math> and <math> \displaystyle t </math>, respectively, rewriting this as
+
We can denote <math>x + y </math> and <math>xy </math> as <math>s </math> and <math>t </math>, respectively, rewriting this as
  
 
<center>
 
<center>
 
<math>
 
<math>
\displaystyle P(s) = (2as + b)t
+
P(s) = (2as + b)t
 
</math>.
 
</math>.
 
</center>
 
</center>
Line 41: Line 41:
 
=== Solution 1 ===
 
=== Solution 1 ===
  
We claim that <math> \displaystyle s </math> can only assume finitely many values.  We note that <math> \displaystyle {} s^2 - 4t = (x-y)^2 \ge 0 </math>, so <math> \displaystyle |t| < s^2 /4 </math>, which brings us to
+
We claim that <math>s </math> can only assume finitely many values.  We note that <math>{} s^2 - 4t = (x-y)^2 \ge 0 </math>, so <math>|t| < s^2 /4 </math>, which brings us to
  
 
<center>
 
<center>
Line 49: Line 49:
 
</center>
 
</center>
  
which is clearly true for at most finitely many integer values of <math> \displaystyle s </math>.
+
which is clearly true for at most finitely many integer values of <math>s </math>.
  
We denote <math> \displaystyle xP(x) </math> by <math> \displaystyle Q(x) </math>.  The condition <math> \displaystyle xP(x) = yP(y) </math> is then equivalent to <math> \displaystyle Q(x) = Q(y) </math>, or <math> \displaystyle Q(s) = Q(r-s)</math>.  But <math> \displaystyle s </math> can only assume finitely many values, so for some value of <math> \displaystyle s </math>, <math> \displaystyle Q(x) = Q(s-x) </math> are quartic polynomials equivalent at infinitely many points and are therefore equivalent.
+
We denote <math>xP(x) </math> by <math>Q(x) </math>.  The condition <math>xP(x) = yP(y) </math> is then equivalent to <math>Q(x) = Q(y) </math>, or <math>Q(s) = Q(r-s)</math>.  But <math>s </math> can only assume finitely many values, so for some value of <math>s </math>, <math>Q(x) = Q(s-x) </math> are quartic polynomials equivalent at infinitely many points and are therefore equivalent.
  
Now, if <math> \displaystyle s = 0 </math>, then we have <math> \displaystyle Q(x) = Q(-x)</math>, so <math> \displaystyle Q </math> is an even function.  Since <math> \displaystyle Q </math> is divisible by <math> \displaystyle x </math>, it must therefore also be divisible by <math> \displaystyle x^2 </math>, implying that <math> \displaystyle P </math> is divisible by <math> \displaystyle x </math>, which means that 0 is a root of <math> \displaystyle P </math>, as desired.
+
Now, if <math>s = 0 </math>, then we have <math>Q(x) = Q(-x)</math>, so <math>Q </math> is an even function.  Since <math>Q </math> is divisible by <math>x </math>, it must therefore also be divisible by <math>x^2 </math>, implying that <math>P </math> is divisible by <math>x </math>, which means that 0 is a root of <math>P </math>, as desired.
  
If <math> \displaystyle s \neq 0 </math>, then we have <math> \displaystyle xP(x) = (s-x)P(s-x) </math>, so <math> \displaystyle sP(s) = 0</math>, implying that <math> \displaystyle P(s) </math> is equal to 0 since <math> \displaystyle s \neq 0</math>.  Thus <math> \displaystyle s </math> is the desired root of <math> \displaystyle P(s) </math>.
+
If <math>s \neq 0 </math>, then we have <math>xP(x) = (s-x)P(s-x) </math>, so <math>sP(s) = 0</math>, implying that <math>P(s) </math> is equal to 0 since <math>s \neq 0</math>.  Thus <math>s </math> is the desired root of <math>P(s) </math>.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
 
   
 
   
Consider the function <math> \displaystyle xP(x) </math>.  If <math> \displaystyle P(x) </math> has roots <math> \lambda_1 \le \lambda_2 \le \lambda_3 </math>, then <math> \displaystyle P(x) </math> is bounded on the interval <math> \left[ \min (\lambda_1 , 0) , \max (\lambda_3 , 0) \right] </math>, and [[injective]] on each of the intervals <math> (-\infty , \min (\lambda_1 , 0) ) , ( \max (\lambda_3 , 0 ) , \infty) </math>.  Because each value of <math> \displaystyle xP(x) </math> yields at most finitely many solutions <math> \displaystyle x,y </math>, there are at most finitely many solutions <math> \displaystyle x,y </math> such that <math> \displaystyle x </math> and <math> \displaystyle y </math> have the same sign.
+
Consider the function <math>xP(x) </math>.  If <math>P(x) </math> has roots <math> \lambda_1 \le \lambda_2 \le \lambda_3 </math>, then <math>P(x) </math> is bounded on the interval <math> \left[ \min (\lambda_1 , 0) , \max (\lambda_3 , 0) \right] </math>, and [[injective]] on each of the intervals <math> (-\infty , \min (\lambda_1 , 0) ) , ( \max (\lambda_3 , 0 ) , \infty) </math>.  Because each value of <math>xP(x) </math> yields at most finitely many solutions <math>x,y </math>, there are at most finitely many solutions <math>x,y </math> such that <math>x </math> and <math>y </math> have the same sign.
  
Since <math> \displaystyle P(s) = xy( 2as + b ) </math>, if <math> \displaystyle P(s) \neq 0 </math>, then each value of <math> \displaystyle s </math> yields at most one solution.  But for arbitrarily large values of <math> \displaystyle s </math>, <math> \displaystyle P(s) </math> and <math> \displaystyle (2as + b) </math> have the same sign, making <math> \displaystyle P(s) = xy (2as + b) </math> impossible if <math> \displaystyle x </math> and <math> \displaystyle y </math> have different signs.  Thus there must be some integer <math> \displaystyle s </math> such that <math> \displaystyle P(s) = 0 </math>.  (Indeed, if <math> \displaystyle P(s) = 2as + b = 0 </math>, then any pair of integers with sum <math> \displaystyle s </math> is a solution.)
+
Since <math>P(s) = xy( 2as + b ) </math>, if <math>P(s) \neq 0 </math>, then each value of <math>s </math> yields at most one solution.  But for arbitrarily large values of <math>s </math>, <math>P(s) </math> and <math>(2as + b) </math> have the same sign, making <math>P(s) = xy (2as + b) </math> impossible if <math>x </math> and <math>y </math> have different signs.  Thus there must be some integer <math>s </math> such that <math>P(s) = 0 </math>.  (Indeed, if <math>P(s) = 2as + b = 0 </math>, then any pair of integers with sum <math>s </math> is a solution.)
  
  

Latest revision as of 18:51, 8 September 2009

Problem

Let $P$ be a cubic polynomial given by $P(x) = ax^3 + bx^2 + cx + d$, where $a, b, c, d$ are integers and $a \neq 0$. Suppose that $xP(x) = yP(y)$ for infinitely many pairs $x$, $y$ of integers with $x \neq y$. Prove that the equation $P(x) = 0$ has an integer root.

Solutions

We note that the condition $xP(x) = yP(y)$ is equivalent to

$a(x^4 - y^4) + b(x^3 - y^3) + c(x^2 - y^2) + d(x - y) = 0$.

Since $x \neq y$, we may remove the factor $(x-y)$ to obtain

$a(x^3 + x^{2}y + xy^2 + y^3) + b(x^2 + xy + y^2) + c(x + y) + d = 0$,

or

$P(x+y) = xy\left[ 2a(x+y) + b \right]$.


We can denote $x + y$ and $xy$ as $s$ and $t$, respectively, rewriting this as

$P(s) = (2as + b)t$.

Solution 1

We claim that $s$ can only assume finitely many values. We note that ${} s^2 - 4t = (x-y)^2 \ge 0$, so $|t| < s^2 /4$, which brings us to

$| as^3 + bs^2 + cs + d | \le \left| \frac{a}{2}s^3 + \frac{b}{4}s^2 \right|$,

which is clearly true for at most finitely many integer values of $s$.

We denote $xP(x)$ by $Q(x)$. The condition $xP(x) = yP(y)$ is then equivalent to $Q(x) = Q(y)$, or $Q(s) = Q(r-s)$. But $s$ can only assume finitely many values, so for some value of $s$, $Q(x) = Q(s-x)$ are quartic polynomials equivalent at infinitely many points and are therefore equivalent.

Now, if $s = 0$, then we have $Q(x) = Q(-x)$, so $Q$ is an even function. Since $Q$ is divisible by $x$, it must therefore also be divisible by $x^2$, implying that $P$ is divisible by $x$, which means that 0 is a root of $P$, as desired.

If $s \neq 0$, then we have $xP(x) = (s-x)P(s-x)$, so $sP(s) = 0$, implying that $P(s)$ is equal to 0 since $s \neq 0$. Thus $s$ is the desired root of $P(s)$.

Solution 2

Consider the function $xP(x)$. If $P(x)$ has roots $\lambda_1 \le \lambda_2 \le \lambda_3$, then $P(x)$ is bounded on the interval $\left[ \min (\lambda_1 , 0) , \max (\lambda_3 , 0) \right]$, and injective on each of the intervals $(-\infty , \min (\lambda_1 , 0) ) , ( \max (\lambda_3 , 0 ) , \infty)$. Because each value of $xP(x)$ yields at most finitely many solutions $x,y$, there are at most finitely many solutions $x,y$ such that $x$ and $y$ have the same sign.

Since $P(s) = xy( 2as + b )$, if $P(s) \neq 0$, then each value of $s$ yields at most one solution. But for arbitrarily large values of $s$, $P(s)$ and $(2as + b)$ have the same sign, making $P(s) = xy (2as + b)$ impossible if $x$ and $y$ have different signs. Thus there must be some integer $s$ such that $P(s) = 0$. (Indeed, if $P(s) = 2as + b = 0$, then any pair of integers with sum $s$ is a solution.)


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

Resources

Invalid username
Login to AoPS