2007 USAMO Problems/Problem 1
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 |