关于咖啡豆的数学问题

在Guo Jing的Blog上看到这样一个数学问题

给定一个盛有一些黑色豆子和一些白色豆子的咖啡罐以及一大堆额外的黑色豆子,重复以下过程,直至罐中仅剩一颗豆子为止。

从罐中随机选取两颗豆子,如果颜色相同,就将它们都扔掉并且放入一个额外的黑色豆子,如果颜色不同,就将白色的豆子放回罐中,而将黑色的豆子扔掉。

证明该过程会终止。最后留在罐中的豆子颜色与最初的罐中的白色豆子和黑色豆子的数量有什么数学关系。

CoffeeBean

(via)

用循环的算法写出代码后,他写到

也就是说,无论我们怎么拿豆子,白色的豆子的取出的过程都是,2个,0个,2个,0个也就是说,白色的豆子为偶数个的时候,留下的一定是黑色,而白色豆子为奇数的时候,留下的一定是白色!

道理是对的,但是证明过程似乎有点简略了。

于是我用数学过程推了一遍:

先假设有N个豆子,其中有b(B)个黑色和w(W)个白色的。这里b(B)+w(W)=N,于是:

  • 根据题目要求,每次都是取出两个豆子再放回一个豆子,所以每取一次,N都会减少一个。所以循环终将以还剩一个豆子结束(第一个问题得证),并且操作的总次数是N-1。

然后,取豆子有三种情况:

  • 1 两个黑色,那么结果是-2(B)+1(B)=-1(B),黑豆子减一个
  • 2 两个白色,那么结果是-2(W)+1(B),白豆子少两个,黑豆子加一个
  • 3 一黑一白,那么结果是-1(B)-1(W)+1(W)=-1(B),黑豆子减一个

于是再设这操作N-1次中,遇到第2种情况x次,遇到第1和第3种情况共y次,那么经过N-1次操作后,豆子的情况是:

  • [b(B)+w(W)]-x(B)-y[2(W)-1(B)]=(w-2y)(W)+(b-x+y)(B)=1

这里就清楚了:

  • 如果剩下的一个豆子是黑色,那么w-2y=0,所以w,也就是白色豆子的数量必须是偶数
  • 如果剩下的一个豆子是白色,那么w-2y=1,所以w是奇数。

要严谨的证明这句话:“白色的豆子的取出的过程都是,2个,0个,2个,0个。也就是说,白色的豆子为偶数个的时候,留下的一定是黑色,而白色豆子为奇数的时候,留下的一定是白色!” ,也不容易啊!

另外,根据上面那个式子还能退往后再推很多东西,也能增加条件让题目变复杂,譬如说如果外围的准备发进去的豆子不是无穷多的,等等等等

想学对计算机程序设计相关的数学的东西,在这里推荐两本书:

  • 一个是Concrete Mathematics,很生动很有可读性的书。
  • 一个是The Art of Computer Programming,是一套书,乃经典中的经典
  • 另外,这里这里有不少美国好大学的课程,计算机和数学类的。另外这个网站上还有很多其他科目的课程,是很好的资源。