MathLabs

第3問

正整数 nn と kk、および平面上の nn 個の点からなる集合 SS を考える。ただし S のどの3点も一直線上にないものとする。SS の各点 P∈SP\in S に対し、PP から等距離にある SS の点が少なくとも kk 個あると仮定する。k<12+2nk<\frac12+\sqrt{2n} を証明せよ。
ステップ 3/5: 全ての無順序ペアと比較する
前のステップ次のステップ
ざっくり言うと

利用できるペアの垂直二等分線は有限なので、余分な重なりはどこかに集中する。

N>n(n−1)=2(n2)N>n(n-1)=2\binom n2
詳しい解説

ステップ1,2を合わせると N>n(n−1)N>n(n-1) となる。一方、SS における無順序ペア {A,B}\{A,B\} は (n2)\binom n2 個しかない。したがって1ペアあたりに付随する点 PP の平均個数は 22 を超える。