Difference between revisions of "2003 USAMO Problems/Problem 3"
m |
|||
Line 13: | Line 13: | ||
</math> | </math> | ||
</center> | </center> | ||
− | by setting <math> | + | by setting <math>t(a_i) </math> to be the number of terms in the sequence <math>A </math> that precede the term <math>a_i </math> and are different from <math>a_i </math>. Show that, starting from any sequence <math>A </math> as above, fewer than <math>n </math> applications of the transformation <math>t </math> lead to a sequence <math>B </math> such that <math>t(B) = B </math>. |
== Solution == | == Solution == | ||
− | Consider some sequence <math> C = c_0, \ldots, c_n </math> as the image of <math> | + | Consider some sequence <math> C = c_0, \ldots, c_n </math> as the image of <math>A </math> after <math>t </math> has been applied some finite number of times. |
− | '''Lemma 1.''' If <math> | + | '''Lemma 1.''' If <math>t(c_k) = c_k = j </math>, then <math> {} c_j = \cdots = c_{j+i} = \cdots = c_k = j </math> (<math> 0 \le i \le k-j</math>). |
− | ''Proof.'' Since the <math> | + | ''Proof.'' Since the <math>j </math> terms <math>c_0, \ldots, c_{j-1} </math> are all less than <math>j </math>, no other terms that precede <math>c_{k} </math> can be unequal to <math>c_k </math>. The lemma follows. |
− | '''Lemma 2.''' If <math> | + | '''Lemma 2.''' If <math>t(c_k) = c_k = j</math>, then <math>t^2(c_k) = t(c_k) </math> (where <math>f^2(x) = f(f(x))</math>). |
− | ''Proof.'' Since only <math> | + | ''Proof.'' Since only <math>i </math> terms precede the term <math>c_i </math>, we will have <math> t^m(c_i) \le i </math>, for any integer <math>m </math>. This means that we will always have <math> t^m (c_0), \ldots, t^m (c_{j-1}) < j </math>. This means that <math>c_j = t(c_j) = \cdots = c_k = t(c_k) </math>, and the lemma follows by iteration. |
− | Thus we may regard a term <math> | + | Thus we may regard a term <math>c_k </math> as ''stable'' if <math>t(c_k) = c_k </math>. We will call a sequence ''stable'' if all of its terms are stable. |
− | '''Lemma 3.''' If <math> | + | '''Lemma 3.''' If <math>c_k =j </math> is not stable, then <math>t(c_k) > c_k </math>. |
− | ''Proof.'' We have <math> c_0, \ldots, c_{j-1} < j </math>, so we always have <math> t(c_k) \ge c_k </math>. Equality implies that <math> | + | ''Proof.'' We have <math> c_0, \ldots, c_{j-1} < j </math>, so we always have <math> t(c_k) \ge c_k </math>. Equality implies that <math>c_k </math> is stable. |
− | We will now prove the problem by induction. For the base case, <math> | + | We will now prove the problem by induction. For the base case, <math>n=1 </math>, we have either 0,0 or 0,1, both of which are stable. Now, suppose that <math> t^{n-2}(a_0), \ldots, t^{n-2}(a_{n-1}) </math> are stable. We must then have <math> t^{n-2}(a_n) \in \{ n-2, n-1, n\} </math>. If <math>t^{n-2}(a_n) = n </math>, then it is already stable. If <math>t^{n-2}(a_n) = n-1 </math>, then either it is already stable or <math>t^{n-1}(a_n) = n </math>, which is stable. If <math>t^{n-2}(a_n) = t^{n-2}(a_{n-1}) </math>, then <math>t^{n-2}(a_n) </math> must already be stable. The only possibilities remaining are <math>t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) = n-1 </math> and <math>t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) < n-2 </math>. In the first case, we must have <math>t^{n-1}(a_n) </math> equal to <math>n-1 </math> or <math>n </math>, both of which will make it stable. In the second case, we must have <math>t^{n-2}(a_{n-2}) = t^{n-2}(a_{n-1}) < n-2 </math>, giving us <math>t^{n-1}(a_n) = n </math>, which will make it stable. Thus the induction is complete. |
{{alternate solutions}} | {{alternate solutions}} | ||
− | |||
− | + | == See also == | |
− | + | {{USAMO newbox|year=2003|num-b=2|num-a=4}} | |
[[Category:Olympiad Algebra Problems]] | [[Category:Olympiad Algebra Problems]] |
Revision as of 20:51, 6 April 2013
Problem
Let . For every sequence of integers
satisfying , for , define another sequence
by setting to be the number of terms in the sequence that precede the term and are different from . Show that, starting from any sequence as above, fewer than applications of the transformation lead to a sequence such that .
Solution
Consider some sequence as the image of after has been applied some finite number of times.
Lemma 1. If , then ().
Proof. Since the terms are all less than , no other terms that precede can be unequal to . The lemma follows.
Lemma 2. If , then (where ).
Proof. Since only terms precede the term , we will have , for any integer . This means that we will always have . This means that , and the lemma follows by iteration.
Thus we may regard a term as stable if . We will call a sequence stable if all of its terms are stable.
Lemma 3. If is not stable, then .
Proof. We have , so we always have . Equality implies that is stable.
We will now prove the problem by induction. For the base case, , we have either 0,0 or 0,1, both of which are stable. Now, suppose that are stable. We must then have . If , then it is already stable. If , then either it is already stable or , which is stable. If , then must already be stable. The only possibilities remaining are and . In the first case, we must have equal to or , both of which will make it stable. In the second case, we must have , giving us , which will make it stable. Thus the induction is complete.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
2003 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |