2003 USAMO 第 3 题

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

让$n \neq 0$。对于每个整数序列

$$

A = a_0,a_1,a_2,\点, a_n

$$

满足$0 \le a_i \le i$，对于$i=0,\dots,n$，定义另一个序列

$$t(A)= t(a_0), t(a_1), t(a_2), \dots, t(a_n)$$

通过将 $t(a_i)$ 设置为序列 $A$ 中位于项 $a_i$ 之前且与 $a_i$ 不同的项数。证明，从上述任何序列 $A$ 开始，少于 $n$ 个变换 $t$ 的应用会导致序列 $B$ 使得 $t(B) = B$。