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)
(→‎Problem)
 
(26 intermediate revisions by 11 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
(''Sam Vandervelde'') 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]].
+
== Solutions ==
  
−
__TOC__
+
=== Solution 1 ===
 +
Let <math>S_k = a_1 + a_2 + \cdots + a_k</math> and <math>b_k = \frac{S_k}{k}</math>. Thus, because <math>S_{k+1} = S_k + a_{k+1}</math>,
 +
<cmath>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}</cmath>
 +
<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</math> and <math>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.
  
−
== Solution ==
+
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 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}\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}\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}</math>. <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>. <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 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 \left(\sum_{i=1}^{k}\right) / 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.
+
=== Solution 2 ===
 +
Let <math>a_1 = n</math>. Since <math>a_k\leq k - 1</math>, we have that
 +
<cmath>a_1 + a_2 + \cdots + a_n\leq n + 1 + 2 + \cdots + n - 1 = \frac{n(n + 1)}{2}.</cmath>
 +
Since <math>a_1 + a_2 + \cdots + 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\leq n</math>. This is true since <math>k\leq\frac{n + 1}{2}\leq n</math>, so the sequence must eventually become constant.
 +
 
 +
=== Solution 3 ===
 +
Define <math>S_k = a_1 + a_2 + \cdots + 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:''' There exists a <math>k</math> such that <math>b_k < k</math>.
  
−
=== Solution 2 ===
+
''Proof:'' Choose any <math>k</math> such that <math>k^2 + 3k - 2 > 2n</math>. Then
 +
<cmath>\begin{align*}
 +
\frac{k^2 + 3k - 2}{2} &> n \\
 +
k^2 &> \frac{k^2 - 3k + 2}{2} + n \\
 +
k^2 &> (k-2) + (k-1) + \cdots + 1 + n \\
 +
k^2 &> a_{k-1} + a_{k-2} + \cdots + a_2 + a_1 \\
 +
k^2 &> S_k \\
 +
k &> \frac{S_k}{k} \\
 +
k &> b_k,
 +
\end{align*}</cmath>
 +
as desired.
 +
 
 +
'''End Lemma'''
 +
 
 +
Let <math>k</math> be the smallest <math>k</math> 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 \pmod{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 <math>k</math>.
 +
 
 +
=== Solution 4 ===
 +
For <math>k\geq 1</math>, let
 +
<cmath>s_k = a_1 + a_2 + \cdots + a_k.</cmath>
 +
We claim that for some <math>m</math> we have <math>s_m = m(m - 1)</math>. To this end, consider the sequence which computes the differences between <math>s_k</math> and <math>k(k - 1)</math>, i.e., whose <math>k</math>-th term is <math>s_k - k(k - 1)</math>. Note that the first term of this sequence is positive (it is equal to <math>n</math>) and that its terms are strictly decreasing since
 +
<cmath>(s_k - k(k - 1)) - (s_{k+1} - (k + 1)k) = 2k - a_{k+1}\geq 2k - k = k\geq 1.</cmath>
 +
Further, a negative term cannot immediately follow a positive term. Suppose otherwise, namely that <math>s_k > k(k - 1)</math> and <math>s_{k+1} < (k + 1)k</math>. Since <math>s_k</math> and <math>s_{k+1}</math> are divisible by <math>k</math> and <math>k + 1</math>, respectively, we can tighten the above inequalities to <math>s_k\geq k^2</math> and <math>s_{k+1}\leq (k + 1)(k - 1) = k^2 - 1</math>. But this would imply that <math>s_k > s_{k+1}</math>, a contradiction. We conclude that the sequence of differences must eventually include a term equal to zero.
  
−
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>.  
+
Let <math>m</math> be a positive integer such that <math>s_m = m(m - 1)</math>. We claim that
 +
<cmath>m - 1 = a_{m+1} = a_{m+2} = a_{m+3} = a_{m+4} = \cdots.</cmath>
 +
This follows from the fact that the sequence <math>a_1, a_2, a_3, \ldots</math> is uniquely determined and choosing <math>a_{m+i} = m - 1</math>, for <math>i\geq 1</math>, satisfies the range condition
 +
<cmath>0\leq a_{m+i} = m - 1\leq m + i - 1,</cmath>
 +
and yields
 +
<cmath>s_{m+i} = s_m + i(m - 1) = m(m - 1) + i(m - 1) = (m + i)(m - 1).</cmath>
 +
==Solution 5(like solution 2)==
 +
First, we may make an observation and say that for <math>n \equiv p (mod k)</math>, <math>\sum_{m=2}^{k} a_m \equiv k-p (mod k)</math> must occur for the whole sum to be divisible by <math>k</math>. Thus, the following is apparent:
 +
<cmath>\sum_{m=2}^{k} a_m =(q+1)k - p , k < n</cmath>
 +
Then, we may make another observation that when <math>n=k</math>, the sum also has to be divisible by n. We may then explore when n=k:
 +
<cmath> \sum_{m=2}^{n} a_m \equiv 0 (mod n), \sum_{m=2}^{n} a_m = rn</cmath>
 +
and
 +
<cmath>a_n = \sum_{m=2}^{n} a_m - \sum_{m=2}^{n-1} a_m</cmath>
 +
Then,
 +
<cmath>a_n = rn - \sum_{m=2}^{n-1} a_m \le n-1</cmath>
 +
Also,
 +
<cmath>a_{n+s} = r, r \le n</cmath> for <math>s \ge 1</math>. This is because:
 +
<cmath>\sum_{m=2}^{n} a_m + r = rn + r = r(n+1)</cmath>
 +
This must be true since <math>r(n+1)</math> will be divisible by <math>n+1</math> and <math>k=n+1</math>, we may then generalize this to all <math>r(n+s), s \in \mathbb{Z}, s \ge 1</math>
 +
<cmath>rn + sr= r(n+s), \frac{r(n+s)}{r} = n + s = \frac{\sum_{m=2}^{n+s} a_m}{r}</cmath>
 +
Thus, we may say that the sequence <math>a_1,a_2,...a_k</math> must converge to some integer value <math>r \le n</math> when <math>k \ge n + 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>
 
−
 
−
However, we also know that <math>s_k=a_1+a_2+...+a_k\le n+1+2+...+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.
+
{{alternate solutions}}
  
 
== See also ==
 
== See also ==
 +
* <url>viewtopic.php?t=145842 Discussion on AoPS/MathLinks</url>
  
−
{{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]]
 
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 19:06, 23 August 2023

Problem

(Sam Vandervelde) 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.

Solutions

Solution 1

Let $S_k = a_1 + a_2 + \cdots + a_k$ and $b_k = \frac{S_k}{k}$. Thus, because $S_{k+1} = S_k + a_{k+1}$, \[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$ and $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\leq k - 1$, we have that \[a_1 + a_2 + \cdots + a_n\leq n + 1 + 2 + \cdots + n - 1 = \frac{n(n + 1)}{2}.\] Since $a_1 + a_2 + \cdots + a_n = nk$ for some integer $k$, we can keep adding $k$ to satisfy the conditions, provided that $k\leq n$. This is true since $k\leq\frac{n + 1}{2}\leq n$, so the sequence must eventually become constant.

Solution 3

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

Lemma: There exists a $k$ such that $b_k < k$.

Proof: Choose any $k$ such that $k^2 + 3k - 2 > 2n$. Then \begin{align*} \frac{k^2 + 3k - 2}{2} &> n \\ k^2 &> \frac{k^2 - 3k + 2}{2} + n \\ k^2 &> (k-2) + (k-1) + \cdots + 1 + n \\ k^2 &> a_{k-1} + a_{k-2} + \cdots + a_2 + a_1 \\ k^2 &> S_k \\ k &> \frac{S_k}{k} \\ k &> b_k, \end{align*} as desired.

End Lemma

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 \pmod{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$.

Solution 4

For $k\geq 1$, let \[s_k = a_1 + a_2 + \cdots + a_k.\] We claim that for some $m$ we have $s_m = m(m - 1)$. To this end, consider the sequence which computes the differences between $s_k$ and $k(k - 1)$, i.e., whose $k$-th term is $s_k - k(k - 1)$. Note that the first term of this sequence is positive (it is equal to $n$) and that its terms are strictly decreasing since \[(s_k - k(k - 1)) - (s_{k+1} - (k + 1)k) = 2k - a_{k+1}\geq 2k - k = k\geq 1.\] Further, a negative term cannot immediately follow a positive term. Suppose otherwise, namely that $s_k > k(k - 1)$ and $s_{k+1} < (k + 1)k$. Since $s_k$ and $s_{k+1}$ are divisible by $k$ and $k + 1$, respectively, we can tighten the above inequalities to $s_k\geq k^2$ and $s_{k+1}\leq (k + 1)(k - 1) = k^2 - 1$. But this would imply that $s_k > s_{k+1}$, a contradiction. We conclude that the sequence of differences must eventually include a term equal to zero.

Let $m$ be a positive integer such that $s_m = m(m - 1)$. We claim that \[m - 1 = a_{m+1} = a_{m+2} = a_{m+3} = a_{m+4} = \cdots.\] This follows from the fact that the sequence $a_1, a_2, a_3, \ldots$ is uniquely determined and choosing $a_{m+i} = m - 1$, for $i\geq 1$, satisfies the range condition \[0\leq a_{m+i} = m - 1\leq m + i - 1,\] and yields \[s_{m+i} = s_m + i(m - 1) = m(m - 1) + i(m - 1) = (m + i)(m - 1).\]

Solution 5(like solution 2)

First, we may make an observation and say that for $n \equiv p (mod k)$, $\sum_{m=2}^{k} a_m \equiv k-p (mod k)$ must occur for the whole sum to be divisible by $k$. Thus, the following is apparent: \[\sum_{m=2}^{k} a_m =(q+1)k - p , k < n\] Then, we may make another observation that when $n=k$, the sum also has to be divisible by n. We may then explore when n=k: \[\sum_{m=2}^{n} a_m \equiv 0 (mod n), \sum_{m=2}^{n} a_m = rn\] and \[a_n = \sum_{m=2}^{n} a_m - \sum_{m=2}^{n-1} a_m\] Then, \[a_n = rn - \sum_{m=2}^{n-1} a_m \le n-1\] Also, \[a_{n+s} = r, r \le n\] for $s \ge 1$. This is because: \[\sum_{m=2}^{n} a_m + r = rn + r = r(n+1)\] This must be true since $r(n+1)$ will be divisible by $n+1$ and $k=n+1$, we may then generalize this to all $r(n+s), s \in \mathbb{Z}, s \ge 1$ \[rn + sr= r(n+s), \frac{r(n+s)}{r} = n + s = \frac{\sum_{m=2}^{n+s} a_m}{r}\] Thus, we may say that the sequence $a_1,a_2,...a_k$ must converge to some integer value $r \le n$ when $k \ge n + 1$.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

  • <url>viewtopic.php?t=145842 Discussion on AoPS/MathLinks</url>
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=197358"