2007 USAMO Problems/Problem 1
(Sam Vandervelde) 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.
Let and . Thus, because , , and by definition, . Thus, . Also, both and 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.
Let . Since , we have that Since for some integer , we can keep adding to satisfy the conditions, provided that . This is true since , so the sequence must eventually become constant.
Define , and . By the problem hypothesis, is an integer valued sequence.
Lemma: There exists a such that .
Proof: Choose any such that . Then as desired.
Let be the smallest such that . Then , and . To make an integer, must be divisible by . Thus, because is divisible by , , and, because , . Then as well. Repeating the same process using instead of gives , and an easy induction can prove that for all , . Thus, becomes a constant function for arbitrarily large values of .
For , let We claim that for some we have . To this end, consider the sequence which computes the differences between and , i.e., whose -th term is . Note that the first term of this sequence is positive (it is equal to ) and that its terms are strictly decreasing since Further, a negative term cannot immediately follow a positive term. Suppose otherwise, namely that and . Since and are divisible by and , respectively, we can tighten the above inequalities to and . But this would imply that , a contradiction. We conclude that the sequence of differences must eventually include a term equal to zero.
Let be a positive integer such that . We claim that This follows from the fact that the sequence is uniquely determined and choosing , for , satisfies the range condition and yields
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
- <url>viewtopic.php?t=145842 Discussion on AoPS/MathLinks</url>
|2007 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|