2010 年中科大少年班初试 · 第 9 题

解答

共有二十个三角形且色组必须不同，所以 $\left(\genfrac{}{}{0ex}{}{m}{3}\right)\ge 20$，$m\ge 6$。若只用六色，二十个三色组合必须全部恰好出现一次。固定一种颜色，它在组合中出现 $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 次。但该颜色的每条边恰属于四个三角形，且虹彩条件保证一个三角形不重复含这色，因此总出现次数应是四的倍数，与十矛盾。故至少七色。 把六个顶点标为模七的 $0,1,\dots ,5$，边 $uv$ 染颜色 $u+v(\mathrm{mod}7)$，七个余数代表七色。任意三角形的相邻两边颜色不同。若其三色为 $r,s,t$，则顶点标号之和为 $S=(r+s+t)/2(\mathrm{mod}7)$，二在模七可逆；其顶点集合恰为 $\{S-r,S-s,S-t\}$。故相同色组必对应相同顶点三元组，不同三角形不会用同一色组。七色构造合法，最小值 $\boxed{7}$，选 B。