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

今天講解一道美國(guó)數(shù)學(xué)邀請(qǐng)賽（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題），屬于中等難度的題目。不過(guò)這差不多是三十年前的難度了，近十年的難度已經(jīng)遠(yuǎn)遠(yuǎn)高于那個(gè)時(shí)候。不過(guò)我很喜歡美國(guó)數(shù)學(xué)邀請(qǐng)賽的題目，有趣味性，也有思想性。下面我用兩個(gè)不同的角度來(lái)解釋一下思考過(guò)程。

解法一：按照我們熟悉的鴿巢原理（Pigeonhole Principle），出現(xiàn)反面（T）的次數(shù)至少要有5次，因?yàn)?次反面會(huì)構(gòu)造出6個(gè)空位用來(lái)分隔另外5次正面（H），否則必然會(huì)出現(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種。因?yàn)檫B續(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ù)列，這個(gè)問(wèn)題的計(jì)算量將大大減小，而且會(huì)讓這個(gè)特殊的問(wèn)題得到一般化的結(jié)論。因?yàn)闊o(wú)論拋擲多少次，我們都可以很快地推出答案。這個(gè)一般化的結(jié)論要比這道題的答案本身有意義很多！接下來(lái)我們就要證明我們的猜想是正確的。要證明這個(gè)猜想，我們先要思考斐波那契數(shù)列本身的構(gòu)造，它是從第3個(gè)數(shù)字開(kāi)始都是前2個(gè)數(shù)字之和。那么我們可以這么思考：假如第一次我們拋擲的是正面（H），那么勢(shì)必第二次要出現(xiàn)反面才能符合題意，于是這個(gè)數(shù)量其實(shí)就是Sn-2時(shí)的情況；假如第一次我們拋擲的是反面（T），那么第二次無(wú)所謂是正面還是反面了，于是問(wèn)題就變?yōu)镾n-1時(shí)的情況。兩者相加，就是Sn。這樣我們就證明了我們的猜想Sn＝Sn-2＋Sn-1。這就是斐波那契數(shù)列的構(gòu)造。于是，我們很方便就得到了S10＝144。

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