Difference between revisions of "2006 USAMO Problems/Problem 3"
5849206328x (talk | contribs) 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>.) | ||
− | + | == Solutions == | |
− | |||
− | |||
+ | === 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> | ||
− | + | {{alternate solutions}} | |
− | == See | + | == See also == |
+ | * <url>viewtopic.php?t=84553 Discussion on AoPS/MathLinks</url> | ||
− | + | {{USAMO newbox|year=2006|num-b=1|num-a=3}} | |
− | |||
− | [[Category:Olympiad | + | [[Category:Olympiad Combinatorics Problems]] |
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 18:25, 5 August 2014
Contents
[hide]Problem
(Titu Andreescu, Gabriel Dospinescu) For integral , let be the greatest prime divisor of . By convention, we set and . Find all polynomials with integer coefficients such that the sequence is bounded above. (In particular, this requires for .)
Solutions
Solution 1
Let be a non-constant polynomial in of degree with integer coefficients, suppose further that no prime divides all the coefficients of (otherwise consider the polynomial obtained by dividing by the gcd of its coefficients). We further normalize by multiplying by , if necessary, to ensure that the leading coefficient (of ) is positive.
Let , then is a polynomial of degree or more and . Let be the factorization of into irreducible factors with positive leading coefficients. Such a factorization is unique. Let denote the degree of . Since the factors are either even functions of or come in pairs with .
Let , . For any other integer let be the largest prime factor of .
Suppose that for some finite constant and all we have . Since the polynomials divide , the same must be true for each of the irreducible polynomials .
A theorem of T. Nagell implies that if the ratio is unbounded for large values of . Since in our case the is asymptotically bounded above by for large , we conclude that all the irreducible factors are linear. Since linear polynomials are not even functions of , they must occur in pairs , . Without loss of generality, . Since the coefficients of are relatively prime, so are and , and since , neither polynomial can have any non-negative integer roots, so and thus .
On the other hand, by Dirichlet's theorem, , since otherwise the sequence would yield infinitely many prime values with So and therefore is a positive odd integer. Setting , clearly . Since this holds for each factor , it is true for the product of all the factors with the bound determined by the factor with the largest value of .
Therefore, for suitable non-negative integers , is a product of polynomials of the form . Now, since , we conclude that is a product of linear factors of the form .
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 . Thus for a suitable non-zero integer and non-negative integers , we have:
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.