2007 USAMO Problems/Problem 1
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
Define , and
. If
, then for
,
. Note that
is a permissible value of
since
: if we substitute
for
, we get
, the unique value for
. So
, from which if follows that the
s become constant.
Now we must show that eventually . Suppose that
for all
. By definition,
, so
. Also, for
, each
so
![$k^2 < s_k \le n + 1 + 2 + \cdots + (k-1) = n + \frac{k^2 - k}2$](http://latex.artofproblemsolving.com/b/4/1/b41f09ceb924aad20b2c9c86594295ce248b37da.png)
![$k^2 < n +\frac{k^2 - k}2 \Longrightarrow \frac{k^2 + k}2 < n$](http://latex.artofproblemsolving.com/6/a/5/6a58080e8631e9d8ebaed5c4af4e03dd94c16aa0.png)
But is constant while
is increasing, so eventually we will have a contradiction and
. Therefore, the sequence of
s will become constant.
Solution 2
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 3
Let . Since
, we have that
.
. 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 |