Question

凸边形中的每条边和每条对角线都被染为n种颜色中的一种颜色．问：对怎样的n，存在一种染色方式，使得对于这n种颜色中的任何3种不同颜色，都能找到一个三角形，其顶点为多边形的顶点，且它的3条边分别被染为这3种颜色？

Answer 1

略

解析:

当为奇数时，存在合乎要求的染法；当为偶数时，不存在所述的染法。

每3个顶点形成一个三角形，三角形的个数为个，而颜色的三三搭配也刚好有种，所以本题相当于要求不同的三角形对应于不同的颜色组合，即形成一一对应．

我们将多边形的边与对角线都称为线段．对于每一种颜色，其余的颜色形成种搭配，所以每种颜色的线段（边或对角线）都应出现在个三角形中，这表明在合乎要求的染法中，各种颜色的线段条数相等．所以每种颜色的线段都应当有条．

当为偶数时，不是整数，所以不可能存在合乎条件的染法．下设为奇数，我们来给出一种染法，并证明它满足题中条件．自某个顶点开始，按顺时针方向将凸边形的各个顶点依次记为．对于，按理解顶点．再将种颜色分别记为颜色．

将边染为颜色，其中．再对每个，都将线段（对角线）染为颜色，其中．于是每种颜色的线段都刚好有条．注意，在我们的染色方法之下，线段与同色，当且仅当

．                ①

因此，对任何，任何，线段都不与同色．换言之，如果

．                ②

则线段都不与同色．

任取两个三角形和，如果它们之间至多只有一条边同色，当然它们不对应相同的颜色组合．如果它们之间有两条边分别同色，我们来证明第3条边必不同颜色．为确定起见，不妨设与同色．

情形1：如果与也同色，则由①知

，  

，  

将二式相减，得，故由②知不与同色．

情形2：如果与也同色，则亦由①知

，  

，  

将二式相减，亦得，亦由②知与不同色．总之，与对应不同的颜色组合．