https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_3&feed=atom&action=history
2003 USAMO Problems/Problem 3 - Revision history
2024-03-28T13:54:29Z
Revision history for this page on the wiki
MediaWiki 1.31.1
https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_3&diff=54775&oldid=prev
Nathan wailes at 17:39, 4 July 2013
2013-07-04T17:39:24Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 17:39, 4 July 2013</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l44" >Line 44:</td>
<td colspan="2" class="diff-lineno">Line 44:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Olympiad Algebra Problems]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Olympiad Algebra Problems]]</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">{{MAA Notice}}</ins></div></td></tr>
</table>
Nathan wailes
https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_3&diff=52250&oldid=prev
Yrushi at 01:51, 7 April 2013
2013-04-07T01:51:43Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 01:51, 7 April 2013</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l13" >Line 13:</td>
<td colspan="2" class="diff-lineno">Line 13:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></math></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></math></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></center></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></center></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>by setting <math> <del class="diffchange diffchange-inline">\displaystyle </del>t(a_i) </math> to be the number of  terms in the sequence <math> <del class="diffchange diffchange-inline">\displaystyle </del>A </math> that precede the term <math> <del class="diffchange diffchange-inline">\displaystyle </del>a_i </math> and are different from <math> <del class="diffchange diffchange-inline">\displaystyle </del>a_i </math>. Show that, starting from any sequence <math> <del class="diffchange diffchange-inline">\displaystyle </del>A </math> as above, fewer than <math> <del class="diffchange diffchange-inline">\displaystyle </del>n </math> applications of the transformation <math> <del class="diffchange diffchange-inline">\displaystyle </del>t </math> lead to a sequence <math> <del class="diffchange diffchange-inline">\displaystyle </del>B </math> such that <math> <del class="diffchange diffchange-inline">\displaystyle </del>t(B) = B </math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Solution ==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Solution ==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Consider some sequence <math> C = c_0, \ldots, c_n </math> as the image of <math> <del class="diffchange diffchange-inline">\displaystyle </del>A </math> after <math> <del class="diffchange diffchange-inline">\displaystyle </del>t </math> has been applied some finite number of times.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>'''Lemma 1.'''  If <math> <del class="diffchange diffchange-inline">\displaystyle </del>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>).</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>'''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>).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>''Proof.'' Since the <math> <del class="diffchange diffchange-inline">\displaystyle </del>j </math> terms <math> <del class="diffchange diffchange-inline">\displaystyle </del>c_0, \ldots, c_{j-1} </math> are all less than <math> <del class="diffchange diffchange-inline">\displaystyle </del>j </math>, no other terms that precede <math> <del class="diffchange diffchange-inline">\displaystyle </del>c_{k} </math> can be unequal to <math> <del class="diffchange diffchange-inline">\displaystyle </del>c_k </math>.  The lemma follows.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>''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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>'''Lemma 2.''' If <math> <del class="diffchange diffchange-inline">\displaystyle </del>t(c_k) = c_k = j</math>, then <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^2(c_k) = t(c_k) </math> (where <math> <del class="diffchange diffchange-inline">\displaystyle </del>f^2(x) = f(f(x))</math>).</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>'''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>).</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>''Proof.''  Since only <math> <del class="diffchange diffchange-inline">\displaystyle </del>i </math> terms precede the term <math> <del class="diffchange diffchange-inline">\displaystyle </del>c_i </math>, we will have <math> t^m(c_i) \le i </math>, for any integer <math> <del class="diffchange diffchange-inline">\displaystyle </del>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> <del class="diffchange diffchange-inline">\displaystyle </del>c_j = t(c_j) = \cdots = c_k = t(c_k) </math>, and the lemma follows by iteration.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>''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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Thus we may regard a term <math> <del class="diffchange diffchange-inline">\displaystyle </del>c_k </math> as ''stable'' if <math> <del class="diffchange diffchange-inline">\displaystyle </del>t(c_k) = c_k </math>.  We will call a sequence ''stable'' if all of its terms are stable.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>'''Lemma 3.'''  If <math> <del class="diffchange diffchange-inline">\displaystyle </del>c_k =j </math> is not stable, then <math> <del class="diffchange diffchange-inline">\displaystyle </del>t(c_k) > c_k </math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>'''Lemma 3.'''  If <math>c_k =j </math> is not stable, then <math>t(c_k) > c_k </math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>''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> <del class="diffchange diffchange-inline">\displaystyle </del>c_k </math> is stable.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>''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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We will now prove the problem by induction.  For the base case, <math> <del class="diffchange diffchange-inline">\displaystyle </del>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> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-2}(a_n) = n </math>, then it is already stable.  If <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-2}(a_n) = n-1 </math>, then either it is already stable or <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-1}(a_n) = n </math>, which is stable.  If <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-2}(a_n) = t^{n-2}(a_{n-1}) </math>, then <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-2}(a_n) </math> must already be stable.  The only possibilities remaining are <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) = n-1 </math> and <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-2}(a_n) = n-2, t^{n-2}(a_{n-1}) < n-2 </math>.  In the first case, we must have <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-1}(a_n) </math> equal to <math> <del class="diffchange diffchange-inline">\displaystyle </del>n-1 </math> or <math> <del class="diffchange diffchange-inline">\displaystyle </del>n </math>, both of which will make it stable.  In the second case, we must have <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-2}(a_{n-2}) = t^{n-2}(a_{n-1}) < n-2 </math>, giving us <math> <del class="diffchange diffchange-inline">\displaystyle </del>t^{n-1}(a_n) = n </math>, which will make it stable.  Thus the induction is complete.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{alternate solutions}}</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{{alternate solutions}}</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">== Resources ==</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* [[</del>2003 <del class="diffchange diffchange-inline">USAMO Problems]]</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">== See also ==</ins></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p</del>=<del class="diffchange diffchange-inline">336202#p336202 Discussion on AoPS/MathLinks]</del></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">{{USAMO newbox|year=</ins>2003<ins class="diffchange diffchange-inline">|num-b=2|num-a</ins>=<ins class="diffchange diffchange-inline">4}}</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Olympiad Algebra Problems]]</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Olympiad Algebra Problems]]</div></td></tr>
</table>
Yrushi
https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_3&diff=14675&oldid=prev
Boy Soprano II at 14:10, 22 April 2007
2007-04-22T14:10:20Z
<p></p>
<p><b>New page</b></p><div>== Problem ==<br />
<br />
Let <math> n \neq 0 </math>. For every sequence of integers<br />
<center><br />
<math><br />
A = a_0,a_1,a_2,\dots, a_n<br />
</math><br />
</center><br />
satisfying <math>0 \le a_i \le i</math>, for <math>i=0,\dots,n</math>, define another sequence<br />
<center><br />
<math><br />
t(A)= t(a_0), t(a_1), t(a_2), \dots, t(a_n)<br />
</math><br />
</center><br />
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>.<br />
<br />
== Solution ==<br />
<br />
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.<br />
<br />
'''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>).<br />
<br />
''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.<br />
<br />
'''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>).<br />
<br />
''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.<br />
<br />
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.<br />
<br />
'''Lemma 3.''' If <math> \displaystyle c_k =j </math> is not stable, then <math> \displaystyle t(c_k) > c_k </math>.<br />
<br />
''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.<br />
<br />
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.<br />
<br />
<br />
{{alternate solutions}}<br />
<br />
== Resources ==<br />
<br />
* [[2003 USAMO Problems]]<br />
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=336202#p336202 Discussion on AoPS/MathLinks]<br />
<br />
<br />
[[Category:Olympiad Algebra Problems]]</div>
Boy Soprano II