均贫富

constant · 发表于 2006-1-16 21:26:41

难度：+++

www.ddhw.com

大圆形赌桌上坐着很多人。赌局开始每人都有几个（蓝）筹码。随着赌局的进行，牌打得好的人面前蓝筹码越来越多，牌打得不好的人蓝筹码输光了，变成红筹码。（蓝筹码表示正分，红筹码表示负分。）这时庄家出来说要搞一搞均贫富。他的方法是：从有红筹码的人中随机选一个出来，把他的红筹码都变成蓝筹码，同时，为保持总分平衡，从他的两个左右邻居中每人减掉相应的蓝筹码（或添加相应的红筹码）。比如，Ａ有５个红筹码，他的左邻有８个蓝筹码，右邻有３个蓝筹码。对Ａ均贫富以后，Ａ的５个红筹码变成５个蓝筹码。他的左邻变成３个蓝筹码，而他的右邻变成２个红筹码。再比如，Ａ有１５个红筹码，他的左邻有１８个蓝筹码，右邻有３个红筹码。对Ａ均贫富以后，Ａ的１５个红筹码变成１５个红筹码。他的左邻变成３个蓝筹码，而他的右邻变成１８个红筹码。

www.ddhw.com

1）现在知道，桌面上蓝筹码的总数比红筹码多。试证明如果一直这样均贫富下去，一定能使桌上不存在任何有红筹码的人。

www.ddhw.com

2）需要搞多少次均贫富才能使桌上不存在有红筹码的人? （求出上界，或找出计算方法。）

LOTUSEATER · 发表于 2006-1-16 22:24:31

你看﹐難題才有挑戰性嘛﹗讓大夥兒多想想﹐才有成就感啊

本贴由[LOTUSEATER]最后编辑于：2006-1-16 14:42:40

QL · 发表于 2006-1-17 00:41:38

I guess the first one is not very hard: Just notice the fact that the total number of red chips will not increase during this process, in fact, the only time that the number of red chips remains unchanged is when, both of the neibours have red chips (i.e., all the three involved guys have only red chips). Suppose there are totally n people in the game, and totally k red chips, it is easy to see that the number of red chips will keep unchanged for at most [n/2] steps, in another word, after every [n/2]+1 step, the total number of red chips will be reduced at least by 1. This gives one upper bound for question 2: k*([n/2]+1)

Of cause, this upper bound is overly conservative, anyone cares to give a better one or even the superemum?

sean9991 · 发表于 2006-1-17 01:42:53

Is the argument "the total number of red chips will not increase during this process" correct?

Consider these three people with chips 3, -10, 3. The outcome after the process is -7, 10, -7.

The number of red chip is 10 before, and 14 after.

ob · 发表于 2006-1-17 04:34:16

Set the initial number of chips for each person is Ni. Set # of red chip is Nr, and blue chips is Nb. Initially, Nrwww.ddhw.com

QL · 发表于 2006-1-17 04:59:18

You are right. I didn't think about it very carefully.

constant · 发表于 2006-1-18 20:56:23

给个提示：这题和计算机算法（sorting）有关。

流动的建筑 · 发表于 2006-1-18 21:36:56

已经有些想法了，但觉得要清楚地写出来会比较长，有空时再写。

constant · 发表于 2006-1-21 15:58:48

还有人想吗？

流动的建筑 · 发表于 2006-1-22 00:11:16

让 constant 的好题晾了半天，不好意思，实在是比较忙。我敲中文太慢，下面用英文简单地说一下我的想法。

Let's consider the simplest case of two numbers {X0,Y0}, where X0+Y0 = D > 0. Without losing generality, assume X0 > 0, Y0 < 0. After the first round of operation, {X0,Y0} becomes {X1,Y1}, where X1=X0+2*Y0 (since X0 is both the left and right neighbor of Y0), and Y1=-Y0. If X1<0, then the operation is applied again, we get {X2,Y2}, and so on.

Generally speaking, all {Xi,Yi} pairs are points on the line X+Y=D. It is not difficult to prove that no matter where the initial point {X0,Y0} is, eventually after n round, where n=floor(-Y0/D), {Xn,Yn} will fall into the interval where Xn and Yn are both positive.

For cases where we have more than two numbers, they are essentially equivalent to the case of two numbers if we observe the following properties.

i) Each operation only affect the immediate neighboring points;
ii) Each operation does not change the sum of any set that includes the affected points.

Therefore we can always partition the whole set into two subsets, after a finite number of operations, the sum of both subsets becomes positive. If there are still some negative numbers inside the subsets, similar analysis can be applied again.

A strict proof will probably take many more words.

constant · 发表于 2006-1-22 02:56:40

and looks like it should work. But the best solution is much simpler, and it gives a traight forward upper bound.

流动的建筑 · 发表于 2006-1-22 06:15:13

愿闻其详

		自动登录	找回密码
密码			立即注册

动态微博

均贫富

我想過了哈﹐沒想出來﹗

回复：均贫富

回复：回复：均贫富

回复：均贫富

回复：回复：回复：均贫富

给个提示：这题和计算机算法（sorting）有关。

好题！

还有人想吗？

回复：还有人想吗？

Interesting thought,

愿闻其详