MathLabs

第6問

平面上の直線の集合が一般の位置にあるとは、どの2直線も平行でなく、どの3直線も同一点を通らないことをいう。一般の位置にある直線の集合は平面をいくつかの領域に分け、そのうちいくつかは有限の面積をもつ;これらをその有限領域と呼ぶ。十分大きいすべての nn に対して、一般の位置にある nn 本の直線からなるどの集合においても、少なくとも n\sqrt{n} 本の直線を、どの有限領域も境界がすべて青色にならないように青く塗ることができることを証明せよ。
ステップ 4/6: 正しさ:有限領域がすべて青一色になることはない
前のステップ次のステップ
no blue line passes through a red point  ⟹  no finite region is entirely blue\text{no blue line passes through a red point} \implies \text{no finite region is entirely blue}
詳しい解説

構成上、青い直線が赤い点を通ることはない(点は、その直線がまだ未着色の間にのみ赤く塗られる)。背理法により、ある有限領域 P1⋯PmP_1\cdots P_m のすべての境界辺が青であると仮定する。P1,…,PmP_1,\ldots,P_m の中で最初に青くなった頂点を P2P_2 とし、辺 P1P2P_1P_2 が P2P3P_2P_3 より少し遅れて塗られたとする。このとき P3P_3 はその時点でまだ未着色でなければならない(そうでなければ P3P_3 が先に青くなっていたはず)。P1P_1 が新しい青い交点を挟んで P2P_2 の隣接点として調べられるとき、課金規則により P1,P3P_1,P_3 の少なくとも一方が赤く塗られる——これはすべての頂点が青いことと矛盾する。したがって、有限領域がすべて青一色になることはない。