Question

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

Answer 1

分析：首先对n进行讨论，当n≥3为奇数时，存在合乎要求的染法；当n≥4为偶数时，不存在所述的染法，每3个顶点形成一个三角形，三角形的个数为C_n³个，而颜色的三三搭配也刚好有C_n³种，对于一种颜色固定，其余的颜色形成C_n-1²种搭配，所以每种颜色的线段（边或对角线）都应出现在C_n-1²个三角形中，这表明在合乎要求的染法中，各种颜色的线段条数相等．所以每种颜色的线段都应当有

C 2 n

n

=

n-1

2

条，然后对n进行讨论．

解答：解：当n≥3为奇数时，存在合乎要求的染法；当n≥4为偶数时，不存在所述的染法．
每3个顶点形成一个三角形，三角形的个数为C_n³个，而颜色的三三搭配也刚好有C_n³种，所以本题相当于要求不同的三角形对应于不同的颜色组合，即形成一一对应．
我们将多边形的边与对角线都称为线段．对于每一种颜色，其余的颜色形成C_n-1²种搭配，所以每种颜色的线段（边或对角线）都应出现在C_n-1²个三角形中，这表明在合乎要求的染法中，各种颜色的线段条数相等．所以每种颜色的线段都应当有

C 2 n

n

=

n-1

2

条．
当n为偶数时，

n-1

2

不是整数，所以不可能存在合乎条件的染法．下设n=2m+1为奇数，我们来给出一种染法，并证明它满足题中条件．自某个顶点开始，按顺时针方向将凸2m+1边形的各个顶点依次记为A₁，A₂，A_2m+1．对于i∉{1，2，2m+1}，按mod2m+1理解顶点A_i．再将2m+1种颜色分别记为颜色1，2，2m+1．
将边A_iA_i+1染为颜色i，其中i=1，2，2m+1．再对每个i=1，2，2m+1，都将线段（对角线）A_i-kA_i+1+k染为颜色i，
其中k=1，2，m-1．于是每种颜色的线段都刚好有m条．注意，在我们的染色方法之下，线段Ai1Aj1与Ai2Aj2同色，
当且仅当i₁+j₁≡i₂+j₂（mod2m+1）．①
因此，对任何i≠j（mod2m+1），任何k≠0（mod2m+1），线段A_iA_j都不与A_i+kA_j+k同色．换言之，
如果i₁-j₁≡i₂-j₂（mod2m+1）．②
则线段Ai1Aj1都不与Ai2Aj2同色．
任取两个三角形△Ai1Aj1Ak1和△Ai2Aj2Ak2，如果它们之间至多只有一条边同色，当然它们不对应相同的颜色组合．如果它们之间有两条边分别同色，我们来证明第3条边必不同颜色．为确定起见，不妨设Ai1Aj1与Ai2Aj2同色．
情形1：如果Aj1Ak1与Aj2Ak2也同色，则由①知i₁+j₁≡i₂+j₂（mod2m+1），j₁+k₁≡j₂+k₂（mod2m+1），
将二式相减，得f（A）=f（B），故由②知Ak1Ai1不与Ak2Ai2同色．
情形2：如果Ai1Ak1与Ai2Ak2也同色，则亦由①知i₁+j₁≡i₂+j₂（mod2m+1），i₁+k₁≡i₂+k₂（mod2m+1），
将二式相减，亦得j₁-k₁≡j₂-k₂（mod2m+1），亦由②知Aj1Ak1与Aj2Ak2不同色．总之，△Ai1Aj1Ak1与△Ai2Aj2Ak2对应不同的颜色组合．

点评：本题主要考查排列与组合的知识点，解答本题的关键是对凸n边形的n进行讨论，熟练运用排列组合的知识找到满足条件的n，本题难度较大．