我很小就从某科普读物得知，让大猩猩在钢琴上蹦11亿年，也会演奏出一首贝多芬的第五交响乐。当然，你无法预测11亿年中哪个时刻，大猩猩会有此壮举。以后上了大学对此事有了较清楚的概念。首先，计算需要一些简化的假定，比如猩猩蹦跳的频率，还需假定蹦跳是匀速的，所以要对大师的第五交响乐作些假定，什么余音绕梁之类，想都不要想。最重要的是，这是统计意义上的，不是说一定会出现。应用通常采取的95%置信区间（Confidence Level），就是说成千上万只的大猩猩在钢琴上乱蹦，经过11亿年，95%的猩猩会在无法预知的时间，至少演奏过一次第五交响乐。然而，直至拿到博士学位，对这经过简化的计算过程，还是一点概念都没有。 有一次，一位大学同学（同系同年级，开车不到10分钟！）问我一个问题，是她女儿的回家作业。在0-99这100个数中，多少不含数字1。她当然做出来了，但总觉得有更好的方法。而且当数字变大，她的死算方法马上就不能用了。这是我的专业，自然是小菜一碟。一般的方法是“Inclusion-Exclusion”原理，或译成“容斥原理”。设有N个元素，符合条件a的有N(a)个，符合条件b的有N(b)个，符合条件(a,b)的有N(a,b)个，问不符合条件a,b,c,... 的元素有多少。答案是 N(0) - {N(a) + N(b) + ...} + {N(a,b) + N(a,c) + ...} - {N(a,b,c) + ...} + N(0)是不加限制的选择数。其意义是先减去我们不要的符合条件的选择。因为减的太多，所以补上。第二次又补的太多，然后再减，直至正好。 现考虑我同学的问题，不妨假定是0-9,999。有4个条件abcd，各代表某一位有数字1。 N(0) = 10,000 N(a) = N(b) = N(c) = N(d) = 1,000 N(a,b) = N(a,c) = ... = 100 （共6项） N(a,b,c) = N(a,b,d) = ... = 10 （共4项） N(a,b,c,d) = 1 所以最终答案是 10,000 - 4,000 + 600 - 40 + 1 = 6,561 就是说先从一万种减去至少含一个1的数，正好含1，2，3，4个1的数分别被扣、减了1，2，3，4次。现在把至少含两个1的加回去，正好含2，3，4个1的被加了1，3，6次。再减去至少含三个1的，正好含3，4个1的被减了1，4次。三次操作一起考虑，正好含1，2，3个1的恰好被减了各一次。含四个1的被减了4-6+4=2次，加上N(a,b,c,d) = 1，也是只减一次。 答案用电邮送出后，我觉得这些数字之间是有联系的。用C (m,n)代表m中取n的组合数，最后答案可以写成 C (4,0)104 - C (4,1)103 + C (4,2)102 - C (4,3)10 + C (4,4) = 6,561 将上式与二项式展开(a + b)4相比较，我们发现a = 10, b = -1, 答案6,561就是9的四次方，这才是真正的答案。我原来的方法比死算当然要好多了，而且有通用性。尽管对大数也很不便，但至少可写程序用电脑轻松求解。很显然，对这个问题来说，那把通用性极大的牛刀确实是重了些。但在考试中，寻找“鸡刀”所用的时间很可能比用牛刀杀鸡的时间还要长。大多数情况下，你开始并不知道这到底是“鸡”还是“牛”。拿这把战无不胜的牛刀，毕竟保证了任务总是能完成的。 看到这个94，我终于明白这个9和4分别是怎么来的。每一位数不能含1，所以可以放其余9个数字中任何一个，共9种放法。一共4位数，就是94。我用容斥原理来解，用上海说，似乎是“港督”了（即傻瓜）。然而，这鸡刀尽管人人都懂，但要在很短时间内马上找到，就要有相当的功力了。黑体辐射现象，人们研究了好几十年，也就找到了长波极限Rayleigh-Jeans公式和短波极限Wien公式，还有博士生的博士论文是用数值方法把这两个公式拟合起来，最后当普朗克（Planck）发现了黑体辐射公式 I = a / (eb/T - 1)，这些前辈们真是可以吐血了。然而，没人会说前辈们的工作是“港督”。正是他们的工作给了普朗克启发，从而一举成功。在现在这个问题，前辈和晚辈都是我自己，港督或聪明人也就无所谓了。事实上，这个最后答案还可以用更简单的方法加以理解。我们问0-9,999中有几个数不含9，这和不含1当然是一样的。这就是说9进制的四位数共有多少值。10进制的四位数有104，2进制的四位数有24，9进制的四位数当然是94了。 现在回到大猩猩演奏贝多芬的问题。我们不妨研究蹦了11亿年不出现第五交响乐的几率，就是N（N为天文数字）位数不含某特定数串的组合数有多少。运用容斥原理，先把总数减去出现至少一次第五交响乐的组合数，再加上出现至少两次的，直至这N位数再也装不下第五交响乐了。那个吃饱没事干的数学家大概证明了，大猩猩蹦了11亿年后，95%的大猩猩至少“演奏”了一次第五交响乐。现在假定我们有个10位数，空缺用0填上（Leading 0），而“第五交响乐”只有三个“音符”123，大猩猩蹦了10次后，0.7985%的大猩猩会演奏出至少一次123。多大的N可保证95%的大猩猩演奏123，我想是没有“鸡刀”的，有兴趣的读者可借助电脑进行计算。 |
