Difference between revisions of "1993 USAMO Problems/Problem 4"
(→Solution) |
m (→Solution) |
||
Line 13: | Line 13: | ||
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 | + | Also note that <math>f_n>0</math> since average of <math>2</math> positive number is always positive. |
<br/> | <br/> | ||
Line 20: | Line 20: | ||
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 | + | 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. |
Revision as of 18:53, 22 April 2010
Problem 4
Let , be odd positive integers. Define the sequence by putting , , and by letting fn 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), .
Resources
1993 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |