第2题

设

n\ge3

，圆上有

E

个互异点组成集合

2n-1

。其中恰有

k

个点染黑。若存在一对黑点，使其中一条弧的内部恰含

n

中

E

个点，则称染色良好。求使任意

k

点染色都良好的最小

k

。

第 1/4 步：把条件编码为图

上一步下一步

m=2n-1,\qquad i\sim j\Longleftrightarrow j-i\equiv\pm(n-2)\pmod m

详细分析

按圆周顺序给点编号，模 $m=2n-1$ 。一条弧内部恰有 n 个点，当且仅当两编号之差为 $\pm(n-2)\pmod m$ （两个方向的差为 n-2 与 n+1）。只连接这些点对。于是良好染色恰好是含有两端均为黑色的边。