每日一题[1539]远交近伐

在正 $2018$ 边形的每两个顶点之间均连一条线段，并把每条线段染成红色或蓝色．求此图形中三边颜色都相同的三角形的最小个数．

答案       $2\mathop{\rm C}\nolimits_{1009}^3$．

解析       设正 $2018$ 边形的顶点为 $A_i$（$i=1,2,\cdots,2018$），$N$ 是此图形中三边颜色都相同的三角形数目，$M$ 是此图形中三边颜色不全相等的三角形数目，则

$$M+N=\mathop{\rm C}\nolimits_{2018}^3,$$ 设 $x_i$ 是以顶点 $A_i$ 为端点的红色线段数目，则有 $$2M=\displaystyle\sum_{i=1}^{2018}x_i(2017-x_i)\leqslant 2018\cdot 1008\cdot 1009,$$ 从而 $$N\geqslant \mathop{\rm C}\nolimits_{2018}^3-1008\cdot 1009^2=2\mathop{\rm C}\nolimits_{1009}^3.$$ 另一方面，$N=2\mathop{\rm C}\nolimits_{1008}^3$ 是可以取得的．对于线段 $A_iA_j$，若 $|A_iA_j|$ 不超过 $A_1A_{505}$，则将其染成红色，否则将其染成蓝色．此时 $x_i=1008$（$i=1,2,\cdots,2018$），因此有 $N=2\mathop{\rm C}\nolimits_{1008}^3$．

备注       如图为正 $12$ 边形的染色方案．