Difference between revisions of "2007 USAMO Problems/Problem 1"

Latest revision as of 21:11, 1 November 2025

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

Let $S_k =\sum_{i=1}^k a_i$ , where $S_k \equiv 0 \pmod{k}$ and $0 \leq a_k < k$ . Define $m_k = S_k / k$ , with $m_1 = n$ .

First, for $k > 1$ , since $S_{k-1} = (k-1) \cdot m_{k-1}$ and $S_k = S_{k-1} + a_k$ , we need $S_k \equiv 0 \pmod{k}$ . Set $a_k \equiv m_{k-1} \pmod{k}$ . Then,

$S_k \bmod k \equiv \bigl((k-1) \cdot m_{k-1} + (m_{k-1} \bmod k)\bigr) \pmod{k}$ . Since $(k-1) \cdot m_{k-1} \equiv -m_{k-1} \pmod{k}$ , and $-m_{k-1} + (m_{k-1} \bmod k) \equiv 0 \pmod{k}$ , this holds.

Next, compute $m_k = S_k / k = \bigl((k-1) \cdot m_{k-1} + a_k\bigr) / k$ . If $m_{k-1} \geq k$ , let $m_{k-1} = qk + r$ with $0 \leq r < k$ , so $a_k = r$ , and $m_k = \frac{(k-1) \cdot m_{k-1} + r}{k} < m_{k-1}$ , so $m_k < m_{k-1}$ . Moreover, so long as $m_{k-1} \geq k$ then $m_{i}$ is strictly decreasing while $k$ is strictly increasing, until $m_{i} \leq k$ , in which case the sequence terminates as $m_{k-1} = m_{k}$

Solution 6(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$ .

Solution 7(A simpler version of Solution 1)

$a_1=1 \cdot x_1$ , $a_1+a_2=2 \cdot x_2$ , $a_1+a_2+a_3=3 \cdot x_3, ...$

Claim.

$x_1 \geq x_2 \geq x_3 \geq ...$

Proof.

$a_2=2 \cdot x_2 - 1 \cdot x_1$ , $a_3=3 \cdot x_3 - 2 \cdot x_2$ , $a_4=4 \cdot x_4 - 3 \cdot x_3, ...$

F.T.S.O.C suppose $x_{n-1} < x_n$ for some $n>1$ .

$a_n=n \cdot x_n - (n-1) \cdot x_{n-1}$ .

Note that $n \cdot x_n > (n-1) \cdot (x_{n-1}+1)$ as $x_n \geq x_{n-1}+1$ .

This directly implies $n \cdot x_n - (n-1) \cdot x_{n-1} = a_n > n-1$ , a contradiction to the given bound on $a_n$ by the problem.

Hence, it is impossibe to have $x_{n-1} < x_n$ for any $n>1$ , implying $x_{n-1} \geq x_n$ for every $n>1$ , that is, $x_1 \geq x_2 \geq x_3 \geq ...$ , proving our claim.

As the sequence $x_i$ only consists of positive integers, it can't be ever decreasing, so that it must become eventually constant,

that is, $x_k=x_{k+1}=...$ from some $k \geq 1$ .

Then,

$a_1+...+a_k=k \cdot x_k$ , $a_1+...+a_k+a_{k+1}=(k+1) \cdot x_{k+1}=(k+1) \cdot x_k, ...$

giving us $x_k=a_{k+1}=a_{k+2}=...$ (by substracting the 1st equation from the 2nd, the 2nd from the 3rd, and so on), completing the proof to the solution.

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

@@ Line 1: / Line 1: @@
 == 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]].
+(''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]].
 == Solutions ==
 === Solution 1 ===
-Let <math>S_k = a_1 + a_2 + ... + a_k</math> and <math>b_k = \frac{S_k}{k}</math>. Thus, because <math>S_{k+1} = S_k + a_{k+1}</math>,
+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.
-<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>
+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 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>.
+''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.
-<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.
+'''End Lemma'''
-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.
+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.
+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===
+Let <math>S_k =\sum_{i=1}^k a_i</math>, where <math>S_k \equiv 0 \pmod{k}</math> and <math>0 \leq a_k < k</math>. Define <math>m_k = S_k / k</math>, with <math>m_1 = n</math>.
+First, for <math>k > 1</math>, since <math>S_{k-1} = (k-1) \cdot m_{k-1}</math> and <math>S_k = S_{k-1} + a_k</math>, we need <math>S_k \equiv 0 \pmod{k}</math>. Set <math>a_k \equiv m_{k-1} \pmod{k}</math>. Then,
+<math>S_k \bmod k \equiv \bigl((k-1) \cdot m_{k-1} + (m_{k-1} \bmod k)\bigr) \pmod{k}</math>.
+Since <math>(k-1) \cdot m_{k-1} \equiv -m_{k-1} \pmod{k}</math>, and <math>-m_{k-1} + (m_{k-1} \bmod k) \equiv 0 \pmod{k}</math>, this holds.
+Next, compute <math>m_k = S_k / k = \bigl((k-1) \cdot m_{k-1} + a_k\bigr) / k</math>.
+If <math>m_{k-1} \geq k</math>, let <math>m_{k-1} = qk + r</math> with <math>0 \leq r < k</math>, so <math>a_k = r</math>, and
+<math>m_k = \frac{(k-1) \cdot m_{k-1} + r}{k} < m_{k-1}</math>,
+so <math>m_k < m_{k-1}</math>. Moreover, so long as <math>m_{k-1} \geq k</math> then <math>m_{i}</math> is strictly decreasing while <math>k</math> is strictly increasing, until <math>m_{i} \leq k</math>, in which case the sequence terminates as <math>m_{k-1} = m_{k}</math>
+===Solution 6(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>.
+==Solution 7(A simpler version of Solution 1)==
+<math>a_1=1 \cdot x_1</math>, <math>a_1+a_2=2 \cdot x_2</math>, <math>a_1+a_2+a_3=3 \cdot x_3, ...</math>
+Claim.
+<math>x_1 \geq x_2 \geq x_3 \geq ...</math>
+Proof.
+<math>a_2=2 \cdot x_2 - 1 \cdot x_1</math>, <math>a_3=3 \cdot x_3 - 2 \cdot x_2</math>, <math>a_4=4 \cdot x_4 - 3 \cdot x_3, ...</math>
+F.T.S.O.C suppose <math>x_{n-1} < x_n</math> for some <math>n>1</math>.
+<math>a_n=n \cdot x_n - (n-1) \cdot x_{n-1}</math>.
-=== Solution 2 ===
+Note that <math>n \cdot x_n > (n-1) \cdot (x_{n-1}+1)</math> as <math>x_n \geq x_{n-1}+1</math>.
-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>.
-Thus, <math>a_1+a_2+\hdots+a_n\le \frac{n(n+1)}{2}</math>.
+This directly implies <math>n \cdot x_n - (n-1) \cdot x_{n-1} = a_n > n-1</math>, a contradiction to the given bound on <math>a_n</math> by the problem.
-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>.
+Hence, it is impossibe to have <math>x_{n-1} < x_n</math> for any <math>n>1</math>, implying  <math>x_{n-1} \geq x_n</math> for every <math>n>1</math>, that is, <math>x_1 \geq x_2 \geq x_3 \geq ...</math>, proving our claim.
-Because <math>k\le \frac{n+1}{2}\le n</math>, the sequence must eventually become constant.
-===Solution 3===
+As the sequence <math>x_i</math> only consists of positive integers, it can't be ever decreasing, so that it must become eventually constant,
-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>.
+that is, <math>x_k=x_{k+1}=...</math> from some <math>k \geq 1</math>.
-Proof: Choose any <math>k</math> such that <math>k^2 + 3k - 2 > 2n</math>. Then:
+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.
+<math>a_1+...+a_k=k \cdot x_k</math>, <math>a_1+...+a_k+a_{k+1}=(k+1) \cdot x_{k+1}=(k+1) \cdot x_k, ...</math>
-''Note: This solution is a formalization of the second solution. Also, the lemma could have been simplified if I chose k = n, which is exactly the second solution's thought process.''
+giving us <math>x_k=a_{k+1}=a_{k+2}=...</math> (by substracting the 1st equation from the 2nd, the 2nd from the 3rd, and so on), completing the proof to the solution.
 {{alternate solutions}}
 == See also ==
+* <url>viewtopic.php?t=145842 Discussion on AoPS/MathLinks</url>
 {{USAMO newbox|year=2007|before=First Question|num-a=2}}

2007 USAMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search