趣题：所有人手上的糖数最终会变得一样多

n 个小朋友在圆桌上坐成一圈。初始时，每个小朋友都拥有一定数量的糖。接下来，反复进行下面两个操作：

1. 如果有人手里的糖数是奇数，就向老师再要一颗糖，把手里的糖数补成偶数；
2. 每个人都把自己手中一半的糖传给他右边的人（同时接到从左边传过来的糖）。

证明：总有一个时刻，所有小朋友手中都会拥有相同数量的糖。
附加题：这是一个非常经典的问题。猜猜看我最早在什么地方看到的这个问题？

我很小很小的时候，就在《十万个为什么》的数学分册 1 上读到了这个问题。在我看过的所有书里，这本书恐怕是历史最悠久，被我翻得最烂，对我意义最大的书了。我甚至还记得书里那篇文章的标题——《怎样调整，使大家的糖一样多》。不过，让人哭笑不得的是，文章中用大量篇幅演示了结论的意思，最终却并没有给出一个证明。于是，究竟该怎样证明这个结论，便成了一桩“悬案”。今天在这里看到这个问题的证明时，实在是有些激动，毫不犹豫地把它记了下来。

在第一次传糖之前，每个人手里的糖数都会被补成偶数。因此，我们可以直接假设初始时所有人手里的糖数都是偶数。把所有人手中的糖数的最大值记作 M 。下面，让我们考虑任意一个小朋友，假设他手中的糖数为 a ，他左边的人手中的糖数为 a’ 。第一次传糖之后，这个人手里的糖数就变成了 (a + a’) / 2 。由于 a 和 a’ 都不超过 M ，因而要么 (a + a’) / 2 正好等于 M （但由于 M 是偶数，因此他不能再向老师要糖了），要么 (a + a’) / 2 将会严格小于 M （即使之后再向老师要一颗糖，最多也只能刚好达到 M ）。因此，在第二次传糖之前，每个人手中的糖数仍然都不超过 M 。由此可见，不断继续下去，今后任何人在任何时刻手中的糖数都不会超过 M 。

这表明，所有人的糖数之和有一个上限。因此，小朋友们手中的总糖数不会无限制地增加，总有一个时候，所有人都不再得到新的糖了，整个过程只剩下 n 个数值间简单的迭代。接下来，神奇的一步出现了。让我们考虑在此之后，每一次传糖将导致所有人的糖数的平方和会如何变化：

这说明，如果小朋友们手上的糖数不全相等的话，糖数的平方和将会严格地减少。但是，这个平方和显然不会无限地减少，总会有一个时候，平方和不再变化。此时，小朋友们手上的糖数就都相等了。



32 条评论

ernest
sf

2011年11月15日 23:51 / 回复
ernest
其实每个人的数量会变成相邻两个的平均，这个应该是切入点

2011年11月15日 23:53 / 回复
osirpt
余以为用二进制考虑这个问题应该会比较简单。

2011年11月16日 12:58 / 回复
挽魇
这个小时候也看到过，好像是《神奇的数学》或者什么，忘了……当时好像是用作差搞定的

2011年11月16日 13:05 / 回复
Star
为什么平方和的差会趋于零啊

2011年11月16日 14:17 / 回复
windmeup
我怎么觉得”今后任何人在任何时刻手中的糖数都不会超过 M “这个就说明了最后每个人的手里都会有m颗糖啊.后面的证明似乎没必要了.

2011年11月16日 16:35 / 回复
hanyuwei70
我怎么没有看到……..
我印象最深的是数学分册上的鹦鹉螺，生物分册上的某生物（防HX），工程科学上的卡车…

2011年11月16日 18:44 / 回复
loveit
恩的确很经典楼主的博客最近才开始关注不过真的很喜欢

2011年11月16日 20:03 / 回复
liu
哦，证明的真棒

2011年11月17日 11:48 / 回复
liu
证明的很好

2011年11月17日 11:50 / 回复
dersonlwd
@地基：交换后M可能变小了

2011年11月17日 11:51 / 回复
正和
不失一般性，令一开始所有人都有偶数块糖，最多的一个人为m块，显然，交换一次后，该人的糖不会增加。证略。
设最少的人A为n块，不失一般性，令其左边的人B为p>n块，显然，交换一次后A、B均多于n块。
可见，最大值单调不增，最小值单调增加或并列最小值的个数单调减少，因此某个时候最小值必定会等于最大值，即所有人手中糖数相等。

2011年11月18日 00:06 / 回复
yangff
十万个为什么碉堡了！

2011年11月18日 18:43 / 回复
彩虹之子
这种题目都是整体考虑啊

2011年11月19日 15:47 / 回复
myxiaoniao
哈哈，这种证明方法是很多中学数学竞赛喜欢用的压轴题哦
构造一个整数域上的函数，这个函数是非负的，每次操作都会减小这个函数，结果就是拉哦

2011年11月19日 18:41 / 回复
正月点灯笼
刚刚写了个程序模拟一下，挺好玩的。
我测试了当n=1000的情况，1000个小朋友手上的糖的数量是随机的，最后，也可以玩出来。

2011年11月24日 07:46 / 回复
Tough Guy
我来提供一种更直观的证明方法：

假设有 n 个小朋友，糖数最多的是 Ma, 最少的是 Mi；
直接假设初始时所有人手里的糖数都是偶数；

把这个传递糖和补充糖的循环过程看成是一个系统。
实际上可以把这个系统不断地分解：

初始系统为：
X1 -> X2 -> X3 ->……Xn-1 -> Xn -> X1

第一次分解：
NO.1 NO.2 …… NO.n NO.1
——————————————————-
1. (X1-Mi) -> (X2-Mi) ->…… -> (Xn-Mi) ->(X1-Mi)

2. Mi -> Mi ->…… -> Mi -> Mi

经过一次分解，可以看出第2个系统是封闭的（即系统中所有的糖数都是相同的）（Mi为偶数）；
我们只需要考虑第1个系统就行了，第1个系统经过几次传递和补糖，又会分解，每一次分解，系统中最大的塘数一定会减少。
所以最终会分解出来的系统会是
0 -> 0 -> …… -> 0 -> 0

2011年12月1日 09:17 / 回复
Tough Guy
我来提供一种更直观的证明方法：

假设有 n 个小朋友，糖数最多的是 Ma, 最少的是 Mi；
直接假设初始时所有人手里的糖数都是偶数；

把这个传递糖和补充糖的循环过程看成是一个系统。
实际上可以把这个系统不断地分解：

初始系统为：

NO.1 NO.2 …… NO.n NO.1
——————————————————-
X1 -> X2 -> …… -> Xn -> X1

经过一次分解：
NO.1 NO.2 …… NO.n NO.1
——————————————————-
1. (X1-Mi) -> (X2-Mi) ->…… -> (Xn-Mi) ->(X1-Mi)

2. Mi -> Mi ->…… -> Mi -> Mi

经过一次分解，可以看出第2个系统是封闭的（即系统中所有的糖数都是相同的）（Mi为偶数）；
我们只需要考虑第1个系统就行了，第1个系统经过几次传递和补糖，又会分解，每一次分解，系统中最大的塘数一定会减少。
所以最终会分解出来的系统会是
0 -> 0 -> …… -> 0 -> 0

2011年12月1日 09:23 / 回复
Tough Guy
我来提供一种更直观的证明方法：

假设有 n 个小朋友，糖数最多的是 Ma, 最少的是 Mi；
直接假设初始时所有人手里的糖数都是偶数；

把这个传递糖和补充糖的循环过程看成是一个系统。
实际上可以把这个系统不断地分解：

初始系统为：

NO.1 NO.2 …… NO.n NO.1
——————————————————-
X1 -> X2 -> …… -> Xn -> X1

经过一次分解：
NO.1 NO.2 …… NO.n NO.1
——————————————————-
1. (X1-Mi) -> (X2-Mi) ->…… -> (Xn-Mi) ->(X1-Mi)

2. Mi -> Mi ->…… -> Mi -> Mi

经过一次分解，可以看出第2个系统是封闭的（即系统中所有的糖数都是相同的）（Mi为偶数）；
我们只需要考虑第1个系统就行了，第1个系统经过几次传递和补糖，又会分解，每一次分解，系统中最大的塘数一定会减少。
所以最终会分解出来的系统会是
0 -> 0 -> …… -> 0 -> 0

2011年12月1日 12:56 / 回复
Tough Guy
我来提供一种更直观的证明方法：

假设有 n 个小朋友，糖数最多的是 Ma, 最少的是 Mi；
直接假设初始时所有人手里的糖数都是偶数；

把这个传递糖和补充糖的循环过程看成是一个系统。
实际上可以把这个系统不断地分解：

初始系统为：

NO.1 NO.2 …… NO.n NO.1
——————————————————-
X1 -> X2 -> …… -> Xn -> X1

经过一次分解：
NO.1 NO.2 …… NO.n NO.1
——————————————————-
1. (X1-Mi) -> (X2-Mi) ->…… -> (Xn-Mi) ->(X1-Mi)

2. Mi -> Mi ->…… -> Mi -> Mi

经过一次分解，可以看出第2个系统是封闭的（即系统中所有的糖数都是相同的）（Mi为偶数）；
我们只需要考虑第1个系统就行了，第1个系统经过几次传递和补糖，又会分解，每一次分解，系统中最大的塘数一定会减少。
所以最终的系统会是
0 -> 0 -> …… -> 0 -> 0

2011年12月1日 12:57 / 回复
youtailin
<n块，显然，交换一次后A、B均多于n块。
可见，最大值单调不增，最小值单调增加或并列最小值的个数单调减少，因此某个时候最小值必定会等于最大值，即所有人手中糖数相等。>>

如何证明最大值严格单调不增，最小值严格单调增加？？？

2011年12月1日 13:02 / 回复
learningBoy
我来质疑一下你的证明，虽然结论肯定正确的。
假如3个人，开始糖果分别为2，4,6，第一次传完后，变为4,3,5，平方和从56变为50，但是在向老师补充完糖果后，变为4,4,6，平方和反而增加了，不能说是严格减少。
楼主证明了传完之后的严格减少，但没有发现之后会补充糖果，即第一次结束的值和第二次开始的值根本不一样。

2011年12月8日 21:20 / 回复
- 嘴大吃八方
  请注意原文这句话：“……因此，小朋友们手中的总糖数不会无限制地增加，总有一个时候，所有人都不再得到新的糖了……”。所以平方和严格减少是建立在这个基础上的，没有什么需要质疑的。
  
  2014年10月21日 12:35
幻风
……
ls,“总有一个时候，所有人都不再得到新的糖了，整个过程只剩下 n 个数值间简单的迭代。”

2011年12月9日 14:41 / 回复
skirr
动态回归的影子..

2011年12月13日 11:56 / 回复
过客
交换后的平方和没法表示吧，因为不知道交换后谁有额外加了1

2012年1月4日 16:50 / 回复
傲哥
我写的程序，不会全部人相等，只是总数不增加，假设有6个人

input some numbers

1 2 3 1 50 100

2 2 4 10 50 100
1 3 4 10 50 100
2 2 6 10 50 100
2 2 3 13 50 100
2 2 4 7 57 100
2 2 4 8 29 129
67 2 4 8 30 65
34 36 4 8 30 66
34 18 22 8 30 66
34 18 11 19 30 66
34 18 12 10 40 66
34 18 12 10 20 86
77 18 12 10 20 43
39 57 12 10 20 44
40 29 41 10 20 44
40 30 21 31 20 44
40 30 22 16 36 44
40 30 22 16 18 62
71 30 22 16 18 31
36 66 22 16 18 32
36 33 55 16 18 32
36 34 28 44 18 32
36 34 28 22 40 32
36 34 28 22 20 52
62 34 28 22 20 26
31 65 28 22 20 26
32 33 61 22 20 26
32 34 31 53 20 26
32 34 32 27 47 26
32 34 32 28 24 50
57 34 32 28 24 25
29 63 32 28 24 26
30 32 64 28 24 26
30 32 32 60 24 26
30 32 32 30 54 26
30 32 32 30 27 53
57 32 32 30 28 27
29 61 32 30 28 28
30 31 63 30 28 28
30 32 32 62 28 28
30 32 32 31 59 28
30 32 32 32 30 58
59 32 32 32 30 29
30 62 32 32 30 30
30 31 63 32 30 30
30 32 32 64 30 30
30 32 32 32 62 30
30 32 32 32 31 61
61 32 32 32 32 31
31 63 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
32 32 32 32 32 64
64 32 32 32 32 32
32 64 32 32 32 32
32 32 64 32 32 32
32 32 32 64 32 32
32 32 32 32 64 32
请按任意键继续. . .

2012年1月30日 13:47 / 回复
xs
终于有个能看懂的~

2012年1月30日 20:58 / 回复
台州整形医院
写得不错，很好

2012年3月12日 14:47 / 回复
cervelo
神奇的数字呀。一切都可以用原理来解答

2012年12月13日 10:59 / 回复
水着女
メンズ水着 + m

2013年8月2日 19:20 / 回复
暗夜疾风
初始最大值M与每个人最后拿到一样多的糖果n有什么关系吗

2014年2月7日 10:36 / 回复