Question

【题目】已知一个正多边形的每条边和对角线恰各染成2018种颜色之一，且所有边及对角线不全同色.若正多边形中不存在两色三角形（即三角形的三边恰被染成两种颜色），则称该多边形的染色是“和谐的”.求最大的正整数 ，使得存在一个和谐的染色正边形.

Answer 1

【答案】

【解析】

先考虑和谐染色的正边形的任意一个顶点 .可证明：对于每种颜色，由至多可以引出2016条该种颜色的边.

否则，设与顶点相连的边有相同的颜色（记为 ），于是，两两之间连边的颜色均为.

令顶点为与相连的边异于颜色的一个顶点（此顶点必然存在，否则，正边形的所有边均为颜色 ，与条件矛盾）.此时，顶点与的连边两两不同色，且均不为颜色 ，这样至少有2019种颜色，与条件矛盾.

从而，在和谐染色的正多边形中，任一顶点引出的边数为

.

再证明：存在和谐的染色正边形.

注意到，2017为素数.

故对任意整数 ，及任意整数，均存在唯一的 ，使得.

用表示个顶点，其中，、，数字0,1，…，2017表示2018种颜色.

对于顶点和 ，当 时，

若，

则将 与 之间的连边染颜色；

若 ，则将与 之间的连边染色颜色2017.

由2017为素数，知染色方式唯一确定.

下面证明：这样的染色方式是和谐的.

对于任意三个顶点、、，若、与 、之间的连边同色，则、之间的连边也必为此种颜色.

事实上，若、与、之间的连边同为颜色2017，则.故、 之间的连边也为颜色2017.

若、 与、之间的连边同为颜色，

则，.

故 .

从而，、 之间的连边也为颜色 .

综上，满足条件的.