Question

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

Answer 1

【答案】

【解析】

考慮一般的情形：

圓周上有n（奇數(shù)，）個(gè)不同的點(diǎn)時(shí)的好染色種數(shù).

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

接下來求非單色好染色.

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

可建立集合X與Y之間的一一對應(yīng).

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

若以兩個(gè)同色點(diǎn)為端點(diǎn)的某一段圓弧之間沒有與端點(diǎn)同色的點(diǎn)，則稱這兩點(diǎn)為“最近同色點(diǎn)

顯然，一個(gè)染色方法為好染色點(diǎn)的充分必要條件為任意兩個(gè)最近同色點(diǎn)之間的異色點(diǎn)個(gè)數(shù)為偶數(shù).

先證明偶頂點(diǎn)的染色方法為一個(gè)好染色，即證明任意兩個(gè)最近同色點(diǎn)的偶頂點(diǎn)之間包含的偶頂點(diǎn)的個(gè)數(shù)為偶數(shù).

設(shè)M、N為任意兩個(gè)最近同色點(diǎn)的偶頂點(diǎn)（不妨設(shè)為紅色），且包含在M、N之間的偶頂點(diǎn)為k個(gè).

當(dāng)k=0時(shí)，則結(jié)論成立；

當(dāng)時(shí)，記k個(gè)偶頂點(diǎn)為，則在M、N之間還包含k+1個(gè)奇頂點(diǎn)，記為，排列如下：.

因?yàn)辄c(diǎn)均不為紅色，所以，點(diǎn)A與的顏色不能為藍(lán)、綠（或綠、藍(lán)）（若出現(xiàn)上述兩種情形，則為紅色，與假設(shè)矛盾）.又點(diǎn)與不同色，則點(diǎn)中一個(gè)隔一個(gè)的為紅色.由點(diǎn)M、N為紅色，知點(diǎn)A、不為紅色.于是，點(diǎn)為紅色.從而，k為偶數(shù)，即M、N中包含的異色頂點(diǎn)為偶數(shù)個(gè).因此，偶頂點(diǎn)染色方法為好染色.故得到一個(gè)從集合X到Y(jié)的映射f.

再證明：f為一一對應(yīng).

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

設(shè)，且.

若，因?yàn)?/span>為非單色好染色，所以，存在兩個(gè)相鄰異色偶頂點(diǎn)（不妨設(shè)為、）.從而，得到a、b的對應(yīng)這兩偶頂點(diǎn)之間的奇頂點(diǎn)的顏色相同.

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

因此，f為單射.

（2）f為滿射.

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

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

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

最后計(jì)算集合X中元素的個(gè)數(shù).記表示對圓周上n個(gè)點(diǎn)的好的染色法的個(gè)數(shù).

由，，則

故好染色方法總數(shù)為