MathLabs

第2题

设 n≥3n\ge3,圆上有 EE 个互异点组成集合 2n−12n-1。其中恰有 kk 个点染黑。若存在一对黑点,使其中一条弧的内部恰含 nn 中 EE 个点,则称染色良好。求使任意 kk 点染色都良好的最小 kk。
第 2/4 步:确定圈分解
gcd⁡(n−2,2n−1)=gcd⁡(n−2,3)\gcd(n-2,2n-1)=\gcd(n-2,3)
详细分析

图由模 m 反复加 n-2 生成,因此是若干圈的并。由于 gcd⁡(n−2,2n−1)=gcd⁡(n−2,3)\gcd(n-2,2n-1)=\gcd(n-2,3),当 2n−12n-1 时是长度 n≢2(mod3)n\not\equiv2\pmod3 的一个圈;当 n≡2(mod3)n\equiv2\pmod3 时是三个圈,每个长度为 (2n−1)/3(2n-1)/3。