Difference between revisions of "2007 USAMO Problems/Problem 1"

Revision as of 21:56, 30 April 2007

Problem

Let $n$ be a positive integer. Define a sequence by setting $a_1 = n$ and, for each $k>1$ , letting $a_k$ be the unique integer in the range $0 \le a_k \le k-1$ for which $\displaystyle a_1 + a_2 + \cdots + a_k$ is divisible by $k$ . For instance, when $n=9$ the obtained sequence is $\displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots$ . Prove that for any $n$ the sequence $\displaystyle a_1, a_2, a_3, \ldots$ eventually becomes constant.

Solution

Solution 1

Define $\displaystyle s_k = \displaystyle \sum_{i=1}^{k} a_i$ , and $b_k = \frac{s_k}{k}$ . If $b_k \le k$ , then for $\displaystyle k + 1$ , $b_{k+1} = \frac{s_{k+1}}{k + 1} = \frac{s_k + a_{k+1}}{k+1} = \frac{b_k \cdot k + a_{k+1}}{k+1}$ . Note that $\displaystyle b_k$ is a permissible value of $a_{k+1} \displaystyle$ since $b_k \le k = (k+1)-1$ : if we substitute $\displaystyle b_k$ for $a_{k+1} \displaystyle$ , we get $b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k$ , the unique value for $a_{k+1} \displaystyle$ . So $\displaystyle b_k = b_{k+1} = b_{k+2} = \cdots$ , from which if follows that the $\displaystyle a_k$ s become constant.

Now we must show that eventually $\displaystyle b_k \le k$ . Suppose that $\displaystyle b_k > k$ for all $\displaystyle k$ . By definition, $\displaystyle \frac {s_k}{k} = b_k > k$ , so $\displaystyle s_k > k^2$ . Also, for $\displaystyle i>1$ , each $a_i \le i-1$ so

$\displaystyle k^2 < s_k \le n + 1 + 2 + \cdots + (k-1) = n + \frac{k^2 - k}2$
$k^2 < n +\frac{k^2 - k}2 \Longrightarrow \frac{k^2 + k}2 < n$

But $\displaystyle n$ is constant while $\displaystyle k$ is increasing, so eventually we will have a contradiction and $b_k \le k$ . Therefore, the sequence of $\displaystyle a_i$ 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}$

$\frac{k}{k+1} < 1$ , and by definition, $\frac{a_{k+1}}{k+1} < 1$ . Thus, $\displaystyle b_{k+1} < b_k + 1$ . Also, both $b_k,\ b_{k+1}$ are integers, so $b_{k+1} \le b_k$ . As the $\displaystyle b_k$ s form a non-increasing sequence of positive integers, they must eventually become constant. Continue as above.

@@ Line 7: / Line 7: @@
 == Solution ==
 === Solution 1 ===
-Create an integer sequence <math>\displaystyle b_1, b_2, \ldots</math> such that for <math>\displaystyle k \ge 1</math>, <math>b_k = \displaystyle \left(\sum_{i=1}^{k} a_i\right) / k</math>. Consider what happens when <math>b_k \le k</math>. For <math>\displaystyle k + 1</math>, we have <math>b_{k+1} = \displaystyle \left(\sum_{i=1}^{k+1}a_i \right) / (k+1) = \left(\displaystyle \sum_{i=1}^{k} a_i + a_{k+1}\right) / (k+1) = \frac{b_k \times k + a_{k+1}}{k+1}</math>. Note that <math>\displaystyle b_k</math> is a permissible value of <math> a_{k+1} \displaystyle </math> since <math>b_k \le k = (k+1)-1</math>: if we [[substitute]] <math>\displaystyle b_k</math> for <math> a_{k+1} \displaystyle </math>, we get <math>b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k</math>.  Therefore <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} = \cdots</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 become constant.
+Define <math>\displaystyle s_k = \displaystyle \sum_{i=1}^{k} a_i</math>, and <math>b_k = \frac{s_k}{k}</math>. If <math>b_k \le k</math>, then for <math>\displaystyle k + 1</math>, <math>b_{k+1} = \frac{s_{k+1}}{k + 1} = \frac{s_k + a_{k+1}}{k+1} = \frac{b_k \cdot k + a_{k+1}}{k+1}</math>. Note that <math>\displaystyle b_k</math> is a permissible value of <math> a_{k+1} \displaystyle </math> since <math>b_k \le k = (k+1)-1</math>: if we [[substitute]] <math>\displaystyle b_k</math> for <math> a_{k+1} \displaystyle </math>, we get <math>b_{k+1} = \frac{b_k (k+1)}{k+1} = b_k</math>, the unique value for <math> a_{k+1} \displaystyle </math>. So <math>\displaystyle b_k = b_{k+1} = b_{k+2} = \cdots</math>, from which if follows that the <math>\displaystyle a_k</math>s become constant.
-Now we must show that eventually <math>\displaystyle b_k \le k</math>. Suppose that <math>\displaystyle b_k > k</math> for all <math>k</math>. By definition, <math> \displaystyle \left(\sum_{i=1}^{k} a_i\right) / k = b_k > k</math>, so <math>\displaystyle \sum_{i=1}^{k} a_i > k^2</math>. We also have that for <math>i>1</math>, each <math>a_i \le i-1</math> so that <math>\displaystyle k^2 <  \sum_{i=1}^{k} a_i \le n + 1 + 2 + \cdots + (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 eventually <math>\displaystyle b_k \le k</math>. Suppose that <math>\displaystyle b_k > k</math> for all <math>\displaystyle k</math>. By definition, <math> \displaystyle \frac {s_k}{k} = b_k > k</math>, so <math>\displaystyle s_k > k^2</math>. Also, for <math>\displaystyle i>1</math>, each <math>a_i \le i-1</math> so
+<div style="text-align:center;"><math>\displaystyle k^2 <  s_k \le n + 1 + 2 + \cdots + (k-1) = n + \frac{k^2 - k}2</math> <br>
+<math>k^2 < n +\frac{k^2 - k}2  \Longrightarrow \frac{k^2 + k}2 < n</math></div>
+But <math>\displaystyle n</math> is constant while <math>\displaystyle k</math> is increasing, so eventually we will have a [[proof by contradiction|contradiction]] and <math>b_k \le k</math>. Therefore, the sequence of <math>\displaystyle a_i</math>s will become constant.
 === Solution 2 ===
+By the above, we have that
-Define <math>\displaystyle s_k=a_1+a_2+\cdots+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>.
+<div style="text-align:center;"><math>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}</math></div>
-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>
-However, we also know that <math>s_k=a_1+a_2+\cdots+a_k\le n+1+2+\cdots+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.
+<math>\frac{k}{k+1} < 1</math>, and by definition, <math>\frac{a_{k+1}}{k+1} < 1</math>. Thus, <math>\displaystyle b_{k+1} < b_k + 1</math>. Also, both <math>b_k,\ b_{k+1}</math> are integers, so <math>b_{k+1} \le b_k</math>. As the <math>\displaystyle b_k</math>s form a [[non-increasing]] sequence of positive integers, they must eventually become constant. Continue as above.
 == 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

Page

Toolbox

Search