Question

凸n边形P中的每条边和每条对角线都被染为n种颜色中的一种颜色．问：对怎样的n，存在一种染色方式，使得对

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

Answer 1

当n≥3为奇数时，存在合乎要求的染法；当n≥4为偶数时，不存在所述的染法． 每3个顶点形成一个三角形，三角形的个数为C n 3 个，而颜色的三三搭配也刚好有C n 3 种，所以本题相当于要求不同的三角形对应于不同的颜色组合，即形成一一对应． 我们将多边形的边与对角线都称为线段．对于每一种颜色，其余的颜色形成C n-1 2 种搭配，所以每种颜色的线段（边或对角线）都应出现在C n-1 2 个三角形中，这表明在合乎要求的染法中，各种颜色的线段条数相等．所以每种颜色的线段都应当有 C 2n n = n-1 2 条． 当n为偶数时， n-1 2 不是整数，所以不可能存在合乎条件的染法．下设n=2m+1为奇数，我们来给出一种染法，并证明它满足题中条件．自某个顶点开始，按顺时针方向将凸2m+1边形的各个顶点依次记为A 1 ，A 2 ，A 2m+1 ．对于i?{1，2，2m+1}，按mod2m+1理解顶点A i ．再将2m+1种颜色分别记为颜色1，2，2m+1． 将边A i A i+1 染为颜色i，其中i=1，2，2m+1．再对每个i=1，2，2m+1，都将线段（对角线）A i-k A i+1+k 染为颜色i， 其中k=1，2，m-1．于是每种颜色的线段都刚好有m条．注意，在我们的染色方法之下，线段 A i 1 A j 1 与 A i 2 A j 2 同色， 当且仅当i 1 +j 1 ≡i 2 +j 2 （mod2m+1）．① 因此，对任何i≠j（mod2m+1），任何k≠0（mod2m+1），线段A i A j 都不与A i+k A j+k 同色．换言之， 如果i 1 -j 1 ≡i 2 -j 2 （mod2m+1）．② 则线段 A i 1 A j 1 都不与 A i 2 A j 2 同色． 任取两个三角形 △ A i 1 A j 1 A k 1 和 △ A i 2 A j 2 A k 2 ，如果它们之间至多只有一条边同色，当然它们不对应相同的颜色组合．如果它们之间有两条边分别同色，我们来证明第3条边必不同颜色．为确定起见，不妨设 A i 1 A j 1 与 A i 2 A j 2 同色． 情形1：如果 A j 1 A k 1 与 A j 2 A k 2 也同色，则由①知i 1 +j 1 ≡i 2 +j 2 （mod2m+1），j 1 +k 1 ≡j 2 +k 2 （mod2m+1）， 将二式相减，得f（A）=f（B），故由②知 A k 1 A i 1 不与 A k 2 A i 2 同色． 情形2：如果 A i 1 A k 1 与 A i 2 A k 2 也同色，则亦由①知i 1 +j 1 ≡i 2 +j 2 （mod2m+1），i 1 +k 1 ≡i 2 +k 2 （mod2m+1）， 将二式相减，亦得j 1 -k 1 ≡j 2 -k 2 （mod2m+1），亦由②知 A j 1 A k 1 与 A j 2 A k 2 不同色．总之， △ A i 1 A j 1 A k 1 与 △ A i 2 A j 2 A k 2 对应不同的颜色组合．