Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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*n=j*(n+1)</math>.  
+
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 $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

Create an integer sequence $\displaystyle b_1, b_2, \ldots$ such that for $\displaystyle k \ge 1$, $b_k = \displaystyle \left(\sum_{i=1}^{k}\right) / k$. Consider what happens when $b_k \le k$. For $\displaystyle k + 1$, we have $b_{k+1} = \displaystyle \left(\sum_{i=1}^{k+1}\right) / (k+1) = \left(\displaystyle \sum_{i=1}^{k} + a_{k+1}\right) / (k+1) = \frac{b_k \times k + a_{k+1}}{k+1}$. $\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$. $\displaystyle b_k$ is the unique value for $a_{k+1} \displaystyle$. We can repeat this argument for $\displaystyle b_k = b_{k+1} = b_{k+2} \ldots$. As we substituted the $\displaystyle b_k$s for the $\displaystyle a_k$s, the $\displaystyle a_k$s become constant.

Now we must show that $\displaystyle b_k$ eventually $\le k$. Suppose that $\displaystyle b_k$ always $\displaystyle > k$. By definition, $\displaystyle \left(\sum_{i=1}^{k}\right) / k = b_k > k$, so $\displaystyle \sum_{i=1}^{k} a_i > k^2$. We also have that each $a_i \le i-1$ so that $k^2 < \displaystyle \sum_{i=1}^{k} \le n + 1 + 2 + \ldots + (k-1) = n + \frac{k^2 - k}2$. So $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

Define $\displaystyle s_k=a_1+a_2+...+a_k$. If we have that $\displaystyle s_k=j*k$ where $j$ is an integer such that $0\le j\le k$, then we can take $\displaystyle a_{k+1}=j$, and we are done since $\displaystyle s_{k+1}=a_{k+1}+s_k=j+j*k=j*(k+1)$.

We always know that $s_k$ is a multiple of $k$ by definition of the sequence. So we know an integer ,$j$, exists. But we also need the inequality ($0\le j\le k$) for $j$ to be able to add $j$ as the next term. We need that, for some $k$, $s_k=k*j\le k^2$

However, we also know that $s_k=a_1+a_2+...+a_k\le n+1+2+...+k-1=n+\frac{(k-1)(k)}{2}$.

So we note that for sufficiently large $k$, we have that $n+\frac{(k-1)(k)}{2}\le k^2\iff n\le \frac{k^2+k}{2}$, hence $s_k\le k^2$. Then we are done, since we can take that suitable $j$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_USAMO_Problems/Problem_1&oldid=14777"