一道概率競賽題中的斐波那契數

今天講解一道美國數學邀請賽（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次的全部可能性為210，于是，i / j＝144/1024＝9/64。綜上，i＋j＝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。

小結：解法二的優勢在于突破了這個題目的答案本身，讓我們看到了問題最核心的本質，更加具有一般性。這也是為什么每次解完題后，我都會要求孩子們思考一下題目條件改變后，如何得到一般化的結果。也只有這樣，才能做到舉一反三和觸類旁通，以不變應萬變。