第3問

正整数

n

と

k

、および平面上の

n

個の点からなる集合

S

を考える。ただし S のどの3点も一直線上にないものとする。

S

の各点

P\in S

に対し、

P

から等距離にある

S

の点が少なくとも

k

個あると仮定する。

k<\frac12+\sqrt{2n}

を証明せよ。

ステップ 1/5: 各中心からの重なりを数える

前のステップ次のステップ

ざっくり言うと

等距な2点の各ペアが垂直二等分線上の証人を1つ与える。

N\ge n\binom{k}{2}=\frac{nk(k-1)}2

詳しい解説

各 $P\in S$ について、 $P$ からの距離が共通な $k$ 個の点を選ぶ。選んだ任意の2点 $A,B$ は $PA=PB$ を満たすので、 $P$ は $AB$ の垂直二等分線上にある。したがって各 $P$ は少なくとも $\binom{k}{2}$ 個の重なり $(P,\{A,B\})$ を与え、 $n$ 個の点全体では $N\ge n\binom{k}{2}=\frac{nk(k-1)}2$ となる。