第3题

设

n

和

k

为正整数,

S

是平面上的

n

个点集,且

S

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

P\in S

,至少有

k

个

S

中的点与

P

等距。证明

k<\frac12+\sqrt{2n}

第 1/5 步：从每个中心计数关联

上一步下一步

通俗地说

每一对等距点都在垂直平分线上提供一个见证点。

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

详细分析

对每个 $P\in S$ ，选取 $k$ 个到 $P$ 距离相同的点。任取两个被选点 $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$ 。