2009 年山西预赛 · 第 11 题

解答

（1）七个盒子作图的七顶点，共有一种颜色就视为禁配。每色只在两盒各一次，每盒含两色，故每点至多有两个禁配邻点。允许图于是每点度至少四。 说明这图必有包含全部七点的圈。取最长简单路径 $v_1,\dots ,v_k$，两端的邻点全在路径上。索引 $i\in \{1,\dots ,k-1\}$ 中，使 $v_1$ 邻接 $v_{i+1}$ 的至少四个，使 $v_k$ 邻接 $v_i$ 的也至少四个。总数八大于 $k-1\le 6$，必有共同 $i$，于是路径可首尾重新连接成包含其全部点的圈

原允许图连通，因为若不连通，每个分量至少有五点，而总共只有七点。若上述圈未含全图，必有圈外点与圈上点相邻，沿该边再绕圈即可得到更长路径，矛盾。因此有七点圈。按此圈将盒放到七边形顶点，相邻盒无共色，即四珠互不同色。 （2）五色情形并非总能。取三盒为 $\{1,2\},\{2,3\},\{3,1\}$，另两盒都为 $\{4,5\}$，每色恰两珠且每盒异色。前三盒两两共色，必须在五边形上互不相邻，但五边形上最多能放两个两两不相邻的顶点，不能放三个。因此结论为 $\boxed{\text{七种颜色总能，五种颜色不一定}}$。