Difference between revisions of "2006 USAMO Problems/Problem 3"
5849206328x (talk | contribs) m |
Kevinmathz (talk | contribs) (→Problem) |
||
(6 intermediate revisions by 3 users not shown) | |||
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>.) | + | (''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 \in \mathbb{Z} \ge 0}</math> is bounded above. (In particular, this requires <math>f(n^2)\neq 0</math> for <math>n\ge 0</math>.) |
== Solutions == | == Solutions == | ||
Line 57: | Line 57: | ||
<math>M</math> and <math>k \ge 0</math> non-negative integers <math>c_i</math>, we have: <cmath>f(n) = M | <math>M</math> and <math>k \ge 0</math> non-negative integers <math>c_i</math>, we have: <cmath>f(n) = M | ||
\cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)</cmath> | \cdot \prod_{i=1}^k (4n - (2c_i + 1)^2)</cmath> | ||
+ | |||
+ | === Solution 2 === | ||
+ | The polynomial <math>f</math> has the required properties if and only if | ||
+ | <cmath>f(x) = c(4x - a_1^2)(4x - a_2^2)\cdots (4x - a_k^2),\qquad\qquad (*)</cmath> | ||
+ | where <math>a_1, a_2, \ldots, a_k</math> are odd positive integers and <math>c</math> is a nonzero integer. It is straightforward to verify that polynomials given by <math>(*)</math> have the required property. If <math>p</math> is a prime divisor of <math>f(n^2)</math> but not of <math>c</math>, then <math>p|(2n - a_j)</math> or <math>p|(2n + a_j)</math> for some <math>j\leq k</math>. Hence <math>p - 2n\leq \max\{a_1, a_2, \ldots, a_k\}</math>. The prime divisors of <math>c</math> form a finite set and do not affect whether or not the given sequence is bounded above. The rest of the proof is devoted to showing that any <math>f</math> for which <math>\{p(f(n^2)) - 2n\}_{n\geq 0}</math> is bounded above is given by <math>(*)</math>. | ||
+ | |||
+ | Let <math>\mathbb{Z}[x]</math> denote the set of all polynomials with integer coefficients. Given <math>f\in\mathbb{Z}[x]</math>, let <math>\mathcal{P}(f)</math> denote the set of those primes that divide at least one of the numbers in the sequence <math>\{f(n)\}_{n\geq 0}</math>. The solution is based on the following lemma. | ||
+ | |||
+ | '''Lemma.''' If <math>f\in\mathbb{Z}[x]</math> is a nonconstant polynomial then <math>\mathcal{P}(f)</math> is infinite. | ||
+ | |||
+ | ''Proof.'' Repeated use will be made of the following basic fact: if <math>a</math> and <math>b</math> are distinct integers and <math>f\in\mathbb{Z}[x]</math>, then <math>a - b</math> divides <math>f(a) - f(b)</math>. If <math>f(0) = 0</math>, then <math>p</math> divides <math>f(p)</math> for every prime <math>p</math>, so <math>\mathcal{P}(f)</math> is infinite. If <math>f(0) = 1</math>, then every prime divisor <math>p</math> of <math>f(n!)</math> satisfies <math>p > n</math>. Otherwise <math>p</math> divides <math>n!</math>, which in turn divides <math>f(n!) - f(0) = f(n!) - 1</math>. This yields <math>p|1</math>, which is false. Hence <math>f(0) = 1</math> implies that <math>\mathcal{P}(f)</math> is infinite. To complete the proof, set <math>g(x) = f(f(0)x)/f(0)</math> and observe that <math>g\in\mathcal{Z}[x]</math> and <math>g(0) = 1</math>. The preceding argument shows that <math>\mathcal{P}(g)</math> is infinite, and it follows that <math>\mathcal{P}(f)</math> is infinite. <math>\blacksquare</math> | ||
+ | |||
+ | Suppose <math>f\in\mathbb{Z}[x]</math> is nonconstant and there exists a number <math>M</math> such that <math>p(f(n^2)) - 2n\leq M</math> for all <math>n\geq 0</math>. Application of the lemma to <math>f(x^2)</math> shows that there is an infinite sequence of distinct primes <math>\{p_j\}</math> and a corresponding infinite sequence of nonnegative integers <math>\{k_j\}</math> such that <math>p_j|f(k_j)^2</math> for all <math>j\geq 1</math>. Consider the sequence <math>\{r_j\}</math> where <math>r_j = \min\{k_j\pmod{p_j}, p_j - k_j\pmod{p_j}\}</math>. Then <math>0\leq r_j\leq (p_j - 1)/2</math> and <math>p_j|f(r_j)^2</math>. Hence <math>2r_j + 1\leq p_j\leq p(f(r_j^2))\leq M + 2r_j</math>, so <math>1\leq p_j - 2r_\leq M</math> for all <math>j\geq 1</math>. It follows that there is an integer <math>a_1</math> such that <math>1\leq a_1\leq M</math> and <math>a_1 = p_j - 2r_j</math> for infinitely many <math>j</math>. Let <math>m = \deg f</math>. Then <math>p_j|4^mf(((p_j - a_1)/2)^2)</math> and <math>4^mf(((x - a_1)/2)^2)\in\mathbb{Z}[x]</math>. Consequently, <math>p_j|f((a_1/2)^2)</math> for infinitely many <math>j</math>, which shows that <math>(a_1/2)^2</math> is a zero of <math>f</math>. Since <math>f(n^2)\leq 0</math> for <math>n\geq 0</math>, <math>a_1</math> must be odd. Then <math>f(x) = (4x - a_1)^2g(x)</math>, where <math>g\in\mathbb{Z}[x]</math>. (See the note below.) Observe that <math>\{p(g(n^2)) - 2n\}_{n\geq 0}</math> must be bounded above. If <math>g</math> is constant, we are done. If <math>g</math> is nonconstant, the argument can be repeated to show that <math>f</math> is given by <math>(*)</math>. | ||
+ | |||
+ | ''Note.'' The step that gives <math>f(x) = (4x - a_1^2)g(x)</math> where <math>g\in\mathbb{Z}[x]</math> follows immediately using a lemma of Gauss. The use of such an advanced result can be avoided by first writing <math>f(x) = r(4x - a_1^2)g(x)</math> where <math>r</math> is rational and <math>g\in\mathbb{Z}[x]</math>. Then continuation gives <math>f(x) = c(4x - a_1^2)\cdots (4x - a_k^2)</math> where <math>c</math> is rational and the <math>a_i</math> are odd. Consideration of the leading coefficient shows that the denominator of <math>c</math> is <math>2^s</math> for some <math>s\geq 0</math> and consideration of the constant term shows that the denominator is odd. Hence <math>c</math> is an integer. | ||
{{alternate solutions}} | {{alternate solutions}} | ||
Line 63: | Line 78: | ||
* <url>viewtopic.php?t=84553 Discussion on AoPS/MathLinks</url> | * <url>viewtopic.php?t=84553 Discussion on AoPS/MathLinks</url> | ||
− | {{USAMO newbox|year=2006|num-b= | + | {{USAMO newbox|year=2006|num-b=2|num-a=4}} |
− | [[Category:Olympiad | + | [[Category:Olympiad Number Theory Problems]] |
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 13:48, 11 April 2020
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:
Solution 2
The polynomial has the required properties if and only if
where
are odd positive integers and
is a nonzero integer. It is straightforward to verify that polynomials given by
have the required property. If
is a prime divisor of
but not of
, then
or
for some
. Hence
. The prime divisors of
form a finite set and do not affect whether or not the given sequence is bounded above. The rest of the proof is devoted to showing that any
for which
is bounded above is given by
.
Let denote the set of all polynomials with integer coefficients. Given
, let
denote the set of those primes that divide at least one of the numbers in the sequence
. The solution is based on the following lemma.
Lemma. If is a nonconstant polynomial then
is infinite.
Proof. Repeated use will be made of the following basic fact: if and
are distinct integers and
, then
divides
. If
, then
divides
for every prime
, so
is infinite. If
, then every prime divisor
of
satisfies
. Otherwise
divides
, which in turn divides
. This yields
, which is false. Hence
implies that
is infinite. To complete the proof, set
and observe that
and
. The preceding argument shows that
is infinite, and it follows that
is infinite.
Suppose is nonconstant and there exists a number
such that
for all
. Application of the lemma to
shows that there is an infinite sequence of distinct primes
and a corresponding infinite sequence of nonnegative integers
such that
for all
. Consider the sequence
where
. Then
and
. Hence
, so
for all
. It follows that there is an integer
such that
and
for infinitely many
. Let
. Then
and
. Consequently,
for infinitely many
, which shows that
is a zero of
. Since
for
,
must be odd. Then
, where
. (See the note below.) Observe that
must be bounded above. If
is constant, we are done. If
is nonconstant, the argument can be repeated to show that
is given by
.
Note. The step that gives where
follows immediately using a lemma of Gauss. The use of such an advanced result can be avoided by first writing
where
is rational and
. Then continuation gives
where
is rational and the
are odd. Consideration of the leading coefficient shows that the denominator of
is
for some
and consideration of the constant term shows that the denominator is odd. Hence
is an integer.
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 2 |
Followed by Problem 4 | |
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.