MathLabs

第6問

平面上の直線の集合が一般の位置にあるとは、どの2直線も平行でなく、どの3直線も同一点を通らないことをいう。一般の位置にある直線の集合は平面をいくつかの領域に分け、そのうちいくつかは有限の面積をもつ;これらをその有限領域と呼ぶ。十分大きいすべての nn に対して、一般の位置にある nn 本の直線からなるどの集合においても、少なくとも n\sqrt{n} 本の直線を、どの有限領域も境界がすべて青色にならないように青く塗ることができることを証明せよ。
ステップ 5/6: 計数による評価:k 本の青い直線が n ≤ k² を強いる
前のステップ次のステップ
n−k≤2(k2)=k(k−1)  ⟹  k≥nn-k \le 2\binom{k}{2} = k(k-1) \implies k \ge \sqrt{n}
詳しい解説

この過程が kk 本の青い直線で終わったとする。すべての非青の直線は少なくとも1つの赤い点を含まねばならない(そうでなければ過程は停止していない)。各赤い点は、まだ青くなかった直線に沿う青同士の交点の隣接点として作られるので、ちょうど1本の青い直線と1本の非青の直線上にある。tt 番目の青い直線を塗ると高々 t−1t-1 個の新しい青い交点が生まれ、それぞれ高々 22 個の赤い点を生むので、赤い点の総数は高々 2(k2)=k(k−1)2\binom{k}{2}=k(k-1) である。n−kn-k 本の非青の直線それぞれが少なくとも1つの赤い点を必要とするので、n−k≤k(k−1)n-k\le k(k-1)、すなわち n≤k2n\le k^2 となり、k≥nk\ge\sqrt n を得る。