第3题

设

n

和

k

为正整数,

S

是平面上的

n

个点集,且

S

中任意三点不共线。假设对每个

P\in S

,至少有

k

个

S

中的点与

P

等距。证明

k<\frac12+\sqrt{2n}

第 3/5 步：与所有无序点对比较

通俗地说

可用的点对垂直平分线有限,多出的关联必然集中到某处。

N>n(n-1)=2\binom n2

详细分析

结合第一、二步得到 $N>n(n-1)$ 。但 $S$ 中无序点对 $\{A,B\}$ 只有 $\binom n2$ 个。因此平均每个点对所关联的垂直平分线点 $P$ 数量超过 $2$ .