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
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 2
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 |