Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m
 
Line 44: Line 44:
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:39, 4 July 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.


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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_3&oldid=54775"