第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）であることと同値。これらの組だけを結ぶ。すると良い塗り方とは黒い両端を持つ辺がある塗り方である。