Difference between revisions of "2007 USAMO Problems/Problem 1"
(→Solution: duplicate solutions...) |
Quantumbyte (talk | contribs) (→Solution 2) |
||
Line 21: | Line 21: | ||
Thus, <math>a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}</math>. | Thus, <math>a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}</math>. | ||
− | Since <math>a_1+a_2+\hdots+a_n=nk</math>, for some integer <math>k</math>, we can keep adding <math>k</math> to satisfy the conditions, provided that <math>k\le n</math> because <math> | + | Since <math>a_1+a_2+\hdots+a_n=nk</math>, for some integer <math>k</math>, we can keep adding <math>k</math> to satisfy the conditions, provided that <math>k\le n</math> because <math>a_{n+1}\le n</math>. |
Because <math>k\le \frac{n+1}{2}\le n</math>, the sequence must eventually become constant. | Because <math>k\le \frac{n+1}{2}\le n</math>, the sequence must eventually become constant. |
Revision as of 23:52, 17 March 2012
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
![$b_{k+1} = \frac{b_k \cdot k + a_{k+1}}{k+1} = \left(\frac{k}{k+1}\right) \cdot b_k + \frac{a_{k+1}}{k+1}$](http://latex.artofproblemsolving.com/0/e/9/0e92bc48e4ac4f62b7a9759d670c4556ae7bd7cc.png)
, 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 |