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

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

题目简介

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

题目详情

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

题型：解答题难度：中档来源：不详

答案

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

C

2n

n

=class="stub"n-1

2

条．
当n为偶数时，class="stub"n-1

2

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

上一篇 : 电表的计数器上先后两次读数之
下一篇 : 1～8八个数排成一排，要求相邻两个

更多内容推荐