Question

凸邊形中的每條邊和每條對(duì)角線都被染為n種顏色中的一種顏色．問(wèn)：對(duì)怎樣的n，存在一種染色方式，使得對(duì)于這n種顏色中的任何3種不同顏色，都能找到一個(gè)三角形，其頂點(diǎn)為多邊形的頂點(diǎn)，且它的3條邊分別被染為這3種顏色？

Answer 1

見(jiàn)解析

解析:

當(dāng)為奇數(shù)時(shí)，存在合乎要求的染法；當(dāng)為偶數(shù)時(shí)，不存在所述的染法。

每3個(gè)頂點(diǎn)形成一個(gè)三角形，三角形的個(gè)數(shù)為個(gè)，而顏色的三三搭配也剛好有種，所以本題相當(dāng)于要求不同的三角形對(duì)應(yīng)于不同的顏色組合，即形成一一對(duì)應(yīng)．

我們將多邊形的邊與對(duì)角線都稱(chēng)為線段．對(duì)于每一種顏色，其余的顏色形成種搭配，所以每種顏色的線段（邊或?qū)�角線）都應(yīng)出現(xiàn)在個(gè)三角形中，這表明在合乎要求的染法中，各種顏色的線段條數(shù)相等．所以每種顏色的線段都應(yīng)當(dāng)有條．

當(dāng)為偶數(shù)時(shí)，不是整數(shù)，所以不可能存在合乎條件的染法．下設(shè)為奇數(shù)，我們來(lái)給出一種染法，并證明它滿足題中條件．自某個(gè)頂點(diǎn)開(kāi)始，按順時(shí)針?lè)较驅(qū)⑼?img width=45 height=19 src="http://thumb.zyjl.cn/pic1/1899/sx/96/297896.gif" >邊形的各個(gè)頂點(diǎn)依次記為．對(duì)于，按理解頂點(diǎn)．再將種顏色分別記為顏色．

將邊染為顏色，其中．再對(duì)每個(gè)，都將線段（對(duì)角線）染為顏色，其中．于是每種顏色的線段都剛好有條．注意，在我們的染色方法之下，線段與同色，當(dāng)且僅當(dāng)

．                ①

因此，對(duì)任何，任何，線段都不與同色．換言之，如果

．                ②

則線段都不與同色．

任取兩個(gè)三角形和，如果它們之間至多只有一條邊同色，當(dāng)然它們不對(duì)應(yīng)相同的顏色組合．如果它們之間有兩條邊分別同色，我們來(lái)證明第3條邊必不同顏色．為確定起見(jiàn)，不妨設(shè)與同色．

情形1：如果與也同色，則由①知

，  

，  

將二式相減，得，故由②知不與同色．

情形2：如果與也同色，則亦由①知

，  

，  

將二式相減，亦得，亦由②知與不同色．總之，與對(duì)應(yīng)不同的顏色組合．