MathLabs

第2题

设 n≥3n\ge3,圆上有 EE 个互异点组成集合 2n−12n-1。其中恰有 kk 个点染黑。若存在一对黑点,使其中一条弧的内部恰含 nn 中 EE 个点,则称染色良好。求使任意 kk 点染色都良好的最小 kk。
第 4/4 步:读出精确阈值
kmin⁡={n,n≡0,1(mod3),n−1,n≡2(mod3),k_{\min}=\begin{cases}n,&n\equiv0,1\pmod3,\\n-1,&n\equiv2\pmod3,\end{cases}
详细分析

在每个奇圈上交替选点即可得到上述大小的独立集,所以界是精确的。因此 kmin⁡=nk_{\min}=n 时 n≡0,1(mod3)n\equiv0,1\pmod3,而 kmin⁡=n−1k_{\min}=n-1 时 n≡2(mod3)n\equiv2\pmod3。