台中區國立高級中學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/的例三。