2003 USAMO Problems/Problem 3

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 $\displaystyle t(a_i)$ to be the number of terms in the sequence $\displaystyle A$ that precede the term $\displaystyle a_i$ and are different from $\displaystyle a_i$ . Show that, starting from any sequence $\displaystyle A$ as above, fewer than $\displaystyle n$ applications of the transformation $\displaystyle t$ lead to a sequence $\displaystyle B$ such that $\displaystyle t(B) = B$ .

Solution

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

Lemma 1. If $\displaystyle 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 $\displaystyle j$ terms $\displaystyle c_0, \ldots, c_{j-1}$ are all less than $\displaystyle j$ , no other terms that precede $\displaystyle c_{k}$ can be unequal to $\displaystyle c_k$ . The lemma follows.

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

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

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

Lemma 3. If $\displaystyle c_k =j$ is not stable, then $\displaystyle 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 $\displaystyle c_k$ is stable.

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