Difference between revisions of "2007 USAMO Problems/Problem 1"
(→Solution) |
Jschroeder (talk | contribs) (→Problem) |
||
(30 intermediate revisions by 13 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]]. | ||
− | + | == Solutions == | |
+ | === 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. | ||
− | + | 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 | + | === 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. | ||
− | + | '''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. | ||
+ | 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>. | ||
− | {{USAMO newbox|year=2007|before=First | + | |
+ | {{alternate solutions}} | ||
+ | |||
+ | == See also == | ||
+ | * <url>viewtopic.php?t=145842 Discussion on AoPS/MathLinks</url> | ||
+ | |||
+ | {{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 20:06, 23 August 2023
Contents
Problem
(Sam Vandervelde) Let be a positive integer. Define a sequence by setting
and, for each
, letting
be the unique integer in the range
for which
is divisible by
. For instance, when
the obtained sequence is
. Prove that for any
the sequence
eventually becomes constant.
Solutions
Solution 1
Let and
. Thus, because
,
, and by definition,
. Thus,
. Also, both
and
are integers, so
. As the
's form a non-increasing sequence of positive integers, they must eventually become constant.
Therefore, for some sufficiently large value of
. Then
, so eventually the sequence
becomes constant.
Solution 2
Let . Since
, we have that
Since
for some integer
, we can keep adding
to satisfy the conditions, provided that
. This is true since
, so the sequence must eventually become constant.
Solution 3
Define , and
. By the problem hypothesis,
is an integer valued sequence.
Lemma: There exists a such that
.
Proof: Choose any such that
. Then
as desired.
End Lemma
Let be the smallest
such that
. Then
, and
. To make
an integer,
must be divisible by
. Thus, because
is divisible by
,
, and, because
,
. Then
as well. Repeating the same process using
instead of
gives
, and an easy induction can prove that for all
,
. Thus,
becomes a constant function for arbitrarily large values of
.
Solution 4
For , let
We claim that for some
we have
. To this end, consider the sequence which computes the differences between
and
, i.e., whose
-th term is
. Note that the first term of this sequence is positive (it is equal to
) and that its terms are strictly decreasing since
Further, a negative term cannot immediately follow a positive term. Suppose otherwise, namely that
and
. Since
and
are divisible by
and
, respectively, we can tighten the above inequalities to
and
. But this would imply that
, a contradiction. We conclude that the sequence of differences must eventually include a term equal to zero.
Let be a positive integer such that
. We claim that
This follows from the fact that the sequence
is uniquely determined and choosing
, for
, satisfies the range condition
and yields
Solution 5(like solution 2)
First, we may make an observation and say that for ,
must occur for the whole sum to be divisible by
. Thus, the following is apparent:
Then, we may make another observation that when
, the sum also has to be divisible by n. We may then explore when n=k:
and
Then,
Also,
for
. This is because:
This must be true since
will be divisible by
and
, we may then generalize this to all
Thus, we may say that the sequence
must converge to some integer value
when
.
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.