圆桌问题

新用户

k个人围着圆桌而坐，每个人的胸前都有一块牌子，上面写着一个数字。

假设：

1、最初每个胸前的数字是随机数。
2、每个人可以看到自己的胸前数字，和下一个人牌子上的数字。
3、每一轮按照座位顺序，各人调整自己胸前的数字，即第1个人先根据自己胸前的数字
和下一个人牌子上的数字来调整自己的数字，然后是第2个人根据自己和第3个人的数字
调整自己的数字，再是第4个人，...,最后是第k个人。其中，第k个人调整比较特殊，他
只能根据自己的数字和第1个人在本轮调整前的数字来调整自己的数字。

问题：应该采取什么样的策略，能够保证：每一轮的数字之和都相等，并且只要轮数足
够多（次数趋于无穷时，极限都存在且相同也可以），则最终每个人牌子上的数字会相等。如果存在这样的策略，能否从理论上证明之？

www.ddhw.com

 

乱弹

This strategy is obvious: everyone takes the average of his number and next number as his new number.    www.ddhw.com To show that  this must work, consider  the sum of all |a(i)-a(j)|, where a(i) is the number that the i-th person has right now. It is easy to show that this sum is nonincreasing after one round's number changing. Thus there is a limit. Further discussion will conclude that the limit is zero. To find the converge rate, we need to go further.   Probably there are some other strategies that are similar but work better.  www.ddhw.com If the players are allowed to have memory and they can change strategies round by round, then there should be better strategies. For example, one cheating strategy: for the first k rounds, the k-th person increases  his old number by the first guy's number,  the (k-1)-th person changes his number to zero, other guys take the next number.  Then after k rounds, the k-th person has the sum of all numbers, and others have zero. The next is to redistribute the sum.   This strategy need every one to know the value of k.       www.ddhw.com

新用户

To show that  this must work, consider  the sum of all |a(i)-a(j)|, where a(i) is the number that the i-th person has right now. It is easy to show that this sum is nonincreasing after one round's number changing. Thus there is a limit. Further discussion will conclude that the limit is zero. To find the converge rate, we need to go further.   能否证明在有限次内解决问题？    www.ddhw.com If the players are allowed to have memory and they can change strategies round by round, then there should be better strategies. For example, one cheating strategy: for the first k rounds, the k-th person increases  his old number by the first guy's number,  the (k-1)-th person changes his number to zero, other guys take the next number.  Then after k rounds, the k-th person has the sum of all numbers, and others have zero. The next is to redistribute the sum.   This strategy need every one to know the value of k.   very interesting.... www.ddhw.com

乱弹

能否证明在有限次内解决问题？ In general, my strategy won't stop in finite steps.  For example, if K is odd,   it never stops.  When will it stop? I guess we need to study binomials.www.ddhw.com   My strategy is just a quick answer. Maybe there are better ones. www.ddhw.com

fzy

"This strategy need every one to know the value of k."   Only two persons need to know the value of k. The others always get number of the next person. It takes 2k - 2 rounds to finish.   Another way is every body remembers his initial number. And at round i he needs to do some calculation so his number is the average of the i+1 people starting from him. This way after k-1 rounds every body have the average. this is the quickest. www.ddhw.com

avanade

Every one remembers his origianal number. At round number i, everybody changes his number to      (his origianal number)/(i+1) + (the number next to him)*i/(i+1).www.ddhw.com   www.ddhw.com