抛硬币概率问题,一道竞赛题中的斐波那契数列

橘子网 3,953 0

今天讲解一道美国数学邀请赛(AIME)的题目:一枚均匀的硬币抛掷10次,从不接连出现正面的概率为j(既约分数),求ij。(原题:A fair coin is to be tossed 10 times. Let /j, in lowest terms, be the probability that heads never occur on consecutive tosses. Find ij.)

抛硬币概率问题,一道竞赛题中的斐波那契数列

这道题是1990年的第9题(一共15题),属于中等难度的题目。不过这差不多是三十年前的难度了,近十年的难度已经远远高于那个时候。不过我很喜欢美国数学邀请赛的题目,有趣味性,也有思想性。下面我用两个不同的角度来解释一下思考过程。

解法一:按照我们熟悉的鸽巢原理(Pigeonhole Principle),出现反面(T)的次数至少要有5次,因为5次反面会构造出6个空位用来分隔另外5次正面(H),否则必然会出现连续两次正面的情况。抛硬币概率问题,一道竞赛题中的斐波那契数列

明白了这一点,我们只需要分类讨论就可以。

1、正面出现0次的情况:C(10,0)=1;

2、正面出现1次的情况:C(10,1)=10;

3、正面出现2次的情况:C(9,2)=36;

4、正面出现3次的情况:C(8,3)=56;

5、正面出现4次的情况:C(7,4)=35;

6、正面出现5次的情况:C(6,5)=6。

因此,符合题意的全部情况数等于1+10+36+56+35+6=144种。因为连续抛掷10次的全部可能性为210,于是,j=144/1024=9/64。综上,ij=9+64=73。

解法二:假设一枚均匀的硬币抛掷n次,从不接连出现正面的情况为Sn。我们发现:S1=2;S2=3;S3=5;S4=8;……。这貌似就是我们所熟悉斐波那契数列(Fibonacci sequence)啊!如果真的是斐波那契数列,这个问题的计算量将大大减小,而且会让这个特殊的问题得到一般化的结论。因为无论抛掷多少次,我们都可以很快地推出答案。这个一般化的结论要比这道题的答案本身有意义很多!

接下来我们就要证明我们的猜想是正确的。

要证明这个猜想,我们先要思考斐波那契数列本身的构造,它是从第3个数字开始都是前2个数字之和。

那么我们可以这么思考:假如第一次我们抛掷的是正面(H),那么势必第二次要出现反面才能符合题意,于是这个数量其实就是Sn-2时的情况;假如第一次我们抛掷的是反面(T),那么第二次无所谓是正面还是反面了,于是问题就变为Sn-1时的情况。两者相加,就是Sn

这样我们就证明了我们的猜想Sn=Sn-2+Sn-1。这就是斐波那契数列的构造。于是,我们很方便就得到了S10=144。

小结:解法二的优势在于突破了这个题目的答案本身,让我们看到了问题最核心的本质,更加具有一般性。这也是为什么每次解完题后,我都会要求孩子们思考一下题目条件改变后,如何得到一般化的结果。也只有这样,才能做到举一反三和触类旁通,以不变应万变。

上一篇:

下一篇:

相关阅读

分享