Question

對一個邊長互不相等的凸n（n≥3）邊形的邊染色，每條邊可以染紅、黃、藍三種顏色中的一種，但是不允許相鄰的邊有相同的顏色．問：共有多少種不同的染色方法？

Answer 1

分析：設n邊形的不同的染色方法有p_n種，由題意得p₃=

A

3 3

=6，根據當n≥4時，pn=3×2n-1-pn-1，數列{Pn-2n}為公比為-1的等比數列，這樣可求得Pn-2n的通項公式，從而求得P_n．

解答：解：設n邊形的不同的染色方法有p_n種．易知三角形的染色方法p₃=

A

3 3

=6．       

當n≥4時，首先，對于邊a₁，有3種不同的染法，由于邊a₂的顏色與邊a₁的顏色不同，
∴對邊a₂有2種不同的染法，類似地，對邊a₃，…，邊a_n-1均有2種染法．對于邊a_n，用與邊a_n-1不同的2種顏色染色，
但是，這樣也包括了它與邊a₁顏色相同的情況，
而邊a₁與邊a_n顏色相同的不同染色方法數就是凸n-1邊形的不同染色方法數的種數p_n-1，
∴pn=3×2n-1-pn-1，pn-2n=-(pn-1-2n-1)．數列{Pn-2n}為公比為-1的等比數列，
∴pn-2n=(-1)n-3(p3-23)=(-1)n-2•2，
∴pn=2n+(-1)n•2，n≥3．
綜上所述，不同的染色方法數為pn=2n+(-1)n•2．

點評：解答本題的關鍵是利用n邊形的染色方法數與n-1邊形的染色方法數的關系，構造等比數列求P_n．