2016年8月12日 星期五

台中區國立高級中學103學年度大學入學第一次學科能力測驗聯合模擬考,選填2

=題目=


紅綠建設公司在台中打算建造10層樓高的總部大樓,為了凸顯公司特色,決定每層樓只能用紅色或綠色的油漆來粉刷,而且不能有連續兩層是紅色的,則他們有幾種可能的粉刷方式?

=解答=

俞克斌先生的解法是插空隙,請參考http://web.tcfsh.tc.edu.tw/jflai/rab/RA367ans.swf

事實上本題可以考慮遞迴解法。

定義全部n層樓時,塗法為$a_n$種。

先對幾個比較小的n值來計算。

$n=1$時,因為可以塗紅色或綠色,所以$a_1=2$。

$n=2$時,從一樓開始記起,合乎條件的塗色方式有:「綠綠」(1樓為綠色、2樓為綠色)、「綠紅」(1樓為綠色、2樓為紅色)、「紅綠」(1樓為紅色、2樓為綠色)。所以$a_2=3$。

$n=3$時,合乎條件的塗色方式有:

$(1^{\circ})$ 3綠:「綠綠綠」

$(2^{\circ})$2綠1紅:「綠綠紅」、「綠紅綠」、「紅綠綠」

$(3^{\circ})$1綠2紅:「紅綠紅」

所以$a_3=5$。

彙整以上結果有:$a_1=2, a_2=3, a_3=5$。可以猜測$a_n=a_{n-1}+a_{n-2}, n \geq 3$。

事實上,當全部樓層為n層時(n當然要足夠大,總不會對很小的n來討論),最後一層,也就是第n層,其顏色只有2種可能,綠色或是紅色。

若是第n層為綠色,那麼向前推,第$n-1$層會是什麼顏色呢?其實紅跟綠都可以的。換句話說,如果確定第n層為綠色,那麼只需考慮前面全部$n-1$層的塗法,因此這時的塗法數為$a_{n-1}$。

若是第n層為紅色,那麼根據題目條件「不能有連續兩層是紅色的」,可以推知第$n-1$層必定是綠色。再繼續向前推,類似於方才的討論,只需考慮前面全部$n-2$層的塗法,因此這時的塗法數為$a_{n-2}$。

我們將全部n層時的塗法分為兩大類,一類是「第n層樓為綠色」,此時塗法數為$a_{n-1}$;另一類是「第n層樓為綠色」,此時塗法數為$a_{n-2}$。所以得到

$\left \{ \begin{array}{l} a_1=2, a_2=3, \\ a_n=a_{n-1}+a_{n-2}, n \geq 3.\end{array} \right.$

這是Fibonacci數列。題目所求的$a_{10}$,基本上可以直接用手算,列表如下:
2, 3, 5, 8, 13, 21, 34, 55, 89, 144

故所求$a_{10}=144$。

當然,利用Fibonacci數列的一般項公式,可以輕易算出任何n值時的$a_n$,我個人偏好的生成函數解法,請參考https://ccjou.wordpress.com/2013/10/23/%E9%81%9E%E8%BF%B4%E9%97%9C%E4%BF%82%E5%BC%8F%E7%9A%84%E6%AF%8D%E5%87%BD%E6%95%B8%E8%A7%A3%E6%B3%95/的例三。

沒有留言:

張貼留言