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"

(what I wrote (am I right?))
m (wik, remove ugly summation - fraction notation)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Let <math>n</math> be a positive integer.  Define a sequence by setting <math>a_1 = n</math> and, for each <math>k>1</math>, letting <math>a_k</math> be the unique integer in the range <math>0 \le a_k \le k-1</math> for which <math>a_1 + a_2 + \cdots + a_k</math> is divisible by <math>k</math>.  For instance, when <math>n=9</math> the obtained sequence is <math>9, 1, 2, 0, 3, 3, 3, \ldots</math>.  Prove that for any <math>n</math> the sequence <math>a_1, a_2, a_3, \ldots</math> eventually becomes constant.
+
Let <math>n</math> be a [[positive]] [[integer]].  Define a [[sequence]] by setting <math>a_1 = n</math> and, for each <math>k>1</math>, letting <math>a_k</math> be the unique integer in the range <math>0 \le a_k \le k-1</math> for which <math>\displaystyle a_1 + a_2 + \cdots + a_k</math> is [[divisible]] by <math>k</math>.  For instance, when <math>n=9</math> the obtained sequence is <math>\displaystyle 9, 1, 2, 0, 3, 3, 3, \ldots</math>.  Prove that for any <math>n</math> the sequence <math>\displaystyle a_1, a_2, a_3, \ldots</math> eventually becomes [[constant]].
 +
 
  
 
== Solution ==
 
== Solution ==
−
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 = \frac{\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} = \frac{\displaystyle \sum_{i=1}^{k+1}}{k+1} = \frac{\displaystyle \sum_{i=1}^{k} + a_{k+1}}{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> \frac{\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.
  
  
 
{{USAMO newbox|year=2007|before=First question|num-a=2}}
 
{{USAMO newbox|year=2007|before=First question|num-a=2}}
 +
 +
[[Category:Olympiad Number Theory Problems]]

Revision as of 18:17, 25 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

Suppose we create a parallel integer sequence $\displaystyle b_1, b_2, \ldots$ such that for every $\displaystyle k \ge 1$, we have that $b_k = \displaystyle \sum_{i=1}^{k} / k$. Consider what happens when $b_k \le k$. For $\displaystyle k + 1$, we have that $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}$. $\displaystyle b_k$ is a permissible value of $a_{k+1} \displaystyle$ since $b_k \le k \le (k+1)-1$: if we substitute $\displaystyle b_k$ for $a_{k+1} \displaystyle$, we get that $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 also become constant.

Now we must show that $\displaystyle b_k$ eventually $\le k$. Suppose that $\displaystyle b_k$ always $\displaystyle > k$. By definition, $\displaystyle \sum_{i=1}^{k} / 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.


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=14715"