MathLabs

第2問

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

同色の各組は二本の平行線で囲む細い帯に入れられる。

2013=1+2⋅10062013=1+2\cdot1006
詳しい解説

最初の切断後、第一の場合は赤点が 2012 個、第二の場合は青点が 2012 個残る。これらを任意に 2 点ずつ組にする。各組 {A,B} に対し、AB に平行で十分近く、二本の間の閉じた帯が他の配置点を含まないような二直線を引く。この組は単色領域に隔離され、必要な本数は 2⋅10062\cdot1006 である。