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 "1995 USAMO Problems/Problem 4"

(Created page with "Suppose <math>q_1,q_2,...</math> is an infinite sequence of integers satisfying the following two conditions: (a) <math>m - n </math> divides <math>q_m - q_n</math> for <math>m>...")
 
(→‎Solution)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
==Problem==
 
Suppose <math>q_1,q_2,...</math> is an infinite sequence of integers satisfying the following two conditions:
 
Suppose <math>q_1,q_2,...</math> is an infinite sequence of integers satisfying the following two conditions:
  
Line 6: Line 7:
  
 
Prove that there is a polynomial <math>Q</math> such that <math>q_n = Q(n)</math> for each <math>n</math>.
 
Prove that there is a polynomial <math>Q</math> such that <math>q_n = Q(n)</math> for each <math>n</math>.
 +
 +
==Solution==
 +
Step 1: Suppose <math>P</math> has degree <math>d</math>. Let <math>Q</math> be the polynomial of degree at most <math>d</math> with <math>Q(x)=q_x</math> for <math>0\leq x\leq d</math>. Since the <math>q_x</math> are all integers, <math>Q</math> has rational coefficients, and there exists <math>k</math> so that <math>kQ</math> has integer coefficients. Then <math>m-n|kQ(m)-kQ(n)</math> for all <math>m,n\in \mathbb N_0</math>.
 +
 +
Step 2: We show that <math>Q</math> is the desired polynomial.
 +
 +
Let <math>x>n</math> be given. Now
 +
<cmath>kq_x\equiv kq_m\pmod{x-m}\text{ for all integers }m\in[0,d]</cmath>
 +
Since <math>kQ(x)</math> satisfies these relations as well, and <math>kq_m=kQ(m)</math>,
 +
<cmath>kq_x\equiv kQ(x)\pmod{x-m}\text{ for all integers }m\in[0,d]</cmath>
 +
and hence
 +
<cmath>kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1)
 +
</cmath>
 +
Now
 +
<cmath>\begin{align*}
 +
\text{lcm}(x,x-1,\ldots, x-i-1)&=\text{lcm}[\text{lcm}(x,x-1,\ldots, x-i),x-i-1]\\
 +
&=\frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[\text{lcm}(x,x-1,\ldots, x-i),(x-i-1)]}\\
 +
&\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[x(x-1)\cdots(x-i),(x-i-1)]}\\
 +
&\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{(i+1)!}
 +
\end{align*}</cmath>
 +
so by induction <math>\text{lcm}(x,x-1,\ldots, x-d)\geq \frac{x(x-1)\cdots (x-d)}{d!(d-1)!\cdots 1!}</math>. Since <math>P(x), Q(x)</math> have degree <math>d</math>, for large enough <math>x</math> (say <math>x>L</math>) we have <math>\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)</math>. By (1) <math>kq_x</math> must differ by a multiple of <math>\text{lcm}(x,x-1,\ldots, x-d)</math> from <math>kQ(x)</math>; hence <math>q_x</math> must differ by a multiple of <math>\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}</math> from <math>Q(x)</math>, and for <math>x>L</math> we must have <math>q_x=Q(x)</math>.
 +
 +
Now for any <math>y</math> we have <math>kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}</math> for any <math>x>L</math>. Since <math>x-y</math> can be arbitrarily large, we must have <math>Q(y)=q_y</math>, as needed.
 +
 +
==See Also==
 +
{{USAMO box|year=1995|num-b=3|num-a=5}}
 +
{{MAA Notice}}
 +
[[Category:Olympiad Algebra Problems]]

Latest revision as of 14:27, 11 May 2018

Problem

Suppose $q_1,q_2,...$ is an infinite sequence of integers satisfying the following two conditions:

(a) $m - n$ divides $q_m - q_n$ for $m>n \geq 0$

(b) There is a polynomial $P$ such that $|q_n|<P(n)$ for all $n$.

Prove that there is a polynomial $Q$ such that $q_n = Q(n)$ for each $n$.

Solution

Step 1: Suppose $P$ has degree $d$. Let $Q$ be the polynomial of degree at most $d$ with $Q(x)=q_x$ for $0\leq x\leq d$. Since the $q_x$ are all integers, $Q$ has rational coefficients, and there exists $k$ so that $kQ$ has integer coefficients. Then $m-n|kQ(m)-kQ(n)$ for all $m,n\in \mathbb N_0$.

Step 2: We show that $Q$ is the desired polynomial.

Let $x>n$ be given. Now \[kq_x\equiv kq_m\pmod{x-m}\text{ for all integers }m\in[0,d]\] Since $kQ(x)$ satisfies these relations as well, and $kq_m=kQ(m)$, \[kq_x\equiv kQ(x)\pmod{x-m}\text{ for all integers }m\in[0,d]\] and hence \[kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1)\] Now \begin{align*} \text{lcm}(x,x-1,\ldots, x-i-1)&=\text{lcm}[\text{lcm}(x,x-1,\ldots, x-i),x-i-1]\\ &=\frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[\text{lcm}(x,x-1,\ldots, x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[x(x-1)\cdots(x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{(i+1)!} \end{align*} so by induction $\text{lcm}(x,x-1,\ldots, x-d)\geq \frac{x(x-1)\cdots (x-d)}{d!(d-1)!\cdots 1!}$. Since $P(x), Q(x)$ have degree $d$, for large enough $x$ (say $x>L$) we have $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$. By (1) $kq_x$ must differ by a multiple of $\text{lcm}(x,x-1,\ldots, x-d)$ from $kQ(x)$; hence $q_x$ must differ by a multiple of $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ from $Q(x)$, and for $x>L$ we must have $q_x=Q(x)$.

Now for any $y$ we have $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ for any $x>L$. Since $x-y$ can be arbitrarily large, we must have $Q(y)=q_y$, as needed.

See Also

1995 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5
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=1995_USAMO_Problems/Problem_4&oldid=94418"