USA IMO 2003

First Solution. Note first that the transformed sequence $t(a)$ also satisfies the inequalities $0\le t(a{)}_i\le i$, for $i=0,\dots ,n$. Call any integer sequence that satisfies these inequalities an index bounded sequence. We prove now that $a_i\le t(a{)}_i$, for $i=0,\dots ,n$. Indeed, this is clear if $a_i=0$. Otherwise, let $x=a_i>0$ and $y=t(a{)}_i$. None of the first $x$ consecutive terms $a_0,a_1,\dots ,a_{x-1}$ is greater than $x-1$, so they are all different from $x$ and precede $x$ (see the diagram below). Thus $y\ge x$, that is, $a_i\le t(a{)}_i$, for $i=0,\dots ,n$.

$$\begin{array}{ccccccc}& 0& 1& \dots & x-1& \dots & i\\ a& a_0& a_1& \dots & a_{x-1}& \dots & x\\ t(a)& t(a{)}_0& t(a{)}_1& \dots & t(a{)}_{x-1}& \dots & y\end{array}$$

This already shows that the sequences stabilize after finitely many applications of the transformation $t$, because the value of the index $i$ term in index bounded sequences cannot exceed $i$. Next we prove that if $a_i=t(a{)}_i$, for some $i=0,\dots ,n$, then no further applications of $t$ will ever change the index $i$ term. We consider two cases.

In this case, we assume that $a_i=t(a{)}_i=0$. This means that no term on the left of $a_i$ is different from 0, that is, they are all 0. Therefore the first $i$ terms in $t(a)$ will also be 0 and this repeats (see the diagram below).

$$\begin{array}{ccccc}& 0& 1& \dots & i\\ a& 0& 0& \dots & 0\\ t(a)& 0& 0& \dots & 0\end{array}$$

In this case, we assume that $a_i=t(a{)}_i=x>0$. The first $x$ terms are all different from $x$. Because $t(a{)}_i=x$, the terms $a_x,a_{x+1},\dots ,a_{i-1}$ must then all be equal to $x$. Consequently, $t(a{)}_j=x$ for $j=x,\dots ,i-1$ and further applications of $t$ cannot change the index $i$ term (see the diagram below).

	0	1	...	$x-1$	$x$	$x+1$	...	$i$
$a$	$a_0$	$a_1$	...	$a_{x-1}$	$x$	$x$	...	$x$
$t(a)$	$t(a{)}_0$	$t(a{)}_1$	...	$t(a{)}_{x-1}$	$x$	$x$	...	$x$

For $0\le i\le n$, the index $i$ entry satisfies the following properties: (i) it takes integer values; (ii) it is bounded above by $i$; (iii) its value does not decrease under transformation $t$; and (iv) once it stabilizes under transformation $t$, it never changes again. This shows that no more than $n$ applications of $t$ lead to a sequence that is stable under the transformation $t$.

Finally, we need to show that no more than $n-1$ applications of $t$ is needed to obtain a fixed sequence from an initial $n+1$-term index bounded sequence $a=(a_0,a_1,\dots ,a_n)$. We induct on $n$.

For $n=1$, the two possible index bounded sequences $(a_0,a_1)=(0,0)$ and $(a_0,a_1)=(0,1)$ are already fixed by $t$ so we need zero applications of $t$.

Assume that any index bounded sequence $(a_0,a_1,\dots ,a_n)$ reach a fixed sequence after no more than $n-1$ applications of $t$. Consider an index bounded sequence $a=(a_0,a_1,\dots ,a_{n+1})$. It suffices to show that $a$ will be stabilized in no more than $n$ applications of $t$. We approach indirectly by assuming on the contrary that $n+1$ applications of transformations are needed. This can happen only if $a_{n+1}=0$ and each application of $t$ increased the index $n+1$ term by exactly 1. Under transformation $t$, the resulting value of index $i$ term will not be effected by index $j$ term for $i<j$. Hence by the induction hypothesis, the subsequence $a^{\prime }=(a_0,a_1,\dots ,a_n)$ will be stabilized in no more than $n-1$ applications of $t$. Because index $n$ term is stabilized at value $x\le n$ after no more than $\min \{x,n-1\}$ applications of $t$ and index $n+1$ term obtains value $x$ after exactly $x$ applications of $t$ under our current assumptions. We conclude that the index $n+1$ term would become equal to the index $n$ term after no more than $n-1$ applications of $t$. However, once two consecutive terms in a sequence are equal they stay equal and stabilize together. Because the index $n$ term needs no more than $n-1$ transformations to be stabilized, $a$ can be stabilized in no more than $n-1$ applications of $t$, which contradicts our assumption of $n+1$ applications needed. Thus our assumption was wrong and we need at most $n$ applications of transformation $t$ to stabilize an $(n+1)$-term index bounded sequence. This completes our inductive proof.

---

Alternative solution.

Second Solution. We prove that for $n\ge 2$, the claim holds without the initial condition $0\le a_i\le i$. (Of course this does not prove anything stronger, but it's convenient.) We do this by induction on $n$, the case $n=2$ being easy to check by hand as in the first solution.

Note that if $c=(c_0,\dots ,c_n)$ is a sequence in the image of $t$, and $d$ is the sequence $(c_1,\dots ,c_n)$, then the following two statements are true:

(a) If $e$ is the sequence obtained from $d$ by subtracting 1 from each nonzero term, then $t(d)=t(e)$. (If there are no zero terms in $d$, then subtracting 1 clearly has no effect. If there is a zero term in $d$, it must occur at the beginning, and then every nonzero term is at least 2.)

(b) One can compute $t(c)$ by applying $t$ to the sequence $c_1,\dots ,c_n$, adding 1 to each nonzero term, and putting a zero in front.

The recipe of (b) works for computing $t^i(c)$ for any $i$, by (a) and induction on $i$.

We now apply the induction hypothesis to $t(a{)}_1,\dots ,t(a{)}_n$ to see that it stabilizes after $n-2$ more applications of $t$; by the recipe above, that means $a$ stabilizes after $n-1$ applications of $t$.