Question

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

Answer 1

略

解析:

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

每3個頂點形成一個三角形，三角形的個數(shù)為個，而顏色的三三搭配也剛好有種，所以本題相當于要求不同的三角形對應于不同的顏色組合，即形成一一對應．

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

當為偶數(shù)時，不是整數(shù)，所以不可能存在合乎條件的染法．下設為奇數(shù)，我們來給出一種染法，并證明它滿足題中條件．自某個頂點開始，按順時針方向將凸邊形的各個頂點依次記為．對于，按理解頂點．再將種顏色分別記為顏色．

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

．                ①

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

．                ②

則線段都不與同色．

任取兩個三角形和，如果它們之間至多只有一條邊同色，當然它們不對應相同的顏色組合．如果它們之間有兩條邊分別同色，我們來證明第3條邊必不同顏色．為確定起見，不妨設與同色．

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

，  

，  

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

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

，  

，  

將二式相減，亦得，亦由②知與不同色．總之，與對應不同的顏色組合．