大圆形赌桌上坐着很多人。赌局开始每人都有几个（蓝）筹码。随着赌局的进行，牌打得好的人面前蓝筹码越来越多，牌打得不好的人蓝筹码输光了，变成红筹码。（蓝筹码表示正分，红筹码表示负分。）这时庄家出来说要搞一搞均贫富。他的方法是：从有红筹码的人中随机选一个出来，把他的红筹码都变成蓝筹码，同时，为保持总分平衡，从他的两个左右邻居中每人减掉相应的蓝筹码（或添加相应的红筹码）。比如，Ａ有５个红筹码，他的左邻有８个蓝筹码，右邻有３个蓝筹码。对Ａ均贫富以后，Ａ的５个红筹码变成５个蓝筹码。他的左邻变成３个蓝筹码，而他的右邻变成２个红筹码。
1）现在知道，桌面上蓝筹码的总数比红筹码多。试证明如果一直这样均贫富下去，一定能使桌上不存在任何有红筹码的人。
2）需要搞多少次均贫富才能使桌上不存在有红筹码的人? （求出上界，或找出计算方法。）
解答
考虑筹码的部分和序列，即从某个人开始，把所有人的筹码数依序加起来，形成一个序列。这个序列可以延长成无穷序列。例如五个人有筹码5，-8，3，10，-6个，则序列为（5，-3，0，10，4，9，1，4，14，8，13，5，9，18，12，…）。如果所有人的筹码都是非负的，这个序列就是递增的。一开始时有一些倒序，即前面的数比后面大。而每次运作都是交换两个相邻的倒序数。有限次后一定会消除所有的倒序。（倒序是周期的，只要消除一个周期内的倒序，整个序列的就都消除了。）
容易看出不论怎样选，需要的次数总是相同的，等于一个周期内数的倒序的总和。例如5，-3，0，10，4的一个周期，5有5个倒序（-3，0，4，1，4），-3和0没有倒序，10有8个倒序（4，9，1，4，8，5，9，9），4有1个倒序（1），一共14 个，14 次可以消除所有倒序。
设共有n个人，b个蓝筹码，r个红筹码，k = ceiling(r/(b-r))。倒序数的一个上界是[(n/2)^2] * k + ((n-1)/2)^2。用前面的例子，5个人，14个红筹码，18个蓝筹码，上界为6*4 + 4 = 28。最接近这个上界的一个分布是（18，0，-13，-1，0），总倒序数为26。一般来说，要得到最大的倒序数，蓝筹码应该都给一个人，这人对面的人拿 (b-r)*(k-1)+1 个红筹码，剩下的红筹码其余人均分。
咱又偷学了不少 
我后来想到，在我昨天的解法里的 {X,Y}, 如果 X,Y 分别定义为蓝筹码和红筹码的和，也许就能得到类似的结果。还需要想想。 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |