Difference between revisions of "2007 USAMO Problems/Problem 1"
(what I wrote (am I right?)) |
|||
Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
+ | Suppose we create a parallel integer sequence <math>\displaystyle b_1, b_2, \ldots</math> such that for every <math>\displaystyle k \ge 1</math>, we have that <math>b_k = \frac{\displaystyle \sum_{i=1}^{k}}{k}</math>. Consider what happens when <math>b_k \le k</math>. For <math>\displaystyle k + 1</math>, we have that <math>b_{k+1} = \frac{\displaystyle \sum_{i=1}^{k+1}}{k+1} = \frac{\displaystyle \sum_{i=1}^{k} + a_{k+1}}{k+1} = \frac{b_k \times k + a_{k+1}}{k+1}</math>. <math>\displaystyle b_k</math> is a permissible value of <math> a_{k+1} \displaystyle </math> since <math>b_k \le k \le (k+1)-1</math>: if we substitute <math>\displaystyle b_k</math> for <math> a_{k+1} \displaystyle </math>, we get that <math>b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k</math>. <math>\displaystyle b_k</math> is the unique value for <math> a_{k+1} \displaystyle </math>. We can repeat this argument for <math>\displaystyle b_k = b_{k+1} = b_{k+2} \ldots</math>. As we substituted the <math>\displaystyle b_k</math>s for the <math>\displaystyle a_k</math>s, the <math>\displaystyle a_k</math>s also become constant. | ||
+ | |||
+ | Now we must show that <math>\displaystyle b_k</math> eventually <math>\le k</math>. Suppose that <math>\displaystyle b_k</math> always <math>\displaystyle > k</math>. By definition, <math> \frac{\displaystyle \sum_{i=1}^{k}}{k} = b_k > k</math>, so <math>\displaystyle \sum_{i=1}^{k} a_i > k^2</math>. We also have that each <math>a_i \le i-1</math> so that <math>k^2 < \displaystyle \sum_{i=1}^{k} \le n + 1 + 2 + \ldots + (k-1) = n + \frac{k^2 - k}2 </math>. So <math>k^2 < n +\frac{k^2 - k}2 \Longrightarrow \frac{k^2 + k}2 < n</math>. But <math>\displaystyle n</math> is constant while <math>\displaystyle k</math> is increasing, so eventually we will have a contradiction and <math>b_k \le k</math>. Therefore, the sequence of <math>\displaystyle a_i</math>s will become constant. | ||
+ | |||
{{USAMO newbox|year=2007|before=First question|num-a=2}} | {{USAMO newbox|year=2007|before=First question|num-a=2}} |
Revision as of 17:46, 25 April 2007
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
Suppose we create a parallel integer sequence such that for every , we have that . Consider what happens when . For , we have that . is a permissible value of since : if we substitute for , we get that . is the unique value for . We can repeat this argument for . As we substituted the s for the s, the s also become constant.
Now we must show that eventually . Suppose that always . By definition, , so . We also have that each so that . So . But is constant while is increasing, so eventually we will have a contradiction and . Therefore, the sequence of s will become constant.
2007 USAMO (Problems • Resources) | ||
Preceded by First question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |