趣题：不断将各数替换为右侧比其小的数的个数，数列终将不再变化

下面这个问题出自The American Mathematical Monthly (Vol.75, No.3.(Mar.,1968), pp.299-301)：

给定一个有限长的非负整数序列。一次操作是指把数列中的每个数替换为它右边比它小的数的个数。对该数列不断进行这个操作。证明总有一个时刻该数列将不再发生改变（即此时每个数都恰好等于它右边比它小的数的个数）。

下面是一个实际的例子。这个数列在第四次操作之后进入循环，不再发生改变。

5, 44, 19,6, 49,1, 27, 19, 50, 20

1,6,2,1,4,0,2,0,1,0

3,8,5,3,5,0,3,0,1,0

4,8,6,4,5,0,3,0,1,0

5,8,7,5,5,0,3,0,1,0

5,8,7,5,5,0,3,0,1,0

………………..

证明过程非常简单，你只需要注意到：前面的数永远不会影响到后面的序列的变化。因此我们想到了用数学归纳法。当序列长度n=1时，一次操作后这个数将永远变成0，因此n=1时结论显然成立。假设当n=k时结论成立，我们证明n=k+1时结论也成立。注意到序列的第一个数不影响后面的数的变化，由我们的假设，后面长度为k的子序列(A₂, A₃, …, A_k+1)将在若干次操作后停止变化。假设此时整个序列为(A₁‘, A₂‘, …, A_k+1‘)。对这个序列再做一次变换我们得到(A₁”, A₂‘, …, A_k+1‘)。如果A₁”=A₁‘，则整个序列已经不再变化了，我们不必再多考虑。如果A₁”>A₁‘，即最后这一次变换让第一个数变大了，这样的话后面比它小的数将增多，于是第一个数将越变越大；但第一个数再大也不可能超过k，因此它增大到一定时候必然会停下来，此时整个序列就不再变化了。类似地，如果A₁”<A₁‘，那么第一个数将越变越小，但它的下界为0，因此总有一个时刻停下来，此时整个序列也就恒定了。

参考资料：http://www.cut-the-knot.org/Curriculum/Algebra/RightReplacement.shtml