一道概率競賽題中的斐波那契數(shù)

今天講解一道美國數(shù)學(xué)邀請賽（AIME）的題目：一枚均勻的硬幣拋擲10次，從不接連出現(xiàn)正面的概率為i / j（既約分?jǐn)?shù)），求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題），屬于中等難度的題目。不過這差不多是三十年前的難度了，近十年的難度已經(jīng)遠(yuǎn)遠(yuǎn)高于那個時候。不過我很喜歡美國數(shù)學(xué)邀請賽的題目，有趣味性，也有思想性。下面我用兩個不同的角度來解釋一下思考過程。

解法一：按照我們熟悉的鴿巢原理（Pigeonhole Principle），出現(xiàn)反面（T）的次數(shù)至少要有5次，因為5次反面會構(gòu)造出6個空位用來分隔另外5次正面（H），否則必然會出現(xiàn)連續(xù)兩次正面的情況。

明白了這一點(diǎn)，我們只需要分類討論就可以。

1、正面出現(xiàn)0次的情況：C（10,0）＝1；

2、正面出現(xiàn)1次的情況：C（10,1）＝10；

3、正面出現(xiàn)2次的情況：C（9,2）＝36；

4、正面出現(xiàn)3次的情況：C（8,3）＝56；

5、正面出現(xiàn)4次的情況：C（7,4）＝35；

6、正面出現(xiàn)5次的情況：C（6,5）＝6。

因此，符合題意的全部情況數(shù)等于1＋10＋36＋56＋35＋6＝144種。因為連續(xù)拋擲10次的全部可能性為210，于是，i / j＝144/1024＝9/64。綜上，i＋j＝9＋64＝73。

解法二：假設(shè)一枚均勻的硬幣拋擲n次，從不接連出現(xiàn)正面的情況為Sn。我們發(fā)現(xiàn)：S1＝2；S2＝3；S3＝5；S4＝8；……。這貌似就是我們所熟悉斐波那契數(shù)列（Fibonacci sequence）啊！如果真的是斐波那契數(shù)列，這個問題的計算量將大大減小，而且會讓這個特殊的問題得到一般化的結(jié)論。因為無論拋擲多少次，我們都可以很快地推出答案。這個一般化的結(jié)論要比這道題的答案本身有意義很多！接下來我們就要證明我們的猜想是正確的。要證明這個猜想，我們先要思考斐波那契數(shù)列本身的構(gòu)造，它是從第3個數(shù)字開始都是前2個數(shù)字之和。那么我們可以這么思考：假如第一次我們拋擲的是正面（H），那么勢必第二次要出現(xiàn)反面才能符合題意，于是這個數(shù)量其實就是Sn-2時的情況；假如第一次我們拋擲的是反面（T），那么第二次無所謂是正面還是反面了，于是問題就變?yōu)镾n-1時的情況。兩者相加，就是Sn。這樣我們就證明了我們的猜想Sn＝Sn-2＋Sn-1。這就是斐波那契數(shù)列的構(gòu)造。于是，我們很方便就得到了S10＝144。

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