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 "2006 USAMO Problems/Problem 3"
m
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
(''Titu Andreescu, Gabriel Dospinescu'') For integral <math>m</math>, let <math>p(m)</math> be the greatest prime divisor of <math>m</math>. By convention, we set <math>p(\pm 1)=1</math> and <math>p(0)=\infty</math>. Find all polynomials <math>f</math> with integer coefficients such that the sequence <math>\{ p(f(n^2))-2n) \}_{n\ge 0}</math> is bounded above. (In particular, this requires <math>f(n^2)\neq 0</math> for <math>n\ge 0</math>.)
  
−
For integral <math>m </math>, let <math>p(m) </math> be the greatest prime divisor of <math>m </math>. By convention, we set <math> p(\pm 1)=1</math> and <math>p(0)=\infty</math>. Find all polynomials <math>f </math> with integer coefficients such that the sequence <math> \{ p(f(n^2))-2n) \} _{n\ge 0} </math> is bounded above. (In particular, this requires <math>f(n^2)\neq 0</math> for <math>n\ge 0</math>.)
+
== Solutions ==
−
 
 
−
== Solution ==
 
  
 +
=== Solution 1 ===
 
Let <math>f(x)</math> be a non-constant polynomial in <math>x</math> of degree <math>d</math> with
 
Let <math>f(x)</math> be a non-constant polynomial in <math>x</math> of degree <math>d</math> with
 
integer coefficients, suppose further that no prime divides all the
 
integer coefficients, suppose further that no prime divides all the
Line 58: Line 58:
 
\cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)</cmath>
 
\cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)</cmath>
  
−
Note: a more elementary solution can be found at [http://www.williams.edu/go/math/sjmiller/public_html/greenchicken/otherexams/olympiad0607solns.pdf USA and International Mathematical Olympiads 2006-2007 by Zuming Feng and Yufei Zhao]
+
{{alternate solutions}}
  
−
== See Also ==
+
== See also ==
 +
* <url>viewtopic.php?t=84553 Discussion on AoPS/MathLinks</url>
  
−
* [[2006 USAMO Problems]]
+
{{USAMO newbox|year=2006|num-b=1|num-a=3}}
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=490625#p490625 Discussion on AoPS/MathLinks]
 
  
−
[[Category:Olympiad Number Theory Problems]]
+
[[Category:Olympiad Combinatorics Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 18:25, 5 August 2014

Problem

(Titu Andreescu, Gabriel Dospinescu) For integral $m$, let $p(m)$ be the greatest prime divisor of $m$. By convention, we set $p(\pm 1)=1$ and $p(0)=\infty$. Find all polynomials $f$ with integer coefficients such that the sequence $\{ p(f(n^2))-2n) \}_{n\ge 0}$ is bounded above. (In particular, this requires $f(n^2)\neq 0$ for $n\ge 0$.)

Solutions

Solution 1

Let $f(x)$ be a non-constant polynomial in $x$ of degree $d$ with integer coefficients, suppose further that no prime divides all the coefficients of $f$ (otherwise consider the polynomial obtained by dividing $f$ by the gcd of its coefficients). We further normalize $f$ by multiplying by $-1$, if necessary, to ensure that the leading coefficient (of $x^d$) is positive.

Let $g(n) = f(n^2)$, then $g(n)$ is a polynomial of degree $2$ or more and $g(n) = g(-n)$. Let $g_1, \ldots, g_k$ be the factorization of $g$ into irreducible factors with positive leading coefficients. Such a factorization is unique. Let $d(g_i)$ denote the degree of $g_i$. Since $g(-n) = g(n)$ the factors $g_i$ are either even functions of $n$ or come in pairs $(g_i, h_i)$ with $g_i(-n) = (-1)^{d(g_i)} h_i(n)$.

Let $P(0) = \infty$, $P(\pm 1) = 1$. For any other integer $m$ let $P(m)$ be the largest prime factor of $m$.

Suppose that for some finite constant $C$ and all $n \ge 0$ we have $P(g(n)) - 2n < C$. Since the polynomials $g_i$ divide $g$, the same must be true for each of the irreducible polynomials $g_i$.

A theorem of T. Nagell implies that if $d(g_i) \ge 2$ the ratio $P(g_i(n))/n$ is unbounded for large values of $n$. Since in our case the $P(g_i(n))/n$ is asymptotically bounded above by $2$ for large $n$, we conclude that all the irreducible factors $g_i$ are linear. Since linear polynomials are not even functions of $n$, they must occur in pairs $g_i(n) = a_in + b_i$, $h_i(n) = a_in - b_i$. Without loss of generality, $b_i \ge 0$. Since the coefficients of $f$ are relatively prime, so are $a_i$ and $b_i$, and since $P(0) = \infty$, neither polynomial can have any non-negative integer roots, so $a_i > 1$ and thus $b_i > 0$.

On the other hand, by Dirichlet's theorem, $a_i \le 2$, since otherwise the sequence $a_in + b_i$ would yield infinitely many prime values with $P(g_i(n)) = a_in + b_i \ge 3n.$ So $a_i = 2$ and therefore $b_i$ is a positive odd integer. Setting $b_i = 2c_i + 1$, clearly $P(g_i(n)) - 2n < 2c_i + 2$. Since this holds for each factor $g_i$, it is true for the product $g$ of all the factors with the bound determined by the factor with the largest value of $c_i$.

Therefore, for suitable non-negative integers $c_i$, $g(n)$ is a product of polynomials of the form $4n^2 - (2c_i + 1)^2$. Now, since $g(n) = f(n^2)$, we conclude that $f(n)$ is a product of linear factors of the form $4n - (2c_i + 1)^2$.

Since we restricted ourselves to non-constant polynomials with relatively prime coefficients, we can now relax this condition and admit a possibly empty list of linear factors as well as an arbitrary non-zero integer multiple $M$. Thus for a suitable non-zero integer $M$ and $k \ge 0$ non-negative integers $c_i$, we have: \[f(n) = M \cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)\]

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

See also

  • <url>viewtopic.php?t=84553 Discussion on AoPS/MathLinks</url>
2006 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_USAMO_Problems/Problem_3&oldid=62752"