Difference between revisions of "2007 USAMO Problems/Problem 1"
(→Solution 3) |
m (→Solution 1: Fix capitalization.) |
||
Line 14: | Line 14: | ||
<math>\frac{k}{k+1} < 1</math>, and by definition, <math>\frac{a_{k+1}}{k+1} < 1</math>. Thus, <math>b_{k+1} < b_k + 1</math>. Also, both <math>b_k,\ b_{k+1}</math> are integers, so <math>b_{k+1} \le b_k</math>. As the <math>b_k</math>s form a [[non-increasing]] sequence of positive integers, they must eventually become constant. | <math>\frac{k}{k+1} < 1</math>, and by definition, <math>\frac{a_{k+1}}{k+1} < 1</math>. Thus, <math>b_{k+1} < b_k + 1</math>. Also, both <math>b_k,\ b_{k+1}</math> are integers, so <math>b_{k+1} \le b_k</math>. As the <math>b_k</math>s form a [[non-increasing]] sequence of positive integers, they must eventually become constant. | ||
− | Therefore, <math>b_k = b_{k+1}</math> for some sufficiently large value of <math>k</math>. Then <math>a_{k+1} = | + | Therefore, <math>b_k = b_{k+1}</math> for some sufficiently large value of <math>k</math>. Then <math>a_{k+1} = S_{k+1} - S_k = b_k(k + 1) - b_k(k) = b_k</math>, so eventually the sequence <math>a_k</math> becomes constant. |
=== Solution 2 === | === Solution 2 === |
Revision as of 15:38, 10 June 2014
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
Let and . Thus, because ,
, 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.
Solution 3
Define , and . By the problem hypothesis, is an integer valued sequence.
Lemma: The exists a such that .
Proof: Choose any such that . Then: as desired.
Let k be the smallest k 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 k.
Note: This solution is a formalization of the second solution. Also, the lemma could have been simplified if I chose k = n, which is exactly the second solution's thought process.
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.