美國的數學競賽難不難看看這道題就知道了

今天的題目是排列組合問題，來自美國的一次數學學術活動，解題所用知識不超過小學5年級。

題目（5星難度）：有一個九邊形的各邊長均不相同，用3種不同的顏色，給9條邊染色，要求每條邊只染一種顏色，且相鄰2條邊的顏色不同。有多少種不同的染色方法？

輔導方法：

將題目寫給小朋友，讓他自行思考解答，若20分鐘仍然沒有思路，再由家長進行提示性講解。

講解思路：

這道題屬于排列組合問題，難點在于9條邊圍成了一個圈，自然想到將問題簡化，考慮邊沒有圍成一個圈的情況。

用a(n)表示n邊形染3種顏色的方法數，我們將采用遞推的方法解題

總的解題思路是：先計算9條邊沒有圍成一個圈的情況，然后得到a(9)和a(8)的關系，接著計算a(3)的值，最后通過遞推得到a(9)的值。

步驟1：先思考第一個問題，如果只有相連的9條邊且沒有圍成一個圈，要求相鄰2條邊顏色不同，在3種不同的顏色下有多少種染色方法？

這個問題比較簡單，從左到右逐漸染色即可，第一條邊有3種選擇，第二條邊只有2種選擇，此后所有邊都只有2種選擇，因此不同的染色方法數是3*2*2*…*2=768種。(注：其中有8個2相乘。)

步驟2：再思考第二個問題，a(9)和a(8)有什么關系？

對步驟1中的情況進行討論，考慮第1條邊和第9條邊的關系，按顏色相同與否來劃分：

第一種情況，如果它們顏色相同，則可以直接把這2條邊再連成圈，此時對應的染色方法數就是a(9);

第二種情況，如果它們顏色不同，則此時第8條邊與第1條邊顏色不同，如果去掉第9條邊，把前8條邊連成一個圈，此時對應的染色方法數就是a(8),故a(9)與a(8)的和就是步驟1的結論，因此a(9)+a(8)=768。

步驟3：綜合上述幾個問題，考慮原題目的答案。類似于步驟2的過程可得：a(3)+a(4)=3*(2^3)=24,a(4)+a(5)=3*(2^4)=48,a(5)+a(6)=3*(2^5)=96,a(6)+a(7)=3*(2^6)=192,a(7)+a(8)=3*(2^7)=384,a(8)+a(9)=3*(2^8)=768。(注：2^3表示2的3次方。)

下面我們先計算a(3)的值，相當于三角形用3種顏色染色，不同的方法數是a(3)=3*2*1=6。代入第一個等式可得a(4)=18,然后不斷代入其它等式遞推，最后可得a(9)=510。所以共有510種不同的染色方法。

注：高中生對數列熟悉以后，可以得到a(n)=2^n+2*[(-1)^n],感興趣的朋友可以自行推導。

思考題（3星難度）：6個小朋友圍成一個圓圈玩游戲，有多少種不同的排隊方法？