MathLabs

第6問

整数 n>1n>1 と、平面上の nn 点からなる集合 SS を考える。SS の異なる2点間の距離はすべて少なくとも 11 とする。ある絶対定数 c>0c>0 に対して、SS を分離する直線 ℓ\ell で、SS の任意の点から ℓ\ell までの距離が少なくとも cn−1/3c n^{-1/3} となるものが存在することを証明せよ。（直線 ℓ\ell が点集合 SS を分離するとは、SS の2点を結ぶある線分が ℓ\ell と交わることである。）
ステップ 1/8: 最大の射影間隔を選ぶ
前のステップ次のステップ
ざっくり言うと

射影の間隔から分離直線が得られる。

d(P,Q)≥1(PeQ),δ=max⁡mmax⁡{extgapofconsecutiveprojectionsontom}d(P,Q)\ge1\quad(P e Q),\qquad \delta=\max_{m}\max\{ ext{gap of consecutive projections onto }m\}
詳しい解説

任意の直線 mm への射影で、連続する射影の最大間隔を δ\delta とする。長さ δ\delta の間隔の中点を通り mm に垂直な直線は SS を分離し、各点との距離を少なくとも δ/2\delta/2 にする。