第6問

平面上の直線の集合が一般の位置にあるとは、どの2直線も平行でなく、どの3直線も同一点を通らないことをいう。一般の位置にある直線の集合は平面をいくつかの領域に分け、そのうちいくつかは有限の面積をもつ;これらをその有限領域と呼ぶ。十分大きいすべての

n

に対して、一般の位置にある

n

本の直線からなるどの集合においても、少なくとも

\sqrt{n}

本の直線を、どの有限領域も境界がすべて青色にならないように青く塗ることができることを証明せよ。

ステップ 3/6: 課金規則:青い交点ごとに新しい赤い点は高々2つ

前のステップ次のステップ

X = \ell_1 \cap \ell_2 \text{ (both blue)} \implies \text{colour } X \text{ blue; mark } \le 2 \text{ neighbours of } X \text{ red}

詳しい解説

直線 $\ell$ が新たに青く塗られたとき、 $\ell$ とすでに青い直線 $\ell_1$ との各交点 $X$ について、 $X$ を青く塗り、 $\ell$ 上と $\ell_1$ 上の $X$ の隣接点、すなわち $\ell$ 上の $A_1,A_2$ と $\ell_1$ 上の $B_1,B_2$ を見る(隣接点がなければ未着色のダミー点を使う)。 $A_1$ 、 $A_2$ のどちらもまだ青くなければ両方を赤く塗る;そうでなければ $B_1$ 、 $B_2$ のどちらもまだ青くなければ両方を赤く塗る;それ以外の場合はこの4点のうち残る未着色の点(高々2つ)を赤く塗る。これにより、青い交点 $X$ ごとに高々 $2$ 個の赤い点が追加される。