Difference between revisions of "2007 USAMO Problems/Problem 1"
5849206328x (talk | contribs) m |
5849206328x (talk | contribs) m (→Solution 3) |
||
Line 33: | Line 33: | ||
as desired. | as desired. | ||
− | '''End Lemma | + | '''End Lemma''' |
Let <math>k</math> be the smallest <math>k</math> such that <math>b_k < k</math>. Then <math>b_k = m < k</math>, and <math>S_k = km</math>. To make <math>b_{k+1}</math> an integer, <math>S_{k+1} = S_k + a_{k+1}</math> must be divisible by <math>k+1</math>. Thus, because <math>km + m</math> is divisible by <math>k+1</math>, <math>a_{k+1} \equiv m \pmod{k+1}</math>, and, because <math>0 \le a_{k+1} < k</math>, <math>a_{k+1} = m</math>. Then <math>b_{k+1} = \frac{(k+1)m}{k+1} = m</math> as well. Repeating the same process using <math>k+1</math> instead of <math>k</math> gives <math>a_{k+2} = m</math>, and an easy induction can prove that for all <math>N > k+1</math>, <math>a_N = m</math>. Thus, <math>a_k</math> becomes a constant function for arbitrarily large values of <math>k</math>. | Let <math>k</math> be the smallest <math>k</math> such that <math>b_k < k</math>. Then <math>b_k = m < k</math>, and <math>S_k = km</math>. To make <math>b_{k+1}</math> an integer, <math>S_{k+1} = S_k + a_{k+1}</math> must be divisible by <math>k+1</math>. Thus, because <math>km + m</math> is divisible by <math>k+1</math>, <math>a_{k+1} \equiv m \pmod{k+1}</math>, and, because <math>0 \le a_{k+1} < k</math>, <math>a_{k+1} = m</math>. Then <math>b_{k+1} = \frac{(k+1)m}{k+1} = m</math> as well. Repeating the same process using <math>k+1</math> instead of <math>k</math> gives <math>a_{k+2} = m</math>, and an easy induction can prove that for all <math>N > k+1</math>, <math>a_N = m</math>. Thus, <math>a_k</math> becomes a constant function for arbitrarily large values of <math>k</math>. |
Revision as of 22:00, 12 August 2014
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.
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
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.