设 $n\geqslant 3$，考虑一 个圆周上 $2n-1$ 个不同的点所成的集合 $E$．如果将 $E$ 中的一些点染成黑色，使得至少有两个黑点，以它们为端点的两条弧之一的内部恰含 $E$ 的 $n$ 个点，那么称这种染色法是“好的”，若 $E$ 的 $k$ 个点染成黑点的每一种染色法都是好的，试求 $k$ 的最小值．（捷克斯洛伐克）
【难度】
【出处】
1990年第31届IMO试题
【标注】
【答案】
略
【解析】
将 $E$ 中的点依次记为 $1,2,\cdots,2n-1$，并将点 $i$ 与 $i+(n-1)$ 用一条边相连（规定 $j+(2n-1)k,k\in Z$，与 $j$ 表示同一个点），这样得到一个图 $G$，$G$ 中的每个顶点的度为 $2$（与两个点相连），并且差为 $3$ 的两个点与同一个点相邻．
因为图 $G$ 的每个顶点的度为 $2$，所以图 $G$ 由一个或几个圈组成．
当 $3\nmid 2n-1$ 时，$1,2,\cdots,2n-1$ 中每一点 $j$ 都可以表示成 $3k$ 的形式（即方程 $3x\equiv j\mod{2n-1}$ 有解），因此图 $G$ 是一个长为 $2n-1$ 的圈．在这圈上可以取出 $n-1$ 个互不相邻的点，而且至多可以取出 $n-1$ 个互不相邻的点．
当 $3|2n-1$ 时，图 $G$ 由三个长为 $\dfrac{2n-1}{3}$ 的圈组成，各个圈的顶点集合为
$\left\{3k+1,k=0,1,\cdots,\dfrac{2n-4}{3}\right\}$
$\left\{3k+2,k=0,1,\cdots,\dfrac{2n-4}{3}\right\}$
$\left\{3k,k=0,1,\cdots,\dfrac{2n-1}{3}\right\}$
每个圈上至少可以取出 $\dfrac{1}{2}\left(\dfrac{2n-1}{3}-1\right)=\dfrac{n-2}{3}$ 个点，它们两两不相邻，总共可取出 $n-2$ 个点互不相邻．
综上所述，$k_{\min}=\begin{cases}n,&&当3\nmid 2n-1时\\
n-1,&&当3|2n-1时\end{cases}$
因为图 $G$ 的每个顶点的度为 $2$，所以图 $G$ 由一个或几个圈组成．
当 $3\nmid 2n-1$ 时，$1,2,\cdots,2n-1$ 中每一点 $j$ 都可以表示成 $3k$ 的形式（即方程 $3x\equiv j\mod{2n-1}$ 有解），因此图 $G$ 是一个长为 $2n-1$ 的圈．在这圈上可以取出 $n-1$ 个互不相邻的点，而且至多可以取出 $n-1$ 个互不相邻的点．
当 $3|2n-1$ 时，图 $G$ 由三个长为 $\dfrac{2n-1}{3}$ 的圈组成，各个圈的顶点集合为
$\left\{3k+1,k=0,1,\cdots,\dfrac{2n-4}{3}\right\}$
$\left\{3k+2,k=0,1,\cdots,\dfrac{2n-4}{3}\right\}$
$\left\{3k,k=0,1,\cdots,\dfrac{2n-1}{3}\right\}$
每个圈上至少可以取出 $\dfrac{1}{2}\left(\dfrac{2n-1}{3}-1\right)=\dfrac{n-2}{3}$ 个点，它们两两不相邻，总共可取出 $n-2$ 个点互不相邻．
综上所述，$k_{\min}=\begin{cases}n,&&当3\nmid 2n-1时\\
n-1,&&当3|2n-1时\end{cases}$
答案
解析
备注
