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

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

这道题是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次的全部可能性为2¹⁰，于是，i / j＝144/1024＝9/64。综上，i＋j＝9＋64＝73。

解法二：假设一枚均匀的硬币抛掷n次，从不接连出现正面的情况为S_n。我们发现：S₁＝2；S₂＝3；S₃＝5；S₄＝8；……。这貌似就是我们所熟悉斐波那契数列（Fibonacci sequence）啊！如果真的是斐波那契数列，这个问题的计算量将大大减小，而且会让这个特殊的问题得到一般化的结论。因为无论抛掷多少次，我们都可以很快地推出答案。这个一般化的结论要比这道题的答案本身有意义很多！

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

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

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

这样我们就证明了我们的猜想S_n＝S_n-2＋S_n-1。这就是斐波那契数列的构造。于是，我们很方便就得到了S₁₀＝144。

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