下面这个问题出自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的子序列(A2, A3, …, Ak+1)将在若干次操作后停止变化。假设此时整个序列为(A1‘, A2‘, …, Ak+1‘)。对这个序列再做一次变换我们得到(A1”, A2‘, …, Ak+1‘)。如果A1”=A1‘,则整个序列已经不再变化了,我们不必再多考虑。如果A1”>A1‘,即最后这一次变换让第一个数变大了,这样的话后面比它小的数将增多,于是第一个数将越变越大;但第一个数再大也不可能超过k,因此它增大到一定时候必然会停下来,此时整个序列就不再变化了。类似地,如果A1”<A1‘,那么第一个数将越变越小,但它的下界为0,因此总有一个时刻停下来,此时整个序列也就恒定了。
参考资料:http://www.cut-the-knot.org/Curriculum/Algebra/RightReplacement.shtml
0点抢沙发
晕
来晚了
M67最近更新好频繁……
我在玩DROD的时候,在玩第二关,在once south,once east那块就过不去了,用到了数学知识了么?走什么不,他都要钻进去,该怎么办,不要告我答案,我该看什么资料才能想到,谢谢!!!
http://zhidao.baidu.com/question/58292539.html
麻烦看看这个- –
我立即想到了最长非降子序列的 O(nlogn) …………
您好!
从您的博客能够看出您对计算数学有较深的造诣。我现在已经研究出NP完全问题的多项式时间算法,我的结论是:NP = P!
最初始的论文请看我的博客,欢迎批评指正。
http://blog.sina.com.cn/iamthe01officer
最终的论文我准备出书,正在筹划中。
前面的数永远不会影响到后面的序列的变化