Difference between revisions of "2007 USAMO Problems/Problem 1"
m (wik, remove ugly summation - fraction notation) |
(→Solution) |
||
Line 4: | Line 4: | ||
− | == Solution == | + | == Solution 1 == |
Suppose we create a [[parallel]] integer sequence <math>\displaystyle b_1, b_2, \ldots</math> such that for every <math>\displaystyle k \ge 1</math>, we have that <math>b_k = \displaystyle \sum_{i=1}^{k} / k</math>. Consider what happens when <math>b_k \le k</math>. For <math>\displaystyle k + 1</math>, we have that <math>b_{k+1} = \displaystyle \sum_{i=1}^{k+1} / (k+1) = \left(\displaystyle \sum_{i=1}^{k} + a_{k+1}\right) / (k+1) = \frac{b_k \times k + a_{k+1}}{k+1}</math>. <math>\displaystyle b_k</math> is a permissible value of <math> a_{k+1} \displaystyle </math> since <math>b_k \le k \le (k+1)-1</math>: if we [[substitute]] <math>\displaystyle b_k</math> for <math> a_{k+1} \displaystyle </math>, we get that <math>b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k</math>. <math>\displaystyle b_k</math> is the unique value for <math> a_{k+1} \displaystyle </math>. We can repeat this argument for <math>\displaystyle b_k = b_{k+1} = b_{k+2} \ldots</math>. As we substituted the <math>\displaystyle b_k</math>s for the <math>\displaystyle a_k</math>s, the <math>\displaystyle a_k</math>s also become constant. | Suppose we create a [[parallel]] integer sequence <math>\displaystyle b_1, b_2, \ldots</math> such that for every <math>\displaystyle k \ge 1</math>, we have that <math>b_k = \displaystyle \sum_{i=1}^{k} / k</math>. Consider what happens when <math>b_k \le k</math>. For <math>\displaystyle k + 1</math>, we have that <math>b_{k+1} = \displaystyle \sum_{i=1}^{k+1} / (k+1) = \left(\displaystyle \sum_{i=1}^{k} + a_{k+1}\right) / (k+1) = \frac{b_k \times k + a_{k+1}}{k+1}</math>. <math>\displaystyle b_k</math> is a permissible value of <math> a_{k+1} \displaystyle </math> since <math>b_k \le k \le (k+1)-1</math>: if we [[substitute]] <math>\displaystyle b_k</math> for <math> a_{k+1} \displaystyle </math>, we get that <math>b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k</math>. <math>\displaystyle b_k</math> is the unique value for <math> a_{k+1} \displaystyle </math>. We can repeat this argument for <math>\displaystyle b_k = b_{k+1} = b_{k+2} \ldots</math>. As we substituted the <math>\displaystyle b_k</math>s for the <math>\displaystyle a_k</math>s, the <math>\displaystyle a_k</math>s also become constant. | ||
Now we must show that <math>\displaystyle b_k</math> eventually <math>\le k</math>. Suppose that <math>\displaystyle b_k</math> always <math>\displaystyle > k</math>. By definition, <math> \displaystyle \sum_{i=1}^{k} / k = b_k > k</math>, so <math>\displaystyle \sum_{i=1}^{k} a_i > k^2</math>. We also have that each <math>a_i \le i-1</math> so that <math>k^2 < \displaystyle \sum_{i=1}^{k} \le n + 1 + 2 + \ldots + (k-1) = n + \frac{k^2 - k}2 </math>. So <math>k^2 < n +\frac{k^2 - k}2 \Longrightarrow \frac{k^2 + k}2 < n</math>. But <math>\displaystyle n</math> is constant while <math>\displaystyle k</math> is increasing, so eventually we will have a contradiction and <math>b_k \le k</math>. Therefore, the sequence of <math>\displaystyle a_i</math>s will become constant. | Now we must show that <math>\displaystyle b_k</math> eventually <math>\le k</math>. Suppose that <math>\displaystyle b_k</math> always <math>\displaystyle > k</math>. By definition, <math> \displaystyle \sum_{i=1}^{k} / k = b_k > k</math>, so <math>\displaystyle \sum_{i=1}^{k} a_i > k^2</math>. We also have that each <math>a_i \le i-1</math> so that <math>k^2 < \displaystyle \sum_{i=1}^{k} \le n + 1 + 2 + \ldots + (k-1) = n + \frac{k^2 - k}2 </math>. So <math>k^2 < n +\frac{k^2 - k}2 \Longrightarrow \frac{k^2 + k}2 < n</math>. But <math>\displaystyle n</math> is constant while <math>\displaystyle k</math> is increasing, so eventually we will have a contradiction and <math>b_k \le k</math>. Therefore, the sequence of <math>\displaystyle a_i</math>s will become constant. | ||
+ | |||
+ | == Solution 2 == | ||
+ | |||
+ | Define <math>s_k=a_1+a_2+...+a_k</math>. If we have that <math>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>a_{k+1}=j</math>, and we are done since <math>s_{k+1}=a_{k+1}+s_k=j+j*n=j*(n+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 that inequality 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> | ||
+ | |||
+ | However, we also know that <math>s_k=a_1+a_2+...+a_k\le n+1+2+...+k-1=n+\frac{(k-1)(k)}{2}</math>. | ||
+ | |||
+ | So we note that for sufficiently large <math>k</math>, we have that <math>n+\frac{(k-1)(k)}{2}\le k^2\iff n\le \frac{k^2+k}{2}</math>, hence <math>s_k\le k^2</math>. Then we are done, since we can take that suitable <math>j</math> and keep adding it. | ||
+ | |||
+ | Solution by AoPS user Altheman | ||
+ | |||
Revision as of 00:19, 26 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.
Solution 1
Suppose we create a parallel integer sequence such that for every
, we have that
. Consider what happens when
. For
, we have that
.
is a permissible value of
since
: if we substitute
for
, we get that
.
is the unique value for
. We can repeat this argument for
. As we substituted the
s for the
s, the
s also 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 that 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.
Solution by AoPS user Altheman
2007 USAMO (Problems • Resources) | ||
Preceded by First question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |