MathLabs

第2問

平面上の 40274027 個の点からなる配置が、20132013 個の赤い点と 20142014 個の青い点からなり、どの3点も同一直線上にないとき、コロンビア配置と呼ぶ。いくつかの直線を引くことで、平面はいくつかの領域に分けられる。あるコロンビア配置に対する直線の配置が良いとは、次の2条件を満たすことをいう:(1) どの直線も配置の点を通らない;(2) どの領域も両方の色の点を含まない。40274027 個の点からなるどのコロンビア配置に対しても kk 本の直線からなる良い配置が存在するような、最小の kk の値を求めよ。
ステップ 4/5: すべての領域が単色であることを確認する
ざっくり言うと

切り離した一点または一組は単色で、帯の外に残る各領域はもう一方の色だけを含む。

k≤1+2⋅1006=2013k\le1+2\cdot1006=2013
詳しい解説

補助直線を一般の位置で十分近く選び、配置点を通らないようにする。各帯には同色の組(または凸包上の一点)だけが入り、すべての帯の外の点は反対色である。したがって両色を含む領域はなく、2013 本で十分である。