MathLabs

第2問

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

赤青の境界の隙間はすべて横切る必要があり、一本の直線が多角形の境界を横切れるのは高々二回である。

k≥40262=2013k\ge\frac{4026}{2}=2013
詳しい解説

凸な 4026 角形の頂点に赤 2013 個と青 2013 個を交互に置き、残りの青点を別の一般位置に置く。4026 本の境界辺は両端が異色なので、良い配置は各辺を横切る必要がある。一つの直線は境界と高々二回交わるから k≥4026/2=2013k\ge4026/2=2013。