做一回事后诸葛亮 |
送交者: 零加一中 2011年09月26日21:43:56 于 [灵机一动] 发送悄悄话 |
我很小就从某科普读物得知,让大猩猩在钢琴上蹦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,我想是没有“鸡刀”的,有兴趣的读者可借助电脑进行计算。 |
|
|
|
![]() |
![]() |
实用资讯 | |
|
|
一周点击热帖 | 更多>> |
|
|
一周回复热帖 |
|
|
历史上的今天:回复热帖 |
2009: | 尺规作图题 | |
2009: | 从“亚他拿修”来看“基督的人性”的定 | |
2008: | 人在行走时所用的能量来源 | |
2006: | 引起法律纠纷的字条. | |