Question

【題目】圓周上依次排列著共2013個不同的點，每個點染紅、藍、綠三色之一.在以任意兩個同色點為端點的圓弧上，與此兩端點異色的點的個數為偶數的染色方法稱為“好染色”問：所有好染色方法有多少種？

Answer 1

【答案】

【解析】

考慮一般的情形：

圓周上有n（奇數，）個不同的點時的好染色種數.

顯然，三種單色染色方法是好染色.

接下來求非單色好染色.

設Y表示圓周上n個不同點時非單色好染色的集合，X表示圓周上n個不同點時任意相鄰兩點異色的染色方法的集合.

可建立集合X與Y之間的一一對應.

考慮圓周上2n（n為奇數）邊形.設奇頂點的染色屬于集合定義每個偶頂點的顏色與其相鄰奇頂點不同.則得偶頂點的染色方法是好染色.

若以兩個同色點為端點的某一段圓弧之間沒有與端點同色的點，則稱這兩點為“最近同色點

顯然，一個染色方法為好染色點的充分必要條件為任意兩個最近同色點之間的異色點個數為偶數.

先證明偶頂點的染色方法為一個好染色，即證明任意兩個最近同色點的偶頂點之間包含的偶頂點的個數為偶數.

設M、N為任意兩個最近同色點的偶頂點（不妨設為紅色），且包含在M、N之間的偶頂點為k個.

當k=0時，則結論成立；

當時，記k個偶頂點為，則在M、N之間還包含k+1個奇頂點，記為，排列如下：.

因為點均不為紅色，所以，點A與的顏色不能為藍、綠（或綠、藍）（若出現上述兩種情形，則為紅色，與假設矛盾）.又點與不同色，則點中一個隔一個的為紅色.由點M、N為紅色，知點A、不為紅色.于是，點為紅色.從而，k為偶數，即M、N中包含的異色頂點為偶數個.因此，偶頂點染色方法為好染色.故得到一個從集合X到Y的映射f.

再證明：f為一一對應.

（1）f為單射.記圓周上2n邊形（為奇頂點，為偶頂點，其中i=1，2，…，n）.

設，且.

若，因為為非單色好染色，所以，存在兩個相鄰異色偶頂點（不妨設為、）.從而，得到a、b的對應這兩偶頂點之間的奇頂點的顏色相同.

由a、b及f的定義，知（，規定）三個頂點所染的顏色不同，換言之，為所染的顏色由、唯一確定，這樣由點、在a、b及f下所染顏色分別相同得所染顏色也相同，再由、所染顏色分別相同得所染的顏色也相同，依此類推，在a、b下，點所染的顏色分別相同，即，這與假設矛盾.

因此，f為單射.

（2）f為滿射.

對，設M、N是c中的相鄰異色偶頂點，則定義位于M、N之間的奇頂點不同于M、N的顏色.

若為c中一串連續同色（不妨設為紅色）偶頂點，它們位于偶頂點M、N間.若M、N同色（不妨設為藍色），則k為偶數（若為奇數，則兩同色點之間的異色點個數為奇數，與好染色矛盾），此時，定義M、N之間所有奇頂點的的顏色依次為綠、藍、綠、……藍、綠.

若M、N異色（不妨設M為藍色，N為綠色），則k為奇數（若不然，k為偶數，則每一段連續同色點的偶頂點為偶數個.否則，不妨設沿方向存在點，若點與N重合，則n為偶數，與n為奇數矛盾.若點與N不重合，則與相鄰的點C與M、N或之一同色，其之間所包含的異色點為奇數.矛盾）.此時，定義M、N之間所有奇頂點的的顏色依次為綠、藍、綠、……藍.如此定義的奇頂點染色方法，相鄰兩個奇頂點顏色相異.

最后計算集合X中元素的個數.記表示對圓周上n個點的好的染色法的個數.

由，，則

故好染色方法總數為