MathLabs

第6問

平面上の直線の集合が一般の位置にあるとは、どの2直線も平行でなく、どの3直線も同一点を通らないことをいう。一般の位置にある直線の集合は平面をいくつかの領域に分け、そのうちいくつかは有限の面積をもつ;これらをその有限領域と呼ぶ。十分大きいすべての nn に対して、一般の位置にある nn 本の直線からなるどの集合においても、少なくとも n\sqrt{n} 本の直線を、どの有限領域も境界がすべて青色にならないように青く塗ることができることを証明せよ。
ステップ 1/6: 準備:点、隣接、そして多角形としての有限領域
(n2) intersection points; each line carries n−1 of them\binom{n}{2} \text{ intersection points; each line carries } n-1 \text{ of them}
詳しい解説

(n2)\binom{n}{2} 個の対ごとの交点を単に点と呼ぶ;nn 本の直線それぞれがそのうち n−1n-1 個を持つ。同じ直線上の2点は、その直線上の他のどの点も厳密に両者の間になければ、隣接しているという。すると各有限領域は、各境界直線に沿った連続する頂点が隣接しているような凸多角形である。