Difference between revisions of "1993 USAMO Problems/Problem 4"
(Created page with '== Problem 4== 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 …') |
m (→Resources) |
||
(6 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 | + | <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 == | ||
+ | |||
+ | <b>Part 1</b>) Prove that <math>f_n</math> is constant for sufficiently large <math>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>0</math> since average of <math>2</math> positive number is always positive. | ||
+ | |||
+ | <br/> | ||
+ | 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> | ||
+ | |||
+ | 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/> | ||
+ | <hr/> | ||
+ | <br/> | ||
+ | |||
+ | <b>Part 2</b>) Show that the constant is <math>\gcd(a,b)</math>. | ||
+ | |||
+ | For any <math>f_n</math> where <math>\gcd(a,b)=d\ne1</math>. <math>f_n=dg_n</math> for <math>g_n</math> with the same property except with <math>g_1=\frac{a}{d}</math> and <math>g_2=\frac{b}{d}</math>. | ||
+ | |||
+ | Therefore, if I prove that the constant for any <math>f_n</math> with relatively prime <math>a</math>, <math>b</math> is <math>1</math>, then I have shown that <b>part 2</b> is true. | ||
+ | |||
+ | <br/> | ||
+ | <b>Lemma</b>) If <math>\gcd(f_n,f_{n-1})=1</math>, then <math>\gcd(f_n,f_{n+1})=1</math>. | ||
+ | |||
+ | Assume for contradiction that <math>\gcd(f_n,f_{n+1})=d\ne1</math>, since both <math>f_n</math> and <math>f_{n+1}</math> are odd, <math>d</math> is not divisible by <math>2</math>. | ||
+ | |||
+ | <math>f_{n+1}=\frac{f_n+f_{n-1}}{2^n}</math> for some <math>n\in \mathbb{Z}^+</math> such that <math>f_{n+1}</math> is odd. | ||
− | == | + | <math>(2^n)f_{n+1}-f_n=f_{n-1}</math> |
+ | |||
+ | <math>d(p+q)=f_{n-1}</math>, where <math>p</math> and <math>q</math> is another integer. | ||
+ | |||
+ | Thus, <math>f_{n-1}</math> is divisible by <math>d</math> which contradicts with the assumption that <math>\gcd(f_n,f_{n-1})=1</math>. | ||
+ | |||
+ | <b>Lemma proven</b> | ||
+ | |||
+ | <br/> By induction, <math>\gcd(f_n,f_{n-1})=1</math> since <math>\gcd(a,b)=\gcd(f_1,f_2)=1</math>. | ||
+ | |||
+ | Since there must exist some <math>n</math> where <math>f_n=f_{n+1}</math> (part 1), <math>\gcd(f_n,f_{n+1})=f_n=1</math>. | ||
− | + | <P align="right"><math>\mathbb{Q.E.D}</math></P> | |
− | == | + | == 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 , be odd positive integers. Define the sequence by putting , , and by letting for be the greatest odd divisor of . Show that is constant for sufficiently large and determine the eventual value as a function of and .
Solution
Part 1) Prove that is constant for sufficiently large .
Note that if there is some for any , then , which is odd. Thus, and by induction, all is constant for .
Also note that since average of positive number is always positive.
Thus, assume for contradiction, , .
Then, ,
Thus, and that means that is a strictly decreasing function and it must reach as , which contradict with the fact that .
Part 1 proven.
Part 2) Show that the constant is .
For any where . for with the same property except with and .
Therefore, if I prove that the constant for any with relatively prime , is , then I have shown that part 2 is true.
Lemma) If , then .
Assume for contradiction that , since both and are odd, is not divisible by .
for some such that is odd.
, where and is another integer.
Thus, is divisible by which contradicts with the assumption that .
Lemma proven
By induction, since .
Since there must exist some where (part 1), .
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.