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

2023-05-29 11:38发布

这道初中数学的题目是:
凸n边形P中的每条边和每条对角线都被染为n种颜色中的一种颜色.问:对怎样的n,存在一种染色方式,使得对于这n种颜色中的任何3种不同颜色,都能找到一个三角形,其顶点为多边形P的顶点,且它的3条边分别被染为这3种颜色?
1条回答
卡西莫多
1楼-- · 2023-05-29 11:54
这道初中数学题的正确答案为:
当n≥3为奇数时,存在合乎要求的染法;当n≥4为偶数时,不存在所述的染法.
每3个顶点形成一个三角形,三角形的个数为Cn3个,而颜色的三三搭配也刚好有Cn3种,所以本题相当于要求不同的三角形对应于不同的颜色组合,即形成一一对应.
我们将多边形的边与对角线都称为线段.对于每一种颜色,其余的颜色形成Cn-12种搭配,所以每种颜色的线段(边或对角线)都应出现在Cn-12个三角形中,这表明在合乎要求的染法中,各种颜色的线段条数相等.所以每种颜色的线段都应当有
C2n
n
=
n-1
2
条.
当n为偶数时,
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条.注意,在我们的染色方法之下,线段Ai1Aj1Ai2Aj2同色,
当且仅当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同色.
任取两个三角形Ai1Aj1Ak1Ai2Aj2Ak2,如果它们之间至多只有一条边同色,当然它们不对应相同的颜色组合.如果它们之间有两条边分别同色,我们来证明第3条边必不同颜色.为确定起见,不妨设Ai1Aj1Ai2Aj2同色.
情形1:如果Aj1Ak1Aj2Ak2也同色,则由①知i1+j1≡i2+j2(mod2m+1),j1+k1≡j2+k2(mod2m+1),
将二式相减,得f(A)=f(B),故由②知Ak1Ai1不与Ak2Ai2同色.
情形2:如果Ai1Ak1Ai2Ak2也同色,则亦由①知i1+j1≡i2+j2(mod2m+1),i1+k1≡i2+k2(mod2m+1),
将二式相减,亦得j1-k1≡j2-k2(mod2m+1),亦由②知Aj1Ak1Aj2Ak2不同色.总之,Ai1Aj1Ak1Ai2Aj2Ak2对应不同的颜色组合.
解题思路
C2n
n

一周热门 更多>

相关问题