Difference between revisions of "2007 USAMO Problems/Problem 1"
m (→Solution 2) |
(→Solution 2) |
||
Line 13: | Line 13: | ||
=== Solution 2 === | === Solution 2 === | ||
− | Define <math>\displaystyle s_k=a_1+a_2+...+a_k</math>. If we have that <math>\displaystyle s_k=j*k</math> where <math>j</math> is an integer such that <math>0\le j\le k</math>, then we can take <math>\displaystyle a_{k+1}=j</math>, and we are done since <math>\displaystyle s_{k+1}=a_{k+1}+s_k=j+j* | + | Define <math>\displaystyle s_k=a_1+a_2+...+a_k</math>. If we have that <math>\displaystyle s_k=j*k</math> where <math>j</math> is an integer such that <math>0\le j\le k</math>, then we can take <math>\displaystyle a_{k+1}=j</math>, and we are done since <math>\displaystyle s_{k+1}=a_{k+1}+s_k=j+j*k=j*(k+1)</math>. |
We always know that <math>s_k</math> is a [[multiple]] of <math>k</math> by definition of the sequence. So we know an integer ,<math>j</math>, exists. But we also need the [[inequality]] (<math>0\le j\le k</math>) for <math>j</math> to be able to add <math>j</math> as the next term. We need that, for some <math>k</math>, <math>s_k=k*j\le k^2</math> | We always know that <math>s_k</math> is a [[multiple]] of <math>k</math> by definition of the sequence. So we know an integer ,<math>j</math>, exists. But we also need the [[inequality]] (<math>0\le j\le k</math>) for <math>j</math> to be able to add <math>j</math> as the next term. We need that, for some <math>k</math>, <math>s_k=k*j\le k^2</math> |
Revision as of 21:24, 28 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.
Contents
[hide]Solution
Solution 1
Create an integer sequence such that for
,
. Consider what happens when
. For
, we have
.
is a permissible value of
since
: if we substitute
for
, we get
.
is the unique value for
. We can repeat this argument for
. As we substituted the
s for the
s, the
s 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.
Solution 2
Define . If we have that
where
is an integer such that
, then we can take
, and we are done since
.
We always know that is a multiple of
by definition of the sequence. So we know an integer ,
, exists. But we also need the inequality (
) for
to be able to add
as the next term. We need that, for some
,
However, we also know that .
So we note that for sufficiently large , we have that
, hence
. Then we are done, since we can take that suitable
and keep adding it.
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 |