Difference between revisions of "2006 USAMO Problems/Problem 3"
Ragnarok23 (talk | contribs) |
Kevinmathz (talk | contribs) (→Problem) |
||
(18 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | == Solution == | + | (''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>.) |
− | == See | + | |
− | *[[ | + | == Solutions == |
+ | |||
+ | === Solution 1 === | ||
+ | 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 | ||
+ | coefficients of <math>f</math> (otherwise consider the polynomial obtained by | ||
+ | dividing <math>f</math> by the gcd of its coefficients). We further normalize | ||
+ | <math>f</math> by multiplying by <math>-1</math>, if necessary, to ensure that the | ||
+ | leading coefficient (of <math>x^d</math>) is positive. | ||
+ | |||
+ | Let <math>g(n) = f(n^2)</math>, then <math>g(n)</math> is a polynomial of degree <math>2</math> or | ||
+ | more and <math>g(n) = g(-n)</math>. Let <math>g_1, \ldots, g_k</math> be the factorization | ||
+ | of <math>g</math> into irreducible factors with positive leading coefficients. | ||
+ | Such a factorization is unique. Let <math>d(g_i)</math> denote the degree of | ||
+ | <math>g_i</math>. Since <math>g(-n) = g(n)</math> the factors <math>g_i</math> are either even | ||
+ | functions of <math>n</math> or come in pairs <math>(g_i, h_i)</math> with <math>g_i(-n) = | ||
+ | (-1)^{d(g_i)} h_i(n)</math>. | ||
+ | |||
+ | Let <math>P(0) = \infty</math>, <math>P(\pm 1) = 1</math>. For any other integer <math>m</math> let | ||
+ | <math>P(m)</math> be the largest prime factor of <math>m</math>. | ||
+ | |||
+ | Suppose that for some finite constant <math>C</math> and all <math>n \ge 0</math> we have | ||
+ | <math>P(g(n)) - 2n < C</math>. Since the polynomials <math>g_i</math> divide <math>g</math>, the | ||
+ | same must be true for each of the irreducible polynomials <math>g_i</math>. | ||
+ | |||
+ | A theorem of T. Nagell implies that if <math>d(g_i) \ge 2</math> the ratio | ||
+ | <math>P(g_i(n))/n</math> is unbounded for large values of <math>n</math>. Since in our case the <math>P(g_i(n))/n</math> is asymptotically bounded above | ||
+ | by <math>2</math> for large <math>n</math>, we conclude that all the irreducible | ||
+ | factors <math>g_i</math> are linear. Since linear polynomials are not even | ||
+ | functions of <math>n</math>, they must occur in pairs <math>g_i(n) = a_in + b_i</math>, | ||
+ | <math>h_i(n) = a_in - b_i</math>. Without loss of generality, <math>b_i \ge 0</math>. | ||
+ | Since the coefficients of <math>f</math> are relatively prime, so are <math>a_i</math> | ||
+ | and <math>b_i</math>, and since <math>P(0) = \infty</math>, neither polynomial can have | ||
+ | any non-negative integer roots, so <math>a_i > 1</math> and thus <math>b_i > 0</math>. | ||
+ | |||
+ | On the other hand, by Dirichlet's theorem, <math>a_i \le 2</math>, since | ||
+ | otherwise the sequence <math>a_in + b_i</math> would yield infinitely many | ||
+ | prime values with <math>P(g_i(n)) = a_in + b_i \ge 3n.</math> So <math>a_i = 2</math> and | ||
+ | therefore <math>b_i</math> is a positive odd integer. Setting <math>b_i = 2c_i + | ||
+ | 1</math>, clearly <math>P(g_i(n)) - 2n < 2c_i + 2</math>. Since this holds for each | ||
+ | factor <math>g_i</math>, it is true for the product <math>g</math> of all the factors | ||
+ | with the bound determined by the factor with the largest value of | ||
+ | <math>c_i</math>. | ||
+ | |||
+ | Therefore, for suitable non-negative integers <math>c_i</math>, <math>g(n)</math> is a | ||
+ | product of polynomials of the form <math>4n^2 - (2c_i + 1)^2</math>. Now, | ||
+ | since <math>g(n) = f(n^2)</math>, we conclude that <math>f(n)</math> is a product of | ||
+ | linear factors of the form <math>4n - (2c_i + 1)^2</math>. | ||
+ | |||
+ | 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 <math>M</math>. Thus for a suitable non-zero integer | ||
+ | <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> | ||
+ | |||
+ | === 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}} | ||
+ | |||
+ | == See also == | ||
+ | * <url>viewtopic.php?t=84553 Discussion on AoPS/MathLinks</url> | ||
+ | |||
+ | {{USAMO newbox|year=2006|num-b=2|num-a=4}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 12:48, 11 April 2020
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:
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.