小朋友分果子的难题

yang_bigarm

幼儿园里，一群小朋友们围一张桌子坐成一圈，老师给他们手里每人一些果子，可是老师发现果子分得
不均匀，大家手里的果子都不一样，但是大家手里的果子都是偶数个。现在老师一声令下，每个小朋友
把他手里的果子分一半给右手边的人，这样一轮下来，每个人手里的果子数都有了变化。老师发现有的
人手里的果子数变成了奇数，于是就再给他一个果子。然后再玩下一轮游戏。。。。

问题1：证明在若干轮之后，大家手里的果子数量都相同。

例如：有7个小朋友，他们手里的果子数分别是
10，8，4，10，12，4，10
每个人分了一半给右边的人之后
10 9 6 7 11 8 7
给奇数的手里增加一个
10 10 6 8 12 8 8
玩下一轮。。。。

问题2：老师这次还是玩同样的游戏，但是给的不是果子，而是牛奶，
这个时候，因为每次都可以拿出一半牛奶分给右边的人，所以老师不
必每轮之后给大家添加牛奶。但是同样可以证明最终大家碗里的牛奶
都会一样多。

lulijie

假设一共有n个小朋友，每个人杯子中的牛奶的初始体积为 a(0)、a(1)、a(2)、......a(n-1)
m轮以后i号小朋友的牛奶体积为 f(m,i)            i 从0记到n-1
那么 f(m,i)=1/2^m * ∑ C(m,k)*a( i-k mod n)     k从0记到m
                比如 n=7，那么第5轮后，  3号小朋友手中的牛奶体积为  
                 1/2^5 *(  C(5,0)*a(3)+C(5,1)*a(2)+C(5,2)*a(1)+C(5,3)*a(0)+C(5,4)*a(6)+C(5,5)*a(5) )
                 =( a(3)+5a(2)+10a(1)+10a(0)+5a(6)+a(5) ) / 2^5

但m很大时，f(m,i)= 1/2^m *  ∑  g(k)*a(k)       k从0记到n-1
              其中g(k)=∑ C(m,i-k+j*n)        对所有可能的j 求和
                  比如 n=7，那么第21轮后，  3号小朋友手中的牛奶体积为  
                  1/2^21 *  {   (  C(21,0)+C(21,7)+C(21,14)+C(21,21) )*a(3)
                                   +(    C(21,1)+C(21,8)+C(21,15)     )        *a(2)
                                   +(   C(21,2)+C(21,9)+C(21,16)     )         *a(1)
                                   +(   C(21,3)+C(21,10)+C(21,17)   )         *a(0)
                                   +(   C(21,4)+C(21,11)+C(21,18)   )         *a(6)
                                   +(   C(21,5)+C(21,12)+C(21,19)   )         *a(5)
                                   +(   C(216)+C(21,13)+C(21,20)   )          *a(4)     }
-------------------------------------
也就是对任何一轮（第m轮），每个小朋友手中牛奶的体积都等于所有小朋友初始体积的调和平均值
      每个调和系数都是  1/2^m *  ∑ C(m,i+j*n)     的形式 ，只是不同的项i值不同而已，相同的i值在不同号的小朋友在公式中的位置不同。
      所有调和系数的和等于1。
               比如4个小朋友，第3轮
                     f(3,0)= C(3,0)/8*a(0) + C(3,3) /8* a(1) + C(3,2)/8*a(2) + C(3,1)/8*a(3)
                     f(3,1)= C(3,1)/8*a(0) + C(3,0)/8 * a(1) + C(3,3)/8*a(2) + C(3,2)/8*a(3)
                    f(3,2)= C(3,2)/8*a(0) + C(3,1) /8* a(1) + C(3,0)/8*a(2) + C(3,3)/8*a(3)
                    f(3,3)= C(3,3)/8*a(0) + C(3,2)/8 * a(1) + C(3,1)/8*a(2) + C(3,0)/8*a(3)
                        若是第二或第一轮，则有些初始值的调和系数为0。
----------------------------------------
可以证明当m趋向无穷大时，每项调和系数  1/2^m *  ∑ C(m,i+j*n)         （对所有可能的j值求和）
       不管i为多少， 调和系数的极限都相等，都等于  1/n 。
也就是说m趋向无穷大的时，任何一个小朋友手中的牛奶的体积都等于
                1/n*a(0)+1/n*a(1)+1/n*a(2)+......+1/n*a(n-1)
              =1/n(a(0)+a(1)+a(2)+......+a(n-1))

[ 本帖最后由 lulijie 于 2009-8-12 21:14 编辑 ]

lulijie

想当然了，问题2确实不那么简单。
尽管每次变换后，最大值至少减少1个，最小值至少减少1个，不断进行下去，最大值不断减小，最小值不断增大，两者的差值不断缩小，但是无限进行下去，这个差值的极限是不是0，还有待证明。

yang_bigarm

good！lulijie对问题1的解答正确。

原帖由 lulijie 于 2009-8-8 20:18 发表
问题2比问题1更简单。

问题2未必简单吧，注意不一定是有限次就能让所有人碗里的牛奶一样多的呀。

yang_bigarm

good！ lulijie 问题1解答正确！

原帖由 lulijie 于 2009-8-8 20:18 发表
问题2比问题1更简单。

问题2恐怕未必简单吧！注意问题2可不一定是有限次分就能让大家碗里的牛奶一样多的哦。

lulijie

问题2比问题1更简单。

lulijie

假设这一圈小朋友手中糖果（已经加到都是偶数）最多为a，最少为b，
那么经过变换后，最大值不会超过a，那么下一轮经过变偶后，仍然不会超过a。
假设所有的小朋友糖果数不全相等，那么一定能找到一个小朋友，他的糖果数是b（最少）且他的右边或左边小朋友的糖果数比他多，那么经过变化后，糖果数是b的小朋友数目至少减少1个。
而 变偶操作后糖果数是b的小朋友不会增加。
所以经过一次给半和变偶操作后，最大的数不会变大，而最小的数至少减少1个，这样不断进行下去，最小的数b没有的，最小的数变成b+2,不断进行下去，最小值不断增大，最大值不变或减小，最终达到大家都相等为止。

mofangPYH

谁知道答案？~~~~~~~~~~~~~~~~~~~~~~~~

342023003

O(∩_∩)O哈哈~