, 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}{c|cccccc} & 0 & 1 & \dots & x-1 & \dots & i \\\hline 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}{c|cccc} & 0 & 1 & \dots & i \\\hline 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' = (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.

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$.