MathLabs

第6問

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

この構成は常に終了し(未着色の直線の本数が厳密に減少する)、正しさの段階により常にすべての有限領域が単色にならないよう保たれ、計数による評価により常に少なくとも ⌈n⌉≥n\lceil\sqrt n\rceil\ge\sqrt n 本の青い直線で終わる。これはすべての n≥2n\ge2 について成り立ち、特にすべての十分大きい nn について成り立つので、主張が証明された。