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

(→‎Solution)
m (→‎Resources)
 
(5 intermediate revisions by 4 users not shown)
Line 2: Line 2:
  
 
Let <math>a</math>, <math>b</math> be odd positive integers. Define the sequence <math>(f_n)</math> by putting <math>f_1 = a</math>,
 
Let <math>a</math>, <math>b</math> be odd positive integers. Define the sequence <math>(f_n)</math> by putting <math>f_1 = a</math>,
−
<math>f_2 = b</math>, and by letting fn for <math>n\ge3</math> be the greatest odd divisor of <math>f_{n-1} + f_{n-2}</math>.
+
<math>f_2 = b</math>, and by letting <math>f_n</math> for <math>n\ge3</math> be the greatest odd divisor of <math>f_{n-1} + f_{n-2}</math>.
 
Show that <math>f_n</math> is constant for <math>n</math> sufficiently large and determine the eventual
 
Show that <math>f_n</math> is constant for <math>n</math> sufficiently large and determine the eventual
 
value as a function of <math>a</math> and <math>b</math>.
 
value as a function of <math>a</math> and <math>b</math>.
−
 
  
 
== Solution ==
 
== Solution ==
Line 13: Line 12:
 
Note that if there is some <math>f_n=f_{n-1}</math> for any <math>n</math>, then <math>\frac{f_{n}+f_{n-1}}{2}=f_n</math>, which is odd. Thus, <math>f_{n+1}=f_n=f_{n-1}</math> and by induction, all <math>f_p</math> is constant for <math>p\ge n</math>.
 
Note that if there is some <math>f_n=f_{n-1}</math> for any <math>n</math>, then <math>\frac{f_{n}+f_{n-1}}{2}=f_n</math>, which is odd. Thus, <math>f_{n+1}=f_n=f_{n-1}</math> and by induction, all <math>f_p</math> is constant for <math>p\ge n</math>.
  
−
Also note that <math>f_n\ge 0</math> since average of <math>2</math> positive number is always positive.
+
Also note that <math>f_n>0</math> since average of <math>2</math> positive number is always positive.
  
 
<br/>
 
<br/>
−
Thus, assume for contradiction, <math>_\nexists n</math>, <math>f_n=f_{n-1}</math>.
+
Thus, assume for contradiction, <math>\nexists n</math>, <math>f_n=f_{n-1}</math>.
  
 
Then, <math>f_{n+1}\le\frac{f_{n}+f_{n-1}}{2}< \max (f_{n},f_{n-1})</math>, <math>f_{n+2}\le\frac{f_{n+1}+f_{n}}{2}< \max (f_{n},f_{n+1})\le\max (f_{n},f_{n-1})</math>
 
Then, <math>f_{n+1}\le\frac{f_{n}+f_{n-1}}{2}< \max (f_{n},f_{n-1})</math>, <math>f_{n+2}\le\frac{f_{n+1}+f_{n}}{2}< \max (f_{n},f_{n+1})\le\max (f_{n},f_{n-1})</math>
  
−
Thus, <math>\max (f_{n},f{n-1})> \max (f_{n+1},f_{n+2})</math> and that means that <math>\max (f_{2n},f_{2n+1})</math> is a strictly decreasing function and it must reach <math>0</math> as <math>n\rightarrow\infty</math>, which contradict with the fact that <math>f_n\ge0</math>.
+
Thus, <math>\max (f_{n},f_{n-1})> \max (f_{n+1},f_{n+2})</math> and that means that <math>\max (f_{2n},f_{2n+1})</math> is a strictly decreasing function and it must reach <math>0</math> as <math>n\rightarrow\infty</math>, which contradict with the fact that <math>f_n>0</math>.
  
 
<br/><b>Part 1</b> proven.
 
<br/><b>Part 1</b> proven.
Line 55: Line 54:
 
<P align="right"><math>\mathbb{Q.E.D}</math></P>
 
<P align="right"><math>\mathbb{Q.E.D}</math></P>
  
−
== Resources ==
+
== See Also ==
  
 
{{USAMO box|year=1993|num-b=3|num-a=5}}
 
{{USAMO box|year=1993|num-b=3|num-a=5}}
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=356413#p356413 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=356413#p356413 Discussion on AoPS/MathLinks]
 +
{{MAA Notice}}
 +
 +
[[Category:Olympiad Number Theory Problems]]

Latest revision as of 06:56, 19 July 2016

Problem 4

Let $a$, $b$ be odd positive integers. Define the sequence $(f_n)$ by putting $f_1 = a$, $f_2 = b$, and by letting $f_n$ for $n\ge3$ be the greatest odd divisor of $f_{n-1} + f_{n-2}$. Show that $f_n$ is constant for $n$ sufficiently large and determine the eventual value as a function of $a$ and $b$.

Solution

Part 1) Prove that $f_n$ is constant for sufficiently large $n$.

Note that if there is some $f_n=f_{n-1}$ for any $n$, then $\frac{f_{n}+f_{n-1}}{2}=f_n$, which is odd. Thus, $f_{n+1}=f_n=f_{n-1}$ and by induction, all $f_p$ is constant for $p\ge n$.

Also note that $f_n>0$ since average of $2$ positive number is always positive.


Thus, assume for contradiction, $\nexists n$, $f_n=f_{n-1}$.

Then, $f_{n+1}\le\frac{f_{n}+f_{n-1}}{2}< \max (f_{n},f_{n-1})$, $f_{n+2}\le\frac{f_{n+1}+f_{n}}{2}< \max (f_{n},f_{n+1})\le\max (f_{n},f_{n-1})$

Thus, $\max (f_{n},f_{n-1})> \max (f_{n+1},f_{n+2})$ and that means that $\max (f_{2n},f_{2n+1})$ is a strictly decreasing function and it must reach $0$ as $n\rightarrow\infty$, which contradict with the fact that $f_n>0$.


Part 1 proven.



Part 2) Show that the constant is $\gcd(a,b)$.

For any $f_n$ where $\gcd(a,b)=d\ne1$. $f_n=dg_n$ for $g_n$ with the same property except with $g_1=\frac{a}{d}$ and $g_2=\frac{b}{d}$.

Therefore, if I prove that the constant for any $f_n$ with relatively prime $a$, $b$ is $1$, then I have shown that part 2 is true.


Lemma) If $\gcd(f_n,f_{n-1})=1$, then $\gcd(f_n,f_{n+1})=1$.

Assume for contradiction that $\gcd(f_n,f_{n+1})=d\ne1$, since both $f_n$ and $f_{n+1}$ are odd, $d$ is not divisible by $2$.

$f_{n+1}=\frac{f_n+f_{n-1}}{2^n}$ for some $n\in \mathbb{Z}^+$ such that $f_{n+1}$ is odd.

$(2^n)f_{n+1}-f_n=f_{n-1}$

$d(p+q)=f_{n-1}$, where $p$ and $q$ is another integer.

Thus, $f_{n-1}$ is divisible by $d$ which contradicts with the assumption that $\gcd(f_n,f_{n-1})=1$.

Lemma proven


By induction, $\gcd(f_n,f_{n-1})=1$ since $\gcd(a,b)=\gcd(f_1,f_2)=1$.

Since there must exist some $n$ where $f_n=f_{n+1}$ (part 1), $\gcd(f_n,f_{n+1})=f_n=1$.

$\mathbb{Q.E.D}$

See Also

1993 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=1993_USAMO_Problems/Problem_4&oldid=79531"