Difference between revisions of "2006 USAMO Problems/Problem 3"
(→Solution) |
(→Solution) |
||
Line 58: | Line 58: | ||
non-negative integers <math>c_i</math>, we have: | non-negative integers <math>c_i</math>, we have: | ||
<cmath>f(n) = M \cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)</cmath> | <cmath>f(n) = M \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] | ||
== See Also == | == See Also == |
Revision as of 10:18, 26 March 2010
Problem
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
.)
Solution
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
polynomials 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 irreducible factors as
well as an arbitrary non-zero integer multiple
. Thus for a
suitable non-zero integer
and a possibly empty set of
non-negative integers
, we have:
Note: a more elementary solution can be found at USA and International Mathematical Olympiads 2006-2007 by Zuming Feng and Yufei Zhao