MathLabs

第2問

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

下界と上界が一致する。

kmin⁡=2013k_{\min}=2013
詳しい解説

交互彩色した凸多角形から k≥2013k\ge2013、凸包と帯の構成から k≤2013k\le2013。従って最小値は k=2013k=2013。