Difference between revisions of "2007 USAMO Problems/Problem 1"
Mathcrazed (talk | contribs) (→Solution 3) |
Mathcrazed (talk | contribs) (→Solution 3) |
||
Line 27: | Line 27: | ||
=== Solution 3 === | === Solution 3 === | ||
Let <math>a_1=n</math>. Since <math>a_k\le k-1</math>, we have that <math>a_1+a_2+a_3+\hdots+a_n\le n+1+2+\hdots+n-1</math>. | Let <math>a_1=n</math>. Since <math>a_k\le k-1</math>, we have that <math>a_1+a_2+a_3+\hdots+a_n\le n+1+2+\hdots+n-1</math>. | ||
+ | |||
Thus, <math>a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}</math>. | Thus, <math>a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}</math>. | ||
+ | |||
Since <math>a_1+a_2+\hdots+a_n=nk</math>, for some integer <math>k</math>, we can keep adding <math>k</math> to satisfy the conditions, provided that <math>k\le n</math> because <math>a_n+1\le n</math>. | Since <math>a_1+a_2+\hdots+a_n=nk</math>, for some integer <math>k</math>, we can keep adding <math>k</math> to satisfy the conditions, provided that <math>k\le n</math> because <math>a_n+1\le n</math>. | ||
Revision as of 09:12, 1 April 2008
Problem
Let be a positive integer. Define a sequence by setting and, for each , letting be the unique integer in the range for which is divisible by . For instance, when the obtained sequence is . Prove that for any the sequence eventually becomes constant.
Solution
Solution 1
Define , and . If , then for , . Note that is a permissible value of since : if we substitute for , we get , the unique value for . So , from which if follows that the s become constant.
Now we must show that eventually . Suppose that for all . By definition, , so . Also, for , each so
But is constant while is increasing, so eventually we will have a contradiction and . Therefore, the sequence of s will become constant.
Solution 2
By the above, we have that
, and by definition, . Thus, . Also, both are integers, so . As the s form a non-increasing sequence of positive integers, they must eventually become constant.
Therefore, for some sufficiently large value of . Then , so eventually the sequence becomes constant.
Solution 3
Let . Since , we have that .
Thus, .
Since , for some integer , we can keep adding to satisfy the conditions, provided that because .
Because , the sequence must eventually become constant.
See also
2007 USAMO (Problems • Resources) | ||
Preceded by First question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |