IT技术博客大学习 共学习 共进步
全部 移动开发 后端 数据库 AI 算法 安全 DevOps 前端 设计 开发者

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

Matrix67: My Blog 2011-11-16 23:41:00 累计浏览 1,737 次
本机暂存

     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 个数值间简单的迭代。接下来,神奇的一步出现了。让我们考虑在此之后,每一次传糖将导致所有人的糖数的平方和会如何变化:

    原图已失效

同分类推荐文章

  1. 对基本有序的序列排序算法 (2026-06-11 17:46:49)
  2. Four Levels Of Customer Understanding (2026-05-22 21:00:00)
  3. 除法的意义 (2026-04-12 20:52:17)

查看更多 算法 文章 →

建议继续学习

  1. 为什么算法这么难? (累计阅读 12,397)
  2. 浅谈MySQL索引背后的数据结构及算法 (累计阅读 11,904)
  3. 加州求职记 (累计阅读 11,562)
  4. 谷歌(Google)2011年校园招聘笔试题 (累计阅读 9,574)
  5. 最常被程序员们谎称读过的计算机书籍 (累计阅读 9,156)
  6. 再谈“我是怎么招聘程序员的” (累计阅读 8,792)
  7. 如何在面试中发现优秀程序员 (累计阅读 8,315)
  8. IBM面试记 (累计阅读 7,386)
  9. 数学之美:《社交网络》中Facemash算法分析 (累计阅读 7,146)
  10. 谈谈在校程序员技能培养 (累计阅读 7,115)