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"

(→‎Solution 2: b_k constant -> a_k constant)
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>\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]].
+
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]].
  
 
__TOC__
 
__TOC__
Line 7: Line 7:
 
== Solution ==
 
== Solution ==
 
=== Solution 1 ===  
 
=== Solution 1 ===  
−
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.
+
Define <math>s_k =\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>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>b_k</math> is a permissible value of <math> a_{k+1}</math> since <math>b_k \le k = (k+1)-1</math>: if we [[substitute]] <math>b_k</math> for <math> a_{k+1}</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}</math>. So <math>b_k = b_{k+1} = b_{k+2} = \cdots</math>, from which if follows that the <math>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>\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  
+
Now we must show that eventually <math>b_k \le k</math>. Suppose that <math>b_k > k</math> for all <math>k</math>. By definition, <math>\frac {s_k}{k} = b_k > k</math>, so <math>s_k > k^2</math>. Also, for <math>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>
+
<div style="text-align:center;"><math>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>
 
<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.
+
But <math>n</math> is constant while <math>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>a_i</math>s will become constant.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
Line 21: Line 21:
 
<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>
 
<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>
  
−
<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.  
+
<math>\frac{k}{k+1} < 1</math>, and by definition, <math>\frac{a_{k+1}}{k+1} < 1</math>. Thus, <math>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>b_k</math>s form a [[non-increasing]] sequence of positive integers, they must eventually become constant.  
  
−
Therefore, <math>\displaystyle b_k = b_{k+1}</math> for some sufficiently large value of <math>\displaystyle k</math>. Then <math>\displaystyle a_{k+1} = s_{k+1} - s_k = b_k(k + 1) - b_k(k) = b_k</math>, so eventually the sequence <math>\displaystyle a_k</math> becomes constant.
+
Therefore, <math>b_k = b_{k+1}</math> for some sufficiently large value of <math>k</math>. Then <math>a_{k+1} = s_{k+1} - s_k = b_k(k + 1) - b_k(k) = b_k</math>, so eventually the sequence <math>a_k</math> becomes constant.
 +
 
 +
=== Solution 3 ===
 +
Let <math>a_1=n</math>.  Since <math>a_k\le k-1</math>, we have that <math>a_1+a_2+a_3+\hdots+a_n\le n+1+2+\hdots+n-1</math>.  <math>a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}</math>.  Since <math>a_1+a_2+\hdots+a_n=nk</math>, for some integer <math>k</math>, we can keep adding <math>k</math> to satisfy the conditions, provided that <math>k\le n</math> because <math>a_n+1\le n</math>.
 +
 
 +
Thus, <math>k\le \frac{n+1}{2}\le n</math>, and the sequence must eventually become constant.  
  
 
== See also ==
 
== See also ==

Revision as of 20:57, 22 March 2008

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 $a_1 + a_2 + \cdots + a_k$ is divisible by $k$. For instance, when $n=9$ the obtained sequence is $9, 1, 2, 0, 3, 3, 3, \ldots$. Prove that for any $n$ the sequence $a_1, a_2, a_3, \ldots$ eventually becomes constant.

Solution

Solution 1

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

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

$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 $n$ is constant while $k$ is increasing, so eventually we will have a contradiction and $b_k \le k$. Therefore, the sequence of $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, $b_{k+1} < b_k + 1$. Also, both $b_k,\ b_{k+1}$ are integers, so $b_{k+1} \le b_k$. As the $b_k$s form a non-increasing sequence of positive integers, they must eventually become constant.

Therefore, $b_k = b_{k+1}$ for some sufficiently large value of $k$. Then $a_{k+1} = s_{k+1} - s_k = b_k(k + 1) - b_k(k) = b_k$, so eventually the sequence $a_k$ becomes constant.

Solution 3

Let $a_1=n$. Since $a_k\le k-1$, we have that $a_1+a_2+a_3+\hdots+a_n\le n+1+2+\hdots+n-1$. $a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}$. Since $a_1+a_2+\hdots+a_n=nk$, for some integer $k$, we can keep adding $k$ to satisfy the conditions, provided that $k\le n$ because $a_n+1\le n$.

Thus, $k\le \frac{n+1}{2}\le n$, and the sequence must eventually become constant.

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