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)
Line 24: Line 24:
  
 
Because <math>k\le \frac{n+1}{2}\le n</math>, the sequence must eventually become constant.
 
Because <math>k\le \frac{n+1}{2}\le n</math>, the sequence must eventually become constant.
 +
 +
===Solution 3===
 +
Define <math>S_k = a_1 + a_2 + ... + a_k</math>, and <math>b_k = \frac{S_k}{k}</math>. By the problem hypothesis, <math>b_k</math> is an integer valued sequence.
 +
 +
''Lemma:'' The exists a <math>k</math> such that <math>b_k < k</math>.
 +
Proof: Choose any <math>k</math> such that <math>k^2 + 3k - 2 > 2n</math>. Then:
 +
<cmath>\frac{k^2 + 3k - 2}{2} > n</cmath>
 +
<cmath>k^2 > \frac{k^2 - 3k + 2}{2} + n</cmath>
 +
<cmath>k^2 > (k-2) + (k-1) + ... + 1 + n</cmath>
 +
<cmath>k^2 > a_{k-1} + a_{k-2} + ... + a_2 + a_1</cmath>
 +
<cmath>k^2 > S_k</cmath>
 +
<cmath>k > \frac{S_k}{k}</cmath>
 +
<cmath>k > b_k,</cmath>
 +
as desired.
 +
 +
Let k be the smallest k such that <math>b_k < k</math>. Then <math>b_k = m < k</math>, and <math>S_k = km</math>. To make <math>b_{k+1}</math> an integer, <math>S_{k+1} = S_k + a_{k+1}</math> must be divisible by <math>k+1</math>. Thus, because <math>km + m</math> is divisible by <math>k+1</math>, <math>a_{k+1} \equiv m (mod k+1)</math>, and, because <math>0 \le a_{k+1} < k</math>, <math>a_{k+1} = m</math>. Then <math>b_{k+1} = \frac{(k+1)m}{k+1} = m</math> as well. Repeating the same process using <math>k+1</math> instead of <math>k</math> gives <math>a_{k+2} = m</math>, and an easy induction can prove that for all <math>N > k+1</math>, <math>a_N = m</math>. Thus, <math>a_k</math> becomes a constant function for arbitrarily large values of k.
  
 
== See also ==
 
== See also ==

Revision as of 12:26, 7 June 2014

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

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 2

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$.

Thus, $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$.

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

Solution 3

Define $S_k = a_1 + a_2 + ... + a_k$, and $b_k = \frac{S_k}{k}$. By the problem hypothesis, $b_k$ is an integer valued sequence.

Lemma: The exists a $k$ such that $b_k < k$. Proof: Choose any $k$ such that $k^2 + 3k - 2 > 2n$. Then: \[\frac{k^2 + 3k - 2}{2} > n\] \[k^2 > \frac{k^2 - 3k + 2}{2} + n\] \[k^2 > (k-2) + (k-1) + ... + 1 + n\] \[k^2 > a_{k-1} + a_{k-2} + ... + a_2 + a_1\] \[k^2 > S_k\] \[k > \frac{S_k}{k}\] \[k > b_k,\] as desired.

Let k be the smallest k such that $b_k < k$. Then $b_k = m < k$, and $S_k = km$. To make $b_{k+1}$ an integer, $S_{k+1} = S_k + a_{k+1}$ must be divisible by $k+1$. Thus, because $km + m$ is divisible by $k+1$, $a_{k+1} \equiv m (mod k+1)$, and, because $0 \le a_{k+1} < k$, $a_{k+1} = m$. Then $b_{k+1} = \frac{(k+1)m}{k+1} = m$ as well. Repeating the same process using $k+1$ instead of $k$ gives $a_{k+2} = m$, and an easy induction can prove that for all $N > k+1$, $a_N = m$. Thus, $a_k$ becomes a constant function for arbitrarily large values of k.

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_USAMO_Problems/Problem_1&oldid=62216"