【AMC12題選】計數問題中的斐波那契數列

有計劃參加今年的AMC12的學生，從(cong) 暑假開始就必須開始做備賽規劃了。我近期將挑選幾道AMC12真題做一些分析和點評，希望能對大家有所啟發和思考。

今天選擇的是一道計數問題。題目如下：

10個(ge) 女人分別坐在排成一行的10張椅子上。在某個(ge) 時間，她們(men) 同時站起來並重新選擇座位。重新就座後她們(men) 仍然每個(ge) 人坐一張椅子，並且每個(ge) 人隻能選擇原來的椅子或與(yu) 原來的椅子相鄰的椅子就座。請問，她們(men) 一共有多少種不同的座位調整方式？

對於(yu) 計數問題，我的個(ge) 人心得是：幾乎所有的計數問題都要分類計數。隻要根據題目的條件設置找到合適的分類方式，就已經成功了一半。

尋找合適的分類方式的過程，非常考驗我們(men) 對題目條件的理解和分析能力。有時候因為(wei) 分析不夠透徹，沒有找到最佳的分類方法，因而導致解答過程冗長且複雜，很容易造成錯誤。

計數問題因其對背景知識要求少，便於(yu) 考察學生的分析推理能力，而成為(wei) 美、英、澳、加等國的數學競賽中很受重視的一個(ge) 題型，並且是貫穿從(cong) 小學到高中的各個(ge) 階段。

對計數問題構造分類有兩(liang) 種不同的模式。

第一種模式，也是大多數情況下采取的模式，是選擇其中一個(ge) 要素進行分類。情況較複雜時，還需要嵌套分類，即在某些類別下再進一步分類。

第二種模式是遞歸分類，即分類後其中部分類別或所有類別都是同類問題的計數。這種分類模式的一個(ge) 典型例子是《計數問題中的分類和遞歸方法》一文中的題目。本文中的題目則是另一個(ge) 有趣的例子。

根據題意，每個(ge) 女人在重新選擇座位時，可以選擇保持不動或換到相鄰的椅子。也就是說，每個(ge) 人都有三個(ge) 選擇——除了原來坐在兩(liang) 端的那兩(liang) 個(ge) 女人，她們(men) 都隻有兩(liang) 個(ge) 選擇。

盡管單獨看每個(ge) 女人，她要麽(me) 有三個(ge) 選擇，要麽(me) 有兩(liang) 個(ge) 選擇，但每個(ge) 人的選擇同時也會(hui) 影響（更確切地說是限製）其他幾個(ge) 女人的選擇，並且這種影響關(guan) 係會(hui) 傳(chuan) 遞下去。

為(wei) 了構造分類，我們(men) 可以選擇其中一個(ge) 女人的位置選擇作為(wei) 分類依據。這樣分類的好處是，在每個(ge) 類別下，我們(men) 都隻需考慮最多9個(ge) 女人的位置選擇。人數的減少意味著問題的簡化。

應該選擇哪個(ge) 女人來分類呢？答案是——選擇初始位置在兩(liang) 端的女人比中間的女人更好，因為(wei) 前者隻有一個(ge) 方向需要關(guan) 注。

從(cong) 其中一端開始，按照座位順序把10個(ge) 女人依次編號為(wei) 1~10，她們(men) 原本坐的椅子也相應編號為(wei) 1~10。1號女人在重新選擇座位時隻有兩(liang) 個(ge) 可能性。

1. 選擇1號椅子。此時，2~10號女人隻能各自在2~10號椅子中選擇一個(ge) 。

2. 選擇2號椅子。此時我們(men) 來考慮2號女人。由於(yu) 2號椅子已經被1號女人占了，所以她隻能選擇1號椅子或3號椅子。然而，假如她選擇了3號椅子，其他女人（3~10號）都不可能選擇1號椅子。也就是說，1號椅子隻能空著。這不符合題目的要求。

根據以上分析，當1號女人選擇2號椅子時，2號女人隻能選擇1號椅子才能保證換位後每個(ge) 人仍然能坐一把椅子。與(yu) 此同時，3~10號女人各自在3~10號椅子中選擇一把椅子。

滿足題目要求的任意一種換位方式，要麽(me) 屬於(yu) 第一類（1號女人選1號椅子），要麽(me) 屬於(yu) 第二類（1，2號女人互換座位）。

題目是針對10個(ge) 女人（在規定的換位規則下）求換位方式的數量。事實上，對任意多個(ge) 女人，我們(men) 都可以問同樣的問題。記n個(ge) 女人的換位方式數量為(wei) A_n。則第一類中的換位方式數量恰好是A₉，因為(wei) 9個(ge) 女人（2~10號）要在她們(men) 坐的9把椅子裏各自選擇一把椅子。類似可知，第二類中的換位方式數量恰好是A₈，因為(wei) 8個(ge) 女人（3~10號）需要各自在8把椅子（3~10號）中選擇一把。

綜上所述，我們(men) 得到了一個(ge) 重要的等式關(guan) 係：

A₁₀=A₉+A₈.

不難發現，這個(ge) 等式可以一般地推廣到n（隻需把上麵的分析方法應用到n個(ge) 女人的情形），即

A_n=A_n-1+A_n-2.

最後，容易求出A₁=1，A₂=2。也就是說，{A_n}恰好就是斐波那契數列。於(yu) 是，本題的答案就是斐波那契數列的第10項的值。

數學題都是編出來的，而編題的水平各有高低。一道題可以從(cong) 幾個(ge) 不同的角度進行評價(jia) ，例如所考察的思維能力及深度（並不是越深越好）、趣味性、啟發性，等等。這道題的妙處在於(yu) 把斐波那契數列和一個(ge) 具體(ti) 問題聯係起來，相當有趣，同時考察了分類計數的分析能力。

斐波那契數列通常在小學高年級作為(wei) 課外知識引入。而在中學的數列學習(xi) 中，斐波那契數列又是一個(ge) 重要的例子。到了AMC12，一道與(yu) 斐波那契數列有關(guan) 的題目可以被列為(wei) 第21題（AMC12的最後5道題通常是難度較大的題目）。由此，我們(men) 可以看到一個(ge) 數學概念不僅(jin) 僅(jin) 是“知識點”，而是有不同層次的理解和分析思考。

暑假是開始備戰AMC12的重要時段。因此，歐拉數學苑將在暑假期間安排一對一和小班的AMC12輔導課程。

其中，小班課程為(wei) 3~4人規模，主要針對已經有參加AMC10的經驗且AMC10的自測水平達到85分（考試成績可以降低到75分）的學生，備考目標為(wei) AMC12的分數達到105~120的區間。

如果備考目標是120分以上，建議參加一對一的輔導課程。