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"

(→‎Solution)
(→‎Problem)
 
(11 intermediate revisions by 5 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 \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>.)
  
−
For integral <math>\displaystyle m </math>, let <math> \displaystyle p(m) </math> be the greatest prime divisor of <math> \displaystyle m </math>. By convention, we set <math> p(\pm 1)=1</math> and <math>p(0)=\infty</math>. Find all polynomials <math>\displaystyle 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 25: Line 25:
 
Suppose that for some finite constant <math>C</math> and all <math>n \ge 0</math> we have
 
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
 
<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
+
same must be true for each of the irreducible polynomials <math>g_i</math>.
−
theorem of T.&nbsp;Nagell implies that if <math>d(g_i) \ge 2</math> the ratio
+
 
−
<math>P(g_i(n))/n</math> takes arbitrarily large values for <math>n</math> sufficiently
+
A theorem of T.&nbsp;Nagell implies that if <math>d(g_i) \ge 2</math> the ratio
−
large. Since in our case the <math>P(g_i(n))/n</math> is asymptotically bounded above
+
<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
 
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
 
factors <math>g_i</math> are linear. Since linear polynomials are not even
Line 49: Line 49:
 
product of polynomials of the form <math>4n^2 - (2c_i + 1)^2</math>.  Now,
 
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
 
since <math>g(n) = f(n^2)</math>, we conclude that <math>f(n)</math> is a product of
−
polynomials of the form <math>4n - (2c_i + 1)^2</math>.
+
linear factors of the form <math>4n - (2c_i + 1)^2</math>.
  
−
Since we restricted ourselves to non-constant polynomials with
+
Since we restricted ourselves to non-constant polynomials with  
 
relatively prime coefficients, we can now relax this condition and
 
relatively prime coefficients, we can now relax this condition and
−
admit a possibly empty list of <math>k \ge 0</math> irreducible factors as
+
admit a possibly empty list of linear factors as well as an arbitrary
−
well as an arbitrary non-zero integer multiple <math>M</math>. Thus for a
+
non-zero integer multiple <math>M</math>. Thus for a suitable non-zero integer
−
suitable non-zero integer <math>M</math> and a possibly empty set of <math>k</math>
+
<math>M</math> and <math>k \ge 0</math> non-negative integers <math>c_i</math>, we have: <cmath>f(n) = M
−
non-negative integers <math>c_i</math>, we have:
+
\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>
+
 
 +
=== 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 ==
+
== See also ==
 +
* <url>viewtopic.php?t=84553 Discussion on AoPS/MathLinks</url>
  
−
* [[2006 USAMO Problems]]
+
{{USAMO newbox|year=2006|num-b=2|num-a=4}}
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=490625#p490625 Discussion on AoPS/MathLinks]
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:48, 11 April 2020

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 \in \mathbb{Z} \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)\]

Solution 2

The polynomial $f$ has the required properties if and only if \[f(x) = c(4x - a_1^2)(4x - a_2^2)\cdots (4x - a_k^2),\qquad\qquad (*)\] where $a_1, a_2, \ldots, a_k$ are odd positive integers and $c$ is a nonzero integer. It is straightforward to verify that polynomials given by $(*)$ have the required property. If $p$ is a prime divisor of $f(n^2)$ but not of $c$, then $p|(2n - a_j)$ or $p|(2n + a_j)$ for some $j\leq k$. Hence $p - 2n\leq \max\{a_1, a_2, \ldots, a_k\}$. The prime divisors of $c$ 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 $f$ for which $\{p(f(n^2)) - 2n\}_{n\geq 0}$ is bounded above is given by $(*)$.

Let $\mathbb{Z}[x]$ denote the set of all polynomials with integer coefficients. Given $f\in\mathbb{Z}[x]$, let $\mathcal{P}(f)$ denote the set of those primes that divide at least one of the numbers in the sequence $\{f(n)\}_{n\geq 0}$. The solution is based on the following lemma.

Lemma. If $f\in\mathbb{Z}[x]$ is a nonconstant polynomial then $\mathcal{P}(f)$ is infinite.

Proof. Repeated use will be made of the following basic fact: if $a$ and $b$ are distinct integers and $f\in\mathbb{Z}[x]$, then $a - b$ divides $f(a) - f(b)$. If $f(0) = 0$, then $p$ divides $f(p)$ for every prime $p$, so $\mathcal{P}(f)$ is infinite. If $f(0) = 1$, then every prime divisor $p$ of $f(n!)$ satisfies $p > n$. Otherwise $p$ divides $n!$, which in turn divides $f(n!) - f(0) = f(n!) - 1$. This yields $p|1$, which is false. Hence $f(0) = 1$ implies that $\mathcal{P}(f)$ is infinite. To complete the proof, set $g(x) = f(f(0)x)/f(0)$ and observe that $g\in\mathcal{Z}[x]$ and $g(0) = 1$. The preceding argument shows that $\mathcal{P}(g)$ is infinite, and it follows that $\mathcal{P}(f)$ is infinite. $\blacksquare$

Suppose $f\in\mathbb{Z}[x]$ is nonconstant and there exists a number $M$ such that $p(f(n^2)) - 2n\leq M$ for all $n\geq 0$. Application of the lemma to $f(x^2)$ shows that there is an infinite sequence of distinct primes $\{p_j\}$ and a corresponding infinite sequence of nonnegative integers $\{k_j\}$ such that $p_j|f(k_j)^2$ for all $j\geq 1$. Consider the sequence $\{r_j\}$ where $r_j = \min\{k_j\pmod{p_j}, p_j - k_j\pmod{p_j}\}$. Then $0\leq r_j\leq (p_j - 1)/2$ and $p_j|f(r_j)^2$. Hence $2r_j + 1\leq p_j\leq p(f(r_j^2))\leq M + 2r_j$, so $1\leq p_j - 2r_\leq M$ for all $j\geq 1$. It follows that there is an integer $a_1$ such that $1\leq a_1\leq M$ and $a_1 = p_j - 2r_j$ for infinitely many $j$. Let $m = \deg f$. Then $p_j|4^mf(((p_j - a_1)/2)^2)$ and $4^mf(((x - a_1)/2)^2)\in\mathbb{Z}[x]$. Consequently, $p_j|f((a_1/2)^2)$ for infinitely many $j$, which shows that $(a_1/2)^2$ is a zero of $f$. Since $f(n^2)\leq 0$ for $n\geq 0$, $a_1$ must be odd. Then $f(x) = (4x - a_1)^2g(x)$, where $g\in\mathbb{Z}[x]$. (See the note below.) Observe that $\{p(g(n^2)) - 2n\}_{n\geq 0}$ must be bounded above. If $g$ is constant, we are done. If $g$ is nonconstant, the argument can be repeated to show that $f$ is given by $(*)$.

Note. The step that gives $f(x) = (4x - a_1^2)g(x)$ where $g\in\mathbb{Z}[x]$ follows immediately using a lemma of Gauss. The use of such an advanced result can be avoided by first writing $f(x) = r(4x - a_1^2)g(x)$ where $r$ is rational and $g\in\mathbb{Z}[x]$. Then continuation gives $f(x) = c(4x - a_1^2)\cdots (4x - a_k^2)$ where $c$ is rational and the $a_i$ are odd. Consideration of the leading coefficient shows that the denominator of $c$ is $2^s$ for some $s\geq 0$ and consideration of the constant term shows that the denominator is odd. Hence $c$ 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. AMC logo.png

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