Difference between revisions of "2007 USAMO Problems/Problem 1"
Jschroeder (talk | contribs) (→Problem) |
|||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | (''Sam Vandervelde'') Let <math>n</math> be a [[positive]] [[integer]]. Define a [[sequence]] by setting <math>a_1 = n</math> and, for each <math>k>1</math>, letting <math>a_k</math> be the unique integer in the range <math>0 \le a_k \le k-1</math> for which <math>a_1 + a_2 + \cdots + a_k</math> is [[divisible]] by <math>k</math>. For instance, when <math>n=9</math> the obtained sequence is <math>9, 1, 2, 0, 3, 3, 3, \ldots</math>. Prove that for any <math>n</math> the sequence <math>a_1, a_2, a_3, \ldots</math> eventually becomes [[constant]]. | + | (''Sam Vandervelde'') Let <math>n</math> be a [[positive]] [[integer]]. Define a [[sequence]] by setting <math>a_1 = n</math> and, for each <math>k>1</math>, letting <math>a_k</math> be the unique integer in the range <math>0 \le a_k \le k-1</math> for which <math>a_1 + a_2 + \cdots + a_k</math> is [[divisible]] by <math>k</math>. For instance, when <math>n=9</math> the obtained sequence is <math>9, 1, 2, 0, 3, 3, 3, \ldots</math>. Prove that for any <math>n</math> the sequence <math>a_1, a_2, a_3, \ldots</math> eventually becomes [[constant]]. ho hum |
== Solutions == | == Solutions == |
Revision as of 19:06, 23 August 2023
Contents
Problem
(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. ho hum
Solutions
Solution 1
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.
Solution 2
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.
Solution 3
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.
End Lemma
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 .
Solution 4
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
Solution 5(like solution 2)
First, we may make an observation and say that for , must occur for the whole sum to be divisible by . Thus, the following is apparent: Then, we may make another observation that when , the sum also has to be divisible by n. We may then explore when n=k: and Then, Also, for . This is because: This must be true since will be divisible by and , we may then generalize this to all Thus, we may say that the sequence must converge to some integer value when .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>viewtopic.php?t=145842 Discussion on AoPS/MathLinks</url>
2007 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.