Difference between revisions of "2003 USAMO Problems/Problem 3"

Revision as of 21:51, 6 April 2013

Problem

Let $n \neq 0$ . For every sequence of integers

$A = a_0,a_1,a_2,\dots, a_n$

satisfying $0 \le a_i \le i$ , for $i=0,\dots,n$ , define another sequence

$t(A)= t(a_0), t(a_1), t(a_2), \dots, t(a_n)$

by setting $t(a_i)$ to be the number of terms in the sequence $A$ that precede the term $a_i$ and are different from $a_i$ . Show that, starting from any sequence $A$ as above, fewer than $n$ applications of the transformation $t$ lead to a sequence $B$ such that $t(B) = B$ .

Solution

Consider some sequence $C = c_0, \ldots, c_n$ as the image of $A$ after $t$ has been applied some finite number of times.

Lemma 1. If $t(c_k) = c_k = j$ , then ${} c_j = \cdots = c_{j+i} = \cdots = c_k = j$ ( $0 \le i \le k-j$ ).

Proof. Since the $j$ terms $c_0, \ldots, c_{j-1}$ are all less than $j$ , no other terms that precede $c_{k}$ can be unequal to $c_k$ . The lemma follows.

Lemma 2. If $t(c_k) = c_k = j$ , then $t^2(c_k) = t(c_k)$ (where $f^2(x) = f(f(x))$ ).

Proof. Since only $i$ terms precede the term $c_i$ , we will have $t^m(c_i) \le i$ , for any integer $m$ . This means that we will always have $t^m (c_0), \ldots, t^m (c_{j-1}) < j$ . This means that $c_j = t(c_j) = \cdots = c_k = t(c_k)$ , and the lemma follows by iteration.

Thus we may regard a term $c_k$ as stable if $t(c_k) = c_k$ . We will call a sequence stable if all of its terms are stable.

Lemma 3. If $c_k =j$ is not stable, then $t(c_k) > c_k$ .

Proof. We have $c_0, \ldots, c_{j-1} < j$ , so we always have $t(c_k) \ge c_k$ . Equality implies that $c_k$ is stable.

We will now prove the problem by induction. For the base case, $n=1$ , we have either 0,0 or 0,1, both of which are stable. Now, suppose that $t^{n-2}(a_0), \ldots, t^{n-2}(a_{n-1})$ are stable. We must then have $t^{n-2}(a_n) \in \{ n-2, n-1, n\}$ . If $t^{n-2}(a_n) = n$ , then it is already stable. If $t^{n-2}(a_n) = n-1$ , then either it is already stable or $t^{n-1}(a_n) = n$ , which is stable. If $t^{n-2}(a_n) = t^{n-2}(a_{n-1})$ , then $t^{n-2}(a_n)$ must already be stable. The only possibilities remaining are $t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) = n-1$ and $t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) < n-2$ . In the first case, we must have $t^{n-1}(a_n)$ equal to $n-1$ or $n$ , both of which will make it stable. In the second case, we must have $t^{n-2}(a_{n-2}) = t^{n-2}(a_{n-1}) < n-2$ , giving us $t^{n-1}(a_n) = n$ , 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.

@@ Line 13: / Line 13: @@
 </math>
 </center>
-by setting <math> \displaystyle t(a_i) </math> to be the number of  terms in the sequence <math> \displaystyle A </math> that precede the term <math> \displaystyle a_i </math> and are different from <math> \displaystyle a_i </math>. Show that, starting from any sequence <math> \displaystyle A </math> as above, fewer than <math> \displaystyle n </math> applications of the transformation <math> \displaystyle t </math> lead to a sequence <math> \displaystyle B </math> such that <math> \displaystyle t(B) = B </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 ==
-Consider some sequence <math> C = c_0, \ldots, c_n </math> as the image of <math> \displaystyle A </math> after <math> \displaystyle t </math> has been applied some finite number of times.
+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> \displaystyle 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>).
+'''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> \displaystyle j </math> terms <math> \displaystyle c_0, \ldots, c_{j-1} </math> are all less than <math> \displaystyle j </math>, no other terms that precede <math> \displaystyle c_{k} </math> can be unequal to <math> \displaystyle c_k </math>.  The lemma follows.
+''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> \displaystyle t(c_k) = c_k = j</math>, then <math> \displaystyle t^2(c_k) = t(c_k) </math> (where <math> \displaystyle f^2(x) = f(f(x))</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> \displaystyle i </math> terms precede the term <math> \displaystyle c_i </math>, we will have <math> t^m(c_i) \le i </math>, for any integer <math> \displaystyle 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> \displaystyle c_j = t(c_j) = \cdots = c_k = t(c_k) </math>, and the lemma follows by iteration.
+''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> \displaystyle c_k </math> as ''stable'' if <math> \displaystyle t(c_k) = c_k </math>.  We will call a sequence ''stable'' if all of its terms are stable.
+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> \displaystyle c_k =j </math> is not stable, then <math> \displaystyle t(c_k) > c_k </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> \displaystyle c_k </math> is stable.
+''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> \displaystyle 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> \displaystyle t^{n-2}(a_n) = n </math>, then it is already stable.  If <math> \displaystyle t^{n-2}(a_n) = n-1 </math>, then either it is already stable or <math> \displaystyle t^{n-1}(a_n) = n </math>, which is stable.  If <math> \displaystyle t^{n-2}(a_n) = t^{n-2}(a_{n-1}) </math>, then <math> \displaystyle t^{n-2}(a_n) </math> must already be stable.  The only possibilities remaining are <math> \displaystyle t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) = n-1 </math> and <math> \displaystyle t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) < n-2 </math>.  In the first case, we must have <math> \displaystyle t^{n-1}(a_n) </math> equal to <math> \displaystyle n-1 </math> or <math> \displaystyle n </math>, both of which will make it stable.  In the second case, we must have <math> \displaystyle t^{n-2}(a_{n-2}) = t^{n-2}(a_{n-1}) < n-2 </math>, giving us <math> \displaystyle t^{n-1}(a_n) = n </math>, which will make it stable.  Thus the induction is complete.
+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}}
-== Resources ==
-* [[2003 USAMO Problems]]
+== See also ==
-* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=336202#p336202 Discussion on AoPS/MathLinks]
+{{USAMO newbox|year=2003|num-b=2|num-a=4}}
 [[Category:Olympiad Algebra Problems]]

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

Page

Toolbox

Search

Difference between revisions of "2003 USAMO Problems/Problem 3"

Revision as of 21:51, 6 April 2013

Problem

Solution

See also